hackerrank_task.js

function countPairs(arr) {
  // console.log('regular:');
  let cnt = 0;
  for (let i = 0; i < arr.length; ++i) {
    for (let j = i + 1; j < arr.length; ++j) {
      const and = arr[i] & arr[j];
      const log = Math.log(and) / Math.log(2);
      
      if (and !== 0 && Math.round(log) === log) {
        // console.log(arr[i], arr[j]);
        ++cnt;
      }
    }
  }
  return cnt;
}

function countPairs3(arr, obj) {
  // console.log('fast:');
  const quan = new Map();
  obj.quan = quan;
  for (let i = 0; i < arr.length; ++i) {
    if (quan.has(arr[i])) {
      quan.set(arr[i], quan.get(arr[i]) + 1);
    } else {
      quan.set(arr[i], 1);
    }
  }
  // const uniq = arr;//[...quan].map(([n, q]) => n);
  const uniq = [...quan].map(([n, q]) => n);
  
	const cond = (a, b) => {
    const and = a & b
    const log = Math.log(and) / Math.log(2);
    return and !== 0 && Math.round(log) === log;
  }
  
  let cnt = 0;
  for (let i = 0; i < uniq.length; ++i) {
    if (cond(uniq[i], uniq[i])) {
      const q = quan.get(uniq[i]);
      const add = (q * (q-1)) / 2;
      // console.log('single', uniq[i], `+${add}`);
      cnt += add;
    }
    for (let j = i + 1; j < uniq.length; ++j) {
      if (cond(uniq[i], uniq[j])) {
        const qa = quan.get(uniq[i]);
        const qb = quan.get(uniq[j]);
      	// console.log('multi', uniq[i], uniq[j], `+${qa}*${qb}`);
        cnt += qa * qb;
      }
    }
  }
  return cnt;
}

for (let t = 0; t < 100; ++ t) {
  const arr = [];
  for (let i = 0; i < 100; ++i) {
    arr.push(Math.round(Math.random()*1e3));
  }
  const obj = {};
  const [a, b] = [countPairs(arr), countPairs3(arr, obj)];
  console.log(a === b ? '   ' : ' # ', a, b,
		'     ',
		[...obj.quan]
			// .filter(([k, v]) => v > 1)
			.map(([k, v]) => (k+'').repeat(v))
  );
}

  // console.log(countPairs3([1,1,3,3]));


// function countPairs2(arr) {
//   // const a2 = arr.map(num => {
//   //   let bits = 0;
//   //   let n = num;
//   //   while (n > 0) {
//   //     if (n & 1) ++bits;
//   //     n >>= 1;
//   //   }
//   //   return {num, bits}
//   // });
//   // return a2.sort((a, b) => a.bits - b.bits)
//   let cnt = 0;
//   for (let i = 0; i < arr.length; ++i) {
//     for (let j = i + 1; j < arr.length; ++j) {
//       const and = arr[i] & arr[j];
//       const log = Math.log(and) / Math.log(2);
      
//       if (and !== 0 && Math.round(log) === log) {
//         ++cnt;
//       }
//     }
//   }
//   return cnt;
// }

// console.log(JSON.stringify(countPairs2([1,1,3,3]), null, '  '));


// for (let j = 0; j < 100; ++j) {
//   const pairs = [];

//   for (let i = 0; i < j; ++i) {
//     pairs.push(i);
//   }

//   console.log(countPairs(pairs), pairs);
// }