0
\$\begingroup\$

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 => {
        Z=[];
        Z.push(element);
        for (i = 0; i < 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>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?

\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

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 => {
    if ((value - first) % 3 == 0) {
      elements.push(value);
    } else {
      unused.push(value);
    }  
  });
  
  console.log('elements', elements);
  if (elements.length > 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 =>. 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.

\$\endgroup\$
1
\$\begingroup\$

The difference of numbers will be a multiple of N if and only if their value mod N is the same. So you can simply group the numbers based on their value mod N, and take the biggest one. This only needs a single pass on the input, which is O(n) complexity instead of O(n2).

console.log(largestSubsetWithDistance([-3, -2, 1, 0, 8, 7, 1], 3));

function largestSubsetWithDistance(nums, diff) {
  let result = [];
  for(let i = 0; i < nums.length; i++) {
    let mod = nums[i] % diff;
    if(mod < 0) mod += diff; //Brings negative numbers into the 0 to N-1 range
    if(!result[mod]) result[mod] = [];
    result[mod].push(nums[i]);
  }
  return result.reduce((a,c) => c.length > a.length ? c : a, []);
}

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.