LeetCode 1009. Complement of Base 10 Integer Solution in Java, C++, Python & More | Explanation + Code

Description

The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation.

• For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2.

Given an integer n, return its complement.

 

Example 1:

Input: n = 5
Output: 2
Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.

Example 2:

Input: n = 7
Output: 0
Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.

Example 3:

Input: n = 10
Output: 5
Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.

 

Constraints:

• 0 <= n < 109

 

Note: This question is the same as 476: https://leetcode.com/problems/number-complement/

Solutions

Solution 1: Bit Manipulation

First, we check if n is 0. If it is, we return 1.

Next, we define two variables ans and i, both initialized to 0. Then we iterate through n. In each iteration, we set the i-th bit of ans to the inverse of the i-th bit of n, increment i by 1, and right shift n by 1.

Finally, we return ans.

The time complexity is O(log n), where n is the given decimal number. The space complexity is O(1).

PythonJavaC++GoTypeScriptRustC#

class Solution: def bitwiseComplement(self, n: int) -> int: if n == 0: return 1 ans = i = 0 while n: ans |= ((n & 1 ^ 1) << i) i += 1 n >>= 1 return ans(code-box)

class Solution { public int bitwiseComplement(int n) { if (n == 0) { return 1; } int ans = 0, i = 0; while (n != 0) { ans |= (n & 1 ^ 1) << (i++); n >>= 1; } return ans; } }(code-box)

class Solution { public: int bitwiseComplement(int n) { if (n == 0) { return 1; } int ans = 0, i = 0; while (n != 0) { ans |= (n & 1 ^ 1) << (i++); n >>= 1; } return ans; } };(code-box)

func bitwiseComplement(n int) (ans int) { if n == 0 { return 1 } for i := 0; n != 0; n >>= 1 { ans |= (n&1 ^ 1) << i i++ } return }(code-box)

function bitwiseComplement(n: number): number { if (n === 0) { return 1; } let ans = 0; for (let i = 0; n; n >>= 1) { ans |= ((n & 1) ^ 1) << i++; } return ans; }(code-box)

impl Solution { pub fn bitwise_complement(mut n: i32) -> i32 { if n == 0 { return 1; } let mut ans = 0; let mut i = 0; while n != 0 { ans |= ((n & 1) ^ 1) << i; n >>= 1; i += 1; } ans } }(code-box)

public class Solution { public int BitwiseComplement(int n) { if (n == 0) { return 1; } int ans = 0, i = 0; while (n != 0) { ans |= ((n & 1) ^ 1) << (i++); n >>= 1; } return ans; } }(code-box)