Smallest common multiples: potential infinite loop issue

Smallest common multiples: potential infinite loop issue
0

#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.


#3

Do you mind posting your final solution and nest it in [spoiler] and [/spoiler] tags to blur it out?

I want to check something in regards to your comment about while loops vs do while loops.


#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]);


#5

FYI - You were close with your original while do (shown above). You just needed to move the times++; to inside the if statement’s true block before the break; like below.

var j; 
 times = 1;
  do {
    arr = newArr[0] * newArr[1] * times;
    for (j = 2; j &lt; newArr.length; j++) {
      if (arr % newArr[j] != 0) {
        times++; // should have been here and it would have worked
        break;
      }
    }
  } while(j &lt; newArr.length);
  return arr;
}

#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.


#7

I totally agree that your final solution is great. I just wanted to let you know it was possible to solve it with a while loop vs do while. FYI - There is no performance difference between the two loop types. The reason your first attempt triggered the infinite loop message is because it actually had an infinite loop. You actually may have known this already, but I thought I would make that point clear in case it was not.


#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.