Hamming Distance - Java O(1)

  • 1

    The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

    Given two integers x and y, calculate the Hamming distance.

    0 ≤ x, y < 231.


    Input: x = 1, y = 4

    Output: 2

    1 (0 0 0 1)
    4 (0 1 0 0)
    ↑ ↑

    The above arrows point to positions where the corresponding bits are different.


    class Solution {
        public int hammingDistance(int x, int y) {  
           return Integer.bitCount(x^y);

    Time Complexity: O(1)
    This solution uses builtin functions to first perform the XoR operation which is in constant time O(1) and count the number of 1s from the integer. This bitCount method also runs in constant time.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.