O(N) - time complexity

function divisibleSumPairs(k, ar) {
  // Write your code here
  const map = new Map();
  let noOfPair = 0;

  for (let i = 0; i < ar.length; i++) {
    const remainder = ar[i] % k;
    let diff = k - remainder;
    if (diff === k) {
			// means ar[i] is a divisible
      diff = 0;
    }

    if (map.has(diff)) {
      noOfPair += map.get(diff);
    }
    if (map.has(remainder)) {
      let count = map.get(remainder);
      map.set(remainder, count + 1);
    } else {
      map.set(remainder, 1);
    }
  }

  return noOfPair;
}

Here is my solution

i tried lots of iterations before arriving at this solution, some of the problems this question poses includes

1) the array could contain multiples of k, for example imagine ar=[1, 3, 6, 9, 8] and k=3 , 3, 6, ,9 are all divisible by 3, meaning there is 3 pairs(n(n-1)/2) i.e (3,6), (3, 9), (6,9)whose sum are divisible by k(3)

2) For integers less than k, how much more do they need to become divisible by k i.e 1 in ar needs k-1 to become divisible by k, k-1 = 3 - 1 = 2 meaning if we find 2 in this array and pair it with 1, sum of the pair will be divisible.

3) Now, for items greater than k but not divisible by k, how much more do they need to become divisible by k , we get that using this formula a = bq + r where a is the integer in the array, b is the multiple, q is the divisible(k) and r is the remainder. for example, 8 in ar is greater than k(3) , using the above formulae 8 = 2 * 3 + 2 i.e integer division of 8 // 3 = 2 , we can only find 2 3’s in 8 with remainder 2 . Now, that we know this, this becomes easier for us, we now know that k-2 is the integer needed to pair with 8 in order for 8 to become a divisible of k

Now we had an array with items [23, 21, 27 28] and k=3, if we analyse the array, we find out that, i) all integers in array are greater than k ii) only 21 and 27 are divisible by k. However, when we break this elements down to their remainders using a = bq + r we transform the array to [2, 0, 0, 1], now it’s easy for us to identify the pairs, (0, 0), (2, 1) .