Return to Revisions

2 of 6

Make code runnable

edit approved Apr 27, 2023 at 18:29

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

you can distribute the m to get

(5) (b mod m) - (a mod m) == 0

by adding (a mod m) to both sides you get

(6) (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])

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 doint it that way, but it should be fine to just remove the typings...

answered Apr 27, 2023 at 18:05

slepic

5.6k
2
9
27

default