Count identical pairs in an array with an efficient algorithm
Problem statement : a[]
is an array of numbers n
, count no. identical pairs in the array, such that 0 <= p < q < n
p, q are the indices of the pair.
a[3,5,6,3,3,5]
n=6
There are no identical pairs here: 4, which are
(0,3), (0,4), (3,4), (1,5)
AND not or , since this violates the condition . (2,2)
(4,3)
p < q
Solution 1:
function getIdenticalPairs(a, n){
var identicalPairs = 0;
for(var i=0;i<n-1;i++){
for(var j=i+1;j<n;j++){
if(a[i]===a[j]){
identicalPairs +=1;
}
}
}
return identicalPairs;
}
This code works fine, but it seems to have O (n 2 ) time complexity .
the second solution i tried is
Solution 2 : Using the combination formula, Identical pairs nos, n c r
var identicalPairs = 0;
function getIdenticalPairs(a, n){
var map = {};
for(var i=0;i<n;i++){
if(map[a[i]]){
map[a[i]].push(i);
}else{
map[a[i]] = [i];
}
}
Object.keys(map).forEach(function(v,i){
var occurances = map[v].length;
if(occurances > 1){
var nFact = factorial(occurances);
var nrFact = factorial(occurances - 2);
var rFact = factorial(2);
//console.log(occurances , nFact, nrFact, rFact);
identicalPairs += nFact/(nrFact*rFact)
}
})
function factorial(n) {
if(n<=1) return 1;
var ret = 1;
for(var i=2;i<=n;++i)
ret *= i;
return ret;
}
return identicalPairs;
}
Q.1 I'm not sure, but solution 2 has time complexity O (n + n + n) = O (n) or O (n 2 )
Q.2 if its not O (n), then is there a better solution, possibly O (nlogn) time complexity, whether in Javascript
or Java
?
source to share
Push indices into an array:
Integer[] indices = new Integer[a.length];
for (int i = 0; i < a.length; ++i) indices[i] = i;
Detach the indices according to the value of the corresponding element in a
:
Arrays.sort(indices, (i, j) -> Integer.compare(a[i], a[j]));
Then just pull out the index blocks with equal matching elements from indices
:
int count = 0;
int i = 0;
while (i < indices.length) {
int start = i;
while (i < indices.length && a[indices[i]] == a[indices[start]]) {
++i;
}
// This is the number of indices whose corresponding values are equal.
int thisCount = i - start;
// This is the number of pairs you can make from
// thisCount indices.
int numPairs = thisCount * (thisCount - 1) / 2;
count += numPairs;
}
This approach has a total complexity of O (n log n) due to sorting. The group count is linear.
source to share
Count the number of occurrences of each element in the array:
Map<Integer, Long> occurrences =
IntStream.of(a).boxed().collect(
Collectors.groupingBy(Function.identity(), Collectors.counting()));
Then just count the number of pairs you can do for each key:
long count =
occurrences.values().stream()
.mapToLong(e -> e * (e - 1) / 2)
.sum();
This approach has a total complexity of O (n), since the insertion into the hashmap is constant time (and this is done n times) and the iteration over the map values is linear.
source to share
You can count the values and get the possible number of combinations.
-
factorial
is a function to get the factorial of a number and -
count
contains the number of elements in the array.
The factorial is needed to get all the combinations of n, and you only need half to count, because of the given rule that the indices must increase.
function getCount(array) {
var factorial = n => +!~-n || n * factorial(n - 1),
count = array.reduce(
(c, v) => (c[v] = (c[v] || 0) + 1, c),
Object.create(null)
);
return Object
.keys(count)
.filter(k => count[k] > 1)
.reduce((r, k) => r + factorial(count[k]) / 2, 0);
}
console.log(getCount([3, 5, 6, 3, 3, 5]));
source to share
This is a typical dynamic programming problem. You can do this very efficiently;
function indicesOfIdentical(a){
return a.reduce((h,e,i) => (h[0][e] ? (h[1] = h[1].concat(h[0][e].map(n => [n,i])), h[0][e].push(i), h)
: h[0][e] = [i], h), [{},[]])[1];
}
var arr = [0,3,5,6,3,3,5,0],
result = indicesOfIdentical(arr);
console.log(JSON.stringify(result));
console.log("Test for 40 random items array of 0-9");
arr = Array(40).fill().map( _ => ~~(Math.random()*10));
result = indicesOfIdentical(arr);
console.log(JSON.stringify(arr));
console.log(JSON.stringify(result));
source to share
Here is my solution using C code: expected time complexity is O (nlogn)
First sort array A in descending order
#include <stdlib.h>
int compr(const void *a, const void *b)
{
return (*(int*)a - *(int*)b);
}
int getIdenticalPairs(int *A, int n)
{
qsort(A, n, sizeof(int), compr);
int sumPair = 0;
int cnt = 0;
//if array size equal or less than 1, return 0
if (n <=1) return 0;
for(int i = 1; i < n; i++)
{
if(A[i-1] == A[i])
{
//add number of identical pairs so far
cnt++;
sumPair += cnt;
}
else
{
cnt = 0;
}
}
return sumPair;
}
source to share
function GetIdenticalPositionPairs(inputArray)
{
var numberCount = {};
for(var i=0;i<inputArray.length-1;i++)
{
for(var j=i+1;j<inputArray.length;j++)
{
if(inputArray[i] == inputArray[j]){
if(numberCount[inputArray[i]] == undefined)
numberCount[inputArray[i]] = 1;
else
numberCount[inputArray[i]] += 1;
console.log(i + "--> (" + i + ","+ j +")");
}
}
}
console.log(numberCount);
}
source to share