"given an array a of n non-negative integers, count the number of unordered pairs" Code Answer's

given an array a of n non-negative integers, count the number of unordered pairs

By Combative Capuchin on Dec 16, 2020

var debug = 0;

function bruteForce(a){
  let answer = 0;
  for (let i = 0; i < a.length; i++) {
    for (let j = i + 1; j < a.length; j++) {
      let and = a[i] & a[j];
      if ((and & (and - 1)) == 0 && and != 0){
        answer++;
        if (debug)
          console.log(a[i], a[j], a[i].toString(2), a[j].toString(2))
      }
    }
  }
  return answer;
}
  
function f(A, N){
  const n = A.length;
  const hash = {}; 
  const dp = new Array(1 << N);
  
  for (let i=0; i<1<<N; i++){
    dp[i] = new Array(N + 1);
    
    for (let j=0; j<N+1; j++)
      dp[i][j] = new Array(N + 1).fill(0);
  }
      
  for (let i=0; i<n; i++){
    if (hash.hasOwnProperty(A[i]))
      hash[A[i]] = hash[A[i]] + 1;
    else
      hash[A[i]] = 1;
  }
  
  for (let mask=0; mask<1<<N; mask++){
    // j is an index where we fix a 1
    for (let j=0; j<=N; j++){
      if (mask & 1){
        if (j == 0)
          dp[mask][j][0] = hash[mask] || 0;
        else
          dp[mask][j][0] = (hash[mask] || 0) + (hash[mask ^ 1] || 0);
        
      } else {
        dp[mask][j][0] = hash[mask] || 0;
      }
    
      for (let i=1; i<=N; i++){
        if (mask & (1 << i)){
          if (j == i)
            dp[mask][j][i] = dp[mask][j][i-1];
          else
            dp[mask][j][i] = dp[mask][j][i-1] + dp[mask ^ (1 << i)][j][i - 1];
          
        } else {
          dp[mask][j][i] = dp[mask][j][i-1];
        }
      }
    }
  } 
  
  let answer = 0; 
  
  for (let i=0; i<n; i++){
    for (let j=0; j<N; j++)
      if (A[i] & (1 << j))
        answer += dp[((1 << N) - 1) ^ A[i] | (1 << j)][j][N];
  }

  for (let i=0; i<N + 1; i++)
    if (hash[1 << i])
      answer = answer - hash[1 << i];

  return answer / 2;
} 
 
var As = [
  [5, 4, 1, 6], // 4
  [10, 7, 2, 8, 3], // 6
  [2, 3, 4, 5, 6, 7, 8, 9, 10],
  [1, 6, 7, 8, 9]
];

for (let A of As){
  console.log(JSON.stringify(A));
  console.log(`DP, brute force: ${ f(A, 4) }, ${ bruteForce(A) }`);
  console.log('');
}

var numTests = 1000;

for (let i=0; i<numTests; i++){
  const N = 6;
  const A = [];
  const n = 10;
  for (let j=0; j<n; j++){
    const num = Math.floor(Math.random() * (1 << N));
    A.push(num);
  }

  const fA = f(A, N);
  const brute = bruteForce(A);
  
  if (fA != brute){
    console.log('Mismatch:');
    console.log(A);
    console.log(fA, brute);
    console.log('');
  }
}

console.log("Done testing.");

Source: stackoverflow.com

Add Comment