JavaScript中级算法：求解给定范围的Smallest Common Multiple问题

Hey there! Let's clear up your confusion first, then walk through solving this problem step by step.

First: What does "evenly divisible" mean? #

No need to overcomplicate this! Evenly divisible just means when you divide one number by another, there's no remainder left. For example, 12 is evenly divisible by 3 because 12 ÷ 3 = 4 with a remainder of 0. If there was a remainder (like 13 ÷ 3 = 4 with remainder 1), it's not evenly divisible.

The Problem Breakdown #

You already know about the lowest common multiple (LCM) of two numbers, but this problem asks for something a bit broader: the smallest number that's evenly divisible by every integer between your two input numbers (including the inputs themselves).

For example, if you get [1,5], you need the smallest number divisible by 1, 2, 3, 4, and 5 — which is 60.

Fixing Your Existing Code #

Let's go through your code and fix the gaps, plus add the logic needed to calculate the smallest common multiple:

Step 1: Generate the full range of numbers #

Your current loop stops at i < changedArr[1], which misses the largest number in the range. Also, using arr.sort() directly modifies the original array — better to make a copy first to avoid side effects.

Step 2: Calculate GCD (Greatest Common Divisor) #

To find the LCM of two numbers, we first need their GCD. We can use the Euclidean algorithm for this, which is super efficient.

Step 3: Calculate LCM of two numbers #

The formula for LCM of a and b is:
LCM(a, b) = (a * b) / GCD(a, b)

Step 4: Iterate to find LCM of the entire range #

We start with the first number's LCM, then keep updating it with each subsequent number in the range until we've covered all values.

Full Working Code #

function smallestCommons(arr) {
  // Make a copy of the array before sorting to avoid modifying the original
  const sortedArr = [...arr].sort((a, b) => a - b);
  const min = sortedArr[0];
  const max = sortedArr[1];
  
  // Generate all numbers in the range (including min and max)
  const numberRange = [];
  for (let i = min; i <= max; i++) {
    numberRange.push(i);
  }

  // Helper function to calculate GCD using Euclidean algorithm
  const gcd = (a, b) => {
    while (b !== 0) {
      let temp = b;
      b = a % b;
      a = temp;
    }
    return a;
  };

  // Helper function to calculate LCM of two numbers
  const lcm = (a, b) => {
    return (a * b) / gcd(a, b);
  };

  // Calculate LCM for the entire range by iterating through each number
  let result = numberRange[0];
  for (let i = 1; i < numberRange.length; i++) {
    result = lcm(result, numberRange[i]);
  }

  return result;
}

console.log(smallestCommons([1,5])); // Outputs 60
console.log(smallestCommons([1,3])); // Outputs 6

Let's Test It #

• For [1,3]: The range is [1,2,3]. LCM(1,2) is 2, then LCM(2,3) is 6 — which matches the example you gave.
• For [1,5]: We calculate LCM(1,2)=2, LCM(2,3)=6, LCM(6,4)=12, LCM(12,5)=60 — which is the correct answer.

内容的提问来源于stack exchange，提问作者AndrewNeedsHelp