How do you solve the 'Complement of Base 10 Integer' problem?

To solve this problem, use bitwise operations such as XOR to flip the binary digits of the given integer and return its complement.

What is the time complexity of the complement problem?

The time complexity is O(log n), as it depends on the number of bits in the integer n.

What is the space complexity for the complement problem?

The space complexity is O(1) because the solution uses a constant amount of extra space.

How should you handle edge cases in the complement problem?

When n equals 0, return 1 as its complement. Ensure to handle this edge case properly.

What is the pattern in the 'Complement of Base 10 Integer' problem?

The problem follows a bit manipulation pattern where the complement is computed by flipping the binary digits of an integer using bitwise operations.

#1009

Easy

auto_awesome位运算·操作·driven·solution·strategy

LeetCode 题解工作台

十进制整数的反码

每个非负整数 N 都有其二进制表示。例如， 5 可以被表示为二进制 "101" ， 11 可以用二进制 "1011" 表示，依此类推。注意，除 N = 0 外，任何二进制表示中都不含前导零。二进制的反码表示是将每个 1 改为 0 且每个 0 变为 1 。例如，二进制数 "101" 的二进制反码为 …

位运算

题目描述

每个非负整数 N 都有其二进制表示。例如， 5 可以被表示为二进制 "101"，11 可以用二进制 "1011" 表示，依此类推。注意，除 N = 0 外，任何二进制表示中都不含前导零。

二进制的反码表示是将每个 1 改为 0 且每个 0 变为 1。例如，二进制数 "101" 的二进制反码为 "010"。

给你一个十进制数 N，请你返回其二进制表示的反码所对应的十进制整数。

示例 1：

输入：5
输出：2
解释：5 的二进制表示为 "101"，其二进制反码为 "010"，也就是十进制中的 2 。

示例 2：

输入：7
输出：0
解释：7 的二进制表示为 "111"，其二进制反码为 "000"，也就是十进制中的 0 。

示例 3：

输入：10
输出：5
解释：10 的二进制表示为 "1010"，其二进制反码为 "0101"，也就是十进制中的 5 。

提示：

0 <= N < 10^9
本题与 476：https://leetcode.cn/problems/number-complement/ 相同

lightbulb

解题思路

方法一：位运算

我们首先判断 $n$ 是否为 $0$ ，如果是，则返回 $1$ 。

接着我们定义两个变量 $\textit{ans}$ 和 $i$ ，初始化为 $0$ 。然后我们遍历 $n$ ，在每次遍历中，我们将 $\textit{ans}$ 的第 $i$ 位设置为 $n$ 的第 $i$ 位取反，然后将 $i$ 加 $1$ ，并且 $n$ 右移 $1$ 位。

最后返回 $\textit{ans}$ 即可。

时间复杂度 $O(\log n)$ ，其中 $n$ 为给定的十进制数。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for knowledge of bitwise operations and how they are used to manipulate binary representations.
question_mark
Assess understanding of how to handle edge cases such as when n is 0.
question_mark
Evaluate familiarity with time and space complexities related to bit manipulation problems.

warning

常见陷阱

外企场景

error
Failing to account for the edge case where n equals 0, which should return 1.
error
Incorrectly handling large values of n by not properly calculating the bit-length.
error
Overcomplicating the problem by trying unnecessary operations rather than using simple bitwise manipulation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the complement is computed for a list of integers instead of a single value?
arrow_right_alt
Can the solution be optimized for extremely large values of n, such as those near 10^9?
arrow_right_alt
How can you apply this bitwise technique to other problems involving binary operations?

help

常见问题

外企场景

继续练习

#1016 子串能表示从 1 到 N 数字的二进制串 #1018 可被 5 整除的二进制前缀 #996 平方数组的数目