What is the time and space complexity of Hamming Distance?

Time complexity: O(1). Space complexity: O(1).

Hamming Distance

Easy

Concept

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Hamming Distance

Approach

XOR the two numbers to get a value with 1s at every bit position where they differ. Count the set bits in the XOR result using Brian Kernighan's algorithm (n & (n - 1) to clear the lowest set bit each iteration).

Complexity Analysis

Time: O(1)
Space: O(1)

Pattern

XOR Pattern

Why It Works

XOR produces 1 exactly where bits differ, so counting 1s in the XOR result directly gives the number of differing positions (Hamming distance).

Updated Mar 2026