Smallest common multiples: potential infinite loop issue

JavaScript
1 

function smallestCommons(arr) {

  // sort the arr argument in ascending order if not
  arr = arr.sort(function(a, b) {
    return a-b;
  });
  
  
  var arrs = [];
  var min = arr[0];
  var max = arr[1];
  var flag = 0;
  var times = 1;
  
  
  init(arrs, min, max);
  
  while (times < 100) {
    flag = check(arrs, min, max, times, flag);
    if (flag == 1) {
      return arrs[0][times-1];
    }
    else {
      times++;
      createMultiple(arrs, min, max, times);
    }
   
  }
  return arrs;
}






// all defined seperate functions..................................

// initiate the nested array to hold the multiples for all numbers
function init(arrs, min, max) {
  for (var i = min; i <= max; i++) {
    arrs[i-min] = [i];
   }
}
  

// check if least common mulitples; if not, generate more multiples
function check(arrs, min, max, times, flag) {
  var count = 0;
  for (var x1 = 0; x1 <= max-min; x1++) {
    if (arrs[x1].indexOf(arrs[0][times-1]) < 0) {
      break;
    }
    else {
      count++;
    }
  }
  
  if (count > max-min) {
    flag = 1;
  }
  
  return flag;
}


// generate multiples
function createMultiple(arrs, min, max, times) {
     for (var num = min; num <= max; num++) {
     arrs[num-min].push(num * times);
   }
  return arrs;
}



// test 
smallestCommons([1,5]);

For the purpose of testing my code, I try smallestCommons([1,5]); first. Since, the smallest common multiple for array range of [1, 5] is 60, which has 12 times multiplication. I provide the while(times < 100), and it outputs correctly as: 60. But for bigger number like smallestCommons([1, 13]), if I run while(times < 360361), my computer run nearly ten seconds, and pop out: Error: potential infinite loop at line 20....., which indicats while() loop. Sure, same result found when use while(true). Could anyone provide some hints about this problem? Thanks in advance.

2

I am aware of the running time for my previous code. After changing the strategy of finding the smallest multiple: starting from the first two biggest number in the array range. …

 var times = 1;
  var j=0;  
  while(j < newArr.length) {
    // 
    arr = newArr[0] * newArr[1] * times;
    for (j = 2; j < newArr.length; j++) {
      if (arr % newArr[j] != 0) {
        break;
      }
      j++;

    times++; 
    }
  }
}// while loop

Again, “Error: potential infinite loop…”.
After googling for some time, I found a post in stackflow: https://stackoverflow.com/questions/44481131/why-the-huge-time-difference-between-while-and-do-while-in-javascript
I wonder the ‘very long’ executing time of while () loop might be the reason in my case.
I then switched to do{} while() to see whether it works in my case:

 var j; 
 times = 1;
  do {
    arr = newArr[0] * newArr[1] * times;
    for (j = 2; j < newArr.length; j++) {
      if (arr % newArr[j] != 0) {
        break;
      }
    }
    times++;
  } while(j < newArr.length);

  return arr;
  
}

It finally works.
Well, very interesting!
To sum up what I have learnt from my failure story:

  1. Thinking of a better solution to solve the same problem.
    I first attempted to create a nested array, with each subarray containing multiples for each of the numbers in the range. And then taking the smallest number aside, trying to check whether other multiples from all the other subarrays has ‘indexoOf’ . In such way, executing time increases as repeatedly searching other subarrays for all of their multiples.
  2. Be ware of the 'potential infinite loop’
    Bad solution, even logically correct (my first attempt), could lead to other issues.

Keep in mind the huge running time difference between while() loop and Do... While loop.

4

Sure. Here is my final solution:


function smallestCommons(arr) {

// sort argument array from greatest to smallest 
  arr = arr.sort(function(a, b) {
    return b-a;
  });

// fit all numbers in the range
  var newArr = [];
  for (var i = 0; i <= arr[0]-arr[1]; i++) {
    newArr.push(arr[0]-i);
  }

 var j; 
 times = 1;
  do {
    arr = newArr[0] * newArr[1] * times;
    for (j = 2; j < newArr.length; j++) {
      if (arr % newArr[j] != 0) {
        break;
      }
    }
    times++;
  } while(j < newArr.length);

  return arr;
  
}


// test 
smallestCommons([1,5]);
6

Many thanks to your reply. I understand your adjustment. But my posted solution works fine as well. When if (arr % newArr[j] != 0) true, execute break, and jump out the for loop, and execute the following times++ statement. So, it works. Still appreciate your effort and your time in reply to my post.

8

As I reviewed back my first attempt using while loop, I do find the problem that times++ statement was nested inside the for loop which will not be updated after one break. Thus, no steps are moved forward to find the ‘smallest common multiple’.

Thanks a lot.