Hamming Distance — LeetCode 461 Python Solution
EasyBit Manipulation
- Problem
- #461
- Pattern
- Bit Manipulation
- Reading time
- 2 min
- Source
- leetcode.com
The problem
The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, return the Hamming distance between them.
Example
- Input
- x = 1, y = 4
- Output
- 2
- Explanation
- 1 (0 0 0 1)
Python solution
Python
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
return (x ^ y).bit_count()Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(1) auxiliary |
Pattern: Bit Manipulation
Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 461. Hamming Distance is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Bit Manipulation.
The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 461. Hamming Distance?
- LeetCode 461. Hamming Distance is rated Easy on LeetCode.
- What is the time complexity of LeetCode 461. Hamming Distance?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 461. Hamming Distance?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 461. Hamming Distance cover?
- LeetCode 461. Hamming Distance is tagged Bit Manipulation on LeetCode.