Count matching pairs (modular equality)

Question

Problem

Given an array of natural numbers a. Find the number of such pairs of elements (a_i, a_j), where abs(a_i − a_j) mod 200 == 0 and i < j

Solution

I came up with this solution:

// n - the length of numbers array
// numbers - the array of natural numbers
function getNumberOfGoodPairs(n, numbers) { 
 let count = 0;
 const remainders = new Map();
 
 for (const num of numbers) {
 const remainder = num % 100;
 const modifiedNum = (num - remainder) / 100;
 
 if (remainders.has(remainder)) {
 const nums = remainders.get(remainder);
 
 for (const num of nums) {
 if (Math.abs(num - modifiedNum) % 2 === 0) ++count;
 }
 
 nums.push(modifiedNum);
 } else {
 remainders.set(remainder, [modifiedNum]);
 }
 }
 
 return count;
}

Notations

• for (const arrayElement of array) - get elements from the array one by one and put this element into arrayElement. It is same as:

  for (let i = 0; i < array.length; ++i) {
   const arrayElement = array[i];
  }
  

• new Map() - is dictionary

• % - is mod

• array.push(el) - add el to the end of array

• remainders.get(remainder) - returns the array of numbers which remainder is equal to remainder when dividing by 100

• remainders.set(remainder, [modifiedNum]) - add to dictionary new key remainder and value [modifiedNum]. [modifiedNum] - a dynamic array with one element modifiedNum

If I'm right the time complexity in worst case is O(n2).

Please help me to optimize this algorithm.

• EzioMercer: @greybeard I want to learn an algorithm regardless of a specific programming language
• greybeard: The way to speed up the procedure sketched would be to leave out what's mind boggling about it anyway. Review the idea of grouping inputs (modified or not) by remainder, and the need to compare the modulus of absolute differences. This isn't algorithm review. This is code review, I expect code to review to be working as is with a contemporary run-time environment.
• slepic: it's a working javascript code, guys. I added the tag and removed the mention about pseudocode. Hopefully that makes the post ok.

Answer 1

With a bit of algebra you can show that

(1) abs(a_i − a_j) mod m == 0, m > 1

can be written as

(2) (a_i − a_j) mod m == 0 if a_i >= a_j
(3) (a_j − a_i) mod m == 0 if a_i <= a_j

on both cases it is the same as saying

(4) (b − a) mod m == 0 if b >= a

Let's define the inverse of mod m as invmod_m

(5) invmod_m(x mod m) = x
(6) invmod_m(x) mod m = x

by applying the mod inverse we get infinitely many equations, but that' ok, we can deal with them all at once

(7) invmod_m((b − a) mod m) == invmod_m(0)

from (5) we can simplify the left side

(8) b - a == invmod_m(0)

now we can add a to both sides

(9) b == a + invmod_m(0)

and do mod m of both sides again

(10) b mod m == (a + invmod_m(0)) mod m

and distribute the m on right side

(11) b mod m == a mod m + invmod_m(0) mod m

from (6) we see that invmod_m(0) mod m is zero so we have

(12) (b mod m) == (a mod m)

And so you see, regardless of what the m is, two numbers are a good pair if and only if their remainder mod m is the same.

So an algorithm with O(n) time complexity is

• build histogram R of remainders mod m
• sum the number of good pairs (R[r] * (R[r] - 1) / 2) for each remainder r in R (with occurence R[r] > 0)

type Solution = (numbers: number[], m: number) => number
const naiveSolution: Solution = (numbers, m) => {
 let count = 0
 for (let j = 1; j < numbers.length; ++j) {
 for (let i = 0; i < j; ++i) {
 const ai = numbers[i]
 const aj = numbers[j]
 if (Math.abs(ai - aj) % m === 0) {
 ++count
 }
 }
 }
 return count
}
const ezioSolution: Solution = (numbers, m) => { 
 let count = 0;
 const remainders = new Map();
 
 for (const num of numbers) {
 const remainder = num % 100;
 const modifiedNum = (num - remainder) / 100;
 
 if (remainders.has(remainder)) {
 const nums = remainders.get(remainder);
 
 for (const num of nums) {
 if (Math.abs(num - modifiedNum) % 2 === 0) ++count;
 }
 
 nums.push(modifiedNum);
 } else {
 remainders.set(remainder, [modifiedNum]);
 }
 }
 
 return count;
}
const slepicSolution: Solution = (numbers, m) => {
 const remainders = new Map/*<number, number>*/()
 for (let j = 0; j < numbers.length; ++j) {
 const aj = numbers[j]
 const r = aj % m
 remainders.set(r, remainders.has(r) ? remainders.get(r) + 1 : 1)
 }
 
 let total = 0
 remainders.forEach((count) => {
 total += count * (count - 1) / 2
 })
 return total
}
const solutionTestSuite = (name: string, solution: Solution): number => {
 let errors = 0
 const solutionTest = (expected:number, numbers: number[], m: number) => {
 const actual = solution(numbers, m)
 if (expected !== actual) {
 console.warn(`${name} returned ${actual} instead of ${expected}`, numbers, `(mod ${m})`)
 ++errors
 } else {
 console.info(`${name} returned ${actual} as expected`, numbers, `(mod ${m})`)
 }
 }
 
 console.info(`${name} starting`)
 
 const start = performance.now()
 solutionTest(0, [], 200)
 solutionTest(0, [0], 200)
 solutionTest(1, [0, 0], 200)
 solutionTest(1, [105, 505], 200)
 solutionTest(3, [205, 605, 5], 200)
 solutionTest(4, [205, 10, 605, 5, 1010], 200)
 const stop = performance.now()
 
 const time = `in ${stop - start} ms`
 
 if (errors > 0) {
 console.warn(`${name} gor ${errors} errors ${time}`)
 } else {
 console.info(`${name} OK ${time}`)
 }
 
 return errors
}
const testAll = () => {
 let errors = 0
 
 errors += solutionTestSuite('naive', naiveSolution)
 errors += solutionTestSuite('ezio', ezioSolution)
 errors += solutionTestSuite('slepic', slepicSolution)
 
 if (errors > 0) {
 console.warn(`${errors} errors in total`)
 } else {
 console.info(`ALL OK`)
 }
}
testAll()

Sorry for the typescript; I felt more confident doing it that way, but it should be fine to just remove the typings...

• EzioMercer: Thank you! Interesting solution. You can also check my answer with only one for loop :)
• slepic: @EzioMercer Yeah,I realized i could do it directly without the next loop, but I had it already written and was lazy for refactor so I left that for you :) Anyway the idea is the very same.

Answer 2

I found a solution with one for loop (rewrited in JS):

The time complexity is O(n)

Algorithm:

• We create an array with the size of 200 and fill it with zeros

• Instead of calculating the remainders dividing by 100 we calculate the remainders dividing by 200 - remainder = num % 200

• This remainder is the place in our prepared array where we will count the number of numbers with the same remainders

• Then we increase count by the value of remainders[remainder] and after this we increase the value of remainders[remainder] by 1

• When we reach out the end of numbers array we already have a total count of pairs

function getNumberOfGoodPairs(n, numbers) { 
 let count = 0;
 const remainders = Array(200).fill(0);
 
 for (const num of numbers) {
 const remainder = num % 200;
 
 count += remainders[remainder];
 
 ++remainders[remainder];
 }
 
 return count;
}

• pacmaninbw: Not really a good answer, good answers are supposed to make observations about the original code.
• EzioMercer: @pacmaninbw You are right! I will add this information ASAP