Return to Question

Summarise the purpose, not the concerns, in the title

Source Link

edited Apr 28, 2023 at 8:41

Toby Speight

edited Apr 28, 2023 at 8:41

Toby Speight

87.5k
14
104
323

How to find count of Count matching pairs efficiently than O(n^2modular equality)

Problem

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:

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(n^2)O(n2).

Please help me to optimize this algorithm.

How to find count of pairs efficiently than O(n^2)

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

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(n^2)

Please help me to optimize this algorithm.

Count matching pairs (modular equality)

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.

Became Hot Network Question

occurred Apr 27, 2023 at 23:38

deleted 63 characters in body; edited tags

Source Link

edited Apr 27, 2023 at 18:07

slepic

edited Apr 27, 2023 at 18:07

slepic

5.6k
2
9
27

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

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(n^2)

Please help me to optimize this algorithm. You can provide the pseudo code to explain the your algorithm

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

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(n^2)

Please help me to optimize this algorithm. You can provide the pseudo code to explain the your algorithm

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

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(n^2)

Please help me to optimize this algorithm.

added 5 characters in body

Source Link

edited Apr 27, 2023 at 16:06

EzioMercer

edited Apr 27, 2023 at 16:06

EzioMercer

ProblemProblem: 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

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 reminderremainder is equal to remainder when dividing by 100
remainders.set(remainder, [modifiedNum]) - add to dictionary new key reminderremainder and value [modifiedNum]. [modifiedNum] - a dynamic array with one element modifiedNum

If I'm right the time complexity in worst case is O(n^2)

Please help me to optimize this algorithm. You can provide the pseudo code to explain the your algorithm

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

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 reminder is equal to remainder when dividing by 100
remainders.set(remainder, [modifiedNum]) - add to dictionary new key reminder and value [modifiedNum]. [modifiedNum] - a dynamic array with one element modifiedNum

If I'm right the time complexity in worst case is O(n^2)

Please help me to optimize this algorithm. You can provide the pseudo code to explain the your algorithm

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

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