Maximum hamming distances

Array Bit Manipulation Breadth-First Search

49.2% acceptance

Mar 31, 2026

Given an array nums and an integer m, with each element nums[i] satisfying 0 <= nums[i] < 2m, return an array answer. The answer array should be of the same length as nums, where each element answer[i] represents the maximum Hamming distance between nums[i] and any other element nums[j] in the array. The Hamming distance between two binary integers is defined as the number of positions at which the corresponding bits differ (add leading zeroes if needed).

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_hamming_distances(nums: Vec<i32>, m: i32) -> Vec<i32> {
    let mask = (1i32 << m) - 1;
    let size = 1usize << m;
    let mut dist = vec![-1i32; size];
    let mut queue = std::collections::VecDeque::new();
    for &x in &nums {
      if dist[x as usize] == -1 {
        dist[x as usize] = 0;
        queue.push_back(x);
      }
    }
    while let Some(x) = queue.pop_front() {
      for bit in 0..m {
        let y = x ^ (1 << bit);
        if dist[y as usize] == -1 {
          dist[y as usize] = dist[x as usize] + 1;
          queue.push_back(y);
        }
      }
    }
    nums.iter().map(|&x| m - dist[(x ^ mask) as usize]).collect()
  }
}