Leetcode 문제 질문

원래 문제가 뭔지 모르겠지만 그냥 추측컨대, 모든 pair를 찾아서 각 pair의 distance를 sum 하는게 아니라 각 bit 별로 "다른" 페어들의 갯수를 구해서 최적화 한 것 같은데요. 예를 들어 0이 2개고 1이 4개면 디스턴스의 총 합을 6*5/2 페어를 돌아가며 계산해서 세는게 아니라 0 갯수 * 1 갯수 = 8 이런식으로 계산한 것 같습니다.

문제에서 요구하는 것은 n개의 수를 입력 받아서 nums[0], nums[1], ..., nums[n-1]의 binary representation으로 나타냈을 때 pairwise hamming distance를 구해서 총합을 구하는 것인데, 이 요구대로 정직하게 (i = 0 .. n-2 & j = i+1 .. n-1) 2중 for-loop을 이용하여 hamming_dist(nums[i], nums[j]) 를 더하는 방법이 있을테구요

본문에 적어주신 방법은 그보다 효율적으로 답을 구하는 방법입니다.

첫 번째 for loop 보시면 i를 [0, 31]까지 올리면서 입력으로 받은 n개의 정수 (nums)의 i번째 bit이 set 된것과 unset된 것의 개수를 셉니다.

정확히는 count variable에 i번째 bit이 set된 개수 (이 값은 0 이상 n이하 이겠죠)가 될거고, 

각 i에 대해서 count * (n - count)가 나타내는 quantity는 우리가 최종적으로 구하고 싶은 전체 hamming distance 총합을 

0번째, 1번째, .., 31번째 비트로 쪼개서 구해서 더했다고 생각하면 됩니다.

예를 들면 문제에서 나온대로 4, 14, 2의 경우 2진수로 나타내면 (편의상 4개씩 끊어서 적었습니다)

0000 0000 0000 0000 0000 0000 0000 0100 = 4

이게 수학 문젠가요? 언제 배우는건가요?  궁금해서 여쭤 봅니다

문제가 숫자들 간의 hamming distance의 총 합을 구하는 것인가봅니다. hamming distance면 bit이 다를 때 1씩 올라가는 건데, 각 bit에 대해서 그 bit이 0인 숫자들의 갯수 (n - count)랑 1인 숫자들의 갯수 (count)들 간에만 거리가 1 생기니까 그 bit에서 생기는 거리의 총 합이 count * (n - count)가 되네요. (count) 숫자들이랑 (n - count) 숫자들로 pair를 만들 수 있는 방법의 수라고 생각하시면 될 것 같습니다.

#이과망했으면