[leetcode] 477. Total Hamming Distance

문제

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given an integer array nums, return the sum of Hamming distances between all the pairs of the integers in nums.

• Example 1:

  	- Input: nums = [4,14,2]
  	- Output: 6

• Example 2:

  	- Input: nums = [4,14,4]
  	- Output: 4

제한사항

1 <= nums.length <= 104
0 <= nums[i] <= 109
The answer for the given input will fit in a 32-bit integer.

풀이1.

function solution(nums) {
  let result = 0;
  const array = permutation(nums, 2);
  console.log(array);
  for (let i = 0; i < array.length; i++) {
    const [a, b] = array[i];
    result += HammingDistance(a, b);
    console.log(result);
  }
  return result;
}

처음 개념은 순열을 이용해서, 두개씩 선택하는 모든 경우의 수를 구한뒤, HammingDistance를 하나씩 구하기로 계획했다.

function permutation(arr, n) {
  if (n == 1) return arr.map((v) => [v]);
  let result = [];
  arr.forEach((fixed, idx, arr) => {
    const rest = arr.slice(idx + 1);
    const combine = permutation(rest, n - 1);
    const combins = combine.map((v) => [fixed, ...v]);
    result.push(...combins);
  });

  return result;
}

재귀함수를 이용해서 순열을 구했다.

function HammingDistance(a, b) {
  const aArray = a.toString(2).split('');
  const bArray = b.toString(2).split('');

  const length = aArray.length < bArray.length ? bArray.length : aArray.length;
  let count = 0;
  for (let i = 0; i < length; i++) {
    const aResult = aArray[aArray.length - 1 - i] || 0;
    const bResult = bArray[bArray.length - 1 - i] || 0;
    if (aResult !== bResult) count++;
  }
  return count;
}

toString(2)을 이용하여, 이진법으로 표현하고 다른 비트의 수를 구했다.

이 때 [6,1,8,6,8]이라는 반례가 있었는데 왜 반례가 되는지를 이해하지 못했다...

풀이2.

function solution(nums) {
  var tot = 0;
  for (var i = 0; i < 32; i++) {
    var count = 0;
    for (var j = 0; j < nums.length; j++) {
      count += (nums[j] >> i) & 1;
    }

    tot += count * (nums.length - count);
    
  }
  return tot;
}

아예 다른 방식으로 접근하게 되었는데, 연산자 >>을 이용하여, 각 수의 자리수 마다 1인것의 개수와 0인 것의 개수를 구해서 count * (nums.lenth -count)를 구하고 그 합을 통해 HammingDistance의 합을 구할 수 있었다.

추가사항

풀이 1의 경우 제일 단순하고 문제만 해석한 경우이고, 풀이 2는 창의적으로 한번 더 생각해서 풀이한 경우 이다. 풀이 1이 왜 안되는지 더 생각해 봐야겠으며, 풀이 2와 같은 경우를 생각할 수 있도록 노력하자