aboutsummaryrefslogtreecommitdiff
path: root/total_hamming_distance.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-16 12:59:18 -0600
committerJack Sangdahl <[email protected]>2025-03-16 12:59:18 -0600
commit27d29594b7a1211d863f38133148842a3285d9e0 (patch)
tree04afe47aa866d4321a108f6b7c997f7dd8e96fc5 /total_hamming_distance.c
parenta1df0fb34031b85f24094bec64c7660db4479483 (diff)
downloadleetcode-27d29594b7a1211d863f38133148842a3285d9e0.tar.gz
leetcode-27d29594b7a1211d863f38133148842a3285d9e0.zip
477. total hamming distance
Diffstat (limited to 'total_hamming_distance.c')
-rw-r--r--total_hamming_distance.c25
1 files changed, 25 insertions, 0 deletions
diff --git a/total_hamming_distance.c b/total_hamming_distance.c
new file mode 100644
index 0000000..571f417
--- /dev/null
+++ b/total_hamming_distance.c
@@ -0,0 +1,25 @@
+// 477. Total Hamming Distance
+#include "leetcode.h"
+
+/*
+ * 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'.
+ */
+
+int totalHammingDistance(int *nums, int numsSize) {
+ int total = 0;
+ for (int i = 0; i < 32; i++) {
+ int cnt = 0;
+ for (int j = 0; j < numsSize; j++)
+ cnt += (nums[j] >> i) & 1;
+ total += cnt * (numsSize - cnt);
+ }
+ return total;
+}
+
+int main() {
+ int n1[] = {4, 14, 2}, n2[] = {4, 14, 4};
+ printf("%d\n", totalHammingDistance(n1, ARRAY_SIZE(n1))); // expect: 6
+ printf("%d\n", totalHammingDistance(n2, ARRAY_SIZE(n2))); // expect: 4
+}