Finding all points on the line where distance between each of them is dividable by X recently I received ( during job interview) a challange to write a method for finding a largest subset of points where distance between them is dividable by a set number.

example points array is A =[-3,-2,1,0,8,7,1]

example number we will be dividing by is 3

so for array above  the biggest subset is [-2,1,7,1]
because:

distance between points is counted as follows abs(A[1] - A[2]) = 3

distance between points 7 and -2 is 9 --> 9 % 3 = 0 so its ok.

I wrote code:

var A = [-3, -2, 1, 0, 8, 7, 1];
    var biggestArray = [];
    (A).forEach(element =&gt; {
        Z=[];
        Z.push(element);
        for (i = 0; i &lt; A.length; i++) {
            if (element !== A[i]) {
                var distance = Math.abs(element - A[i]);
                if (distance % 3 === 0) {
                    Z.push(A[i]);
                }
            }

        }
        if(Z.length&gt;biggestArray.length){
            biggestArray=Z;
        }
    });
    console.log("biggest Array length:"+biggestArray.length);
    console.log("points: "+biggestArray);


For each element from entry array i check its distance with any other element. If it is %3 then I add this point do result array. After each outer loop iteration i check if current result is bigger than last. If yes then I store new one. I receive correct data at least for array given to me. 

This task seems to be quite easy ( am I not seeing something?)
Also it will do n^2 operations. Is there any nice way to tone it down?
I would think that on each iteration you could remove the elements that you include in Z, i.e. your first iteration will return [-3, 0] so you could remove them from A, they will never match anything else. My solution would be:



let input      = [-3, -2, 1, 0, 8, 7, 1];
let result     = [];
let workingSet = input;

while (workingSet.length) {
  let first    = workingSet[0];
  let elements = [];
  let unused   = [];
  
  workingSet.forEach( value =&gt; {
    if ((value - first) % 3 == 0) {
      elements.push(value);
    } else {
      unused.push(value);
    }  
  });
  
  console.log('elements', elements);
  if (elements.length &gt; result.length)
    result = elements;
  workingSet = unused;
}  
   
console.log('result', result);




One note is that you mix old style JS code like var with ES6 features like =&gt;. I would expect code to either stick to using the older JS style for maximum browser compatibility or to stick to the newer JS style consistently.