Bit Manipulation

You are given a **non-empty** array of integers `nums`. Every integer appears twice except for one. Return the integer that appears only once. You must implement a solution with $O(n)$ runtime complexity and use only $O(1)$ extra space. **Example 1:** ```java Input: nums = [3,2,3] Output: 2 ``` **Example 2:** ```java Input: nums = [7,6,6,7,8] Output: 8 ``` **Constraints:** * `1 <= nums.length <= 10000` * `-10000 <= nums[i] <= 10000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(1)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force approach would iterate through the array, checking each element using a nested loop. If a duplicate is found, we continue to the next element; otherwise, the current element is the required number. This results in an <code>O(n^2)</code> solution. Can you think of a better way? Maybe a data structure can help detect duplicates efficiently. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We use a hash set, iterating through the array and adding elements that are not in the set while removing those that are already present. After the iteration, the required number remains in the hash set. This results in an <code>O(n)</code> space solution. Can you further optimize it? Maybe a bitwise operator could be useful here. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> Think about the bitwise XOR <code>("^")</code>. What is the result when two identical numbers are XORed? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> When two identical numbers are XORed, they cancel out, resulting in zero. Since every number appears twice except for one, the XOR of the entire array gives the number that appears only once. </p> </details>

You are given an unsigned integer `n`. Return the number of `1` bits in its binary representation. You may assume `n` is a non-negative integer which fits within 32-bits. **Example 1:** ```java Input: n = 00000000000000000000000000010111 Output: 4 ``` **Example 2:** ```java Input: n = 01111111111111111111111111111101 Output: 30 ``` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(1)</code> time and <code>O(1)</code> space. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> The given integer is a <code>32</code>-bit integer. Can you think of using bitwise operators to iterate through its bits? Maybe you should consider iterating <code>32</code> times. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We iterate <code>32</code> times <code>(0 to 31)</code> using index <code>i</code>. The expression <code>(1 << i)</code> creates a bitmask with a set bit at the <code>i</code>-th position. How can you check whether the <code>i</code>-th bit is set in the given number? Maybe you should consider using the bitwise-AND <code>("&")</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> Since the mask has a set bit at the <code>i</code>-th position and all <code>0</code>s elsewhere, we can perform a bitwise-AND with <code>n</code>. If <code>n</code> has a set bit at the <code>i</code>-th position, the result is positive; otherwise, it is <code>0</code>. We increment the global count if the result is positive and return it after the iteration. </p> </details>

Given an integer `n`, count the number of `1`'s in the binary representation of every number in the range `[0, n]`. Return an array `output` where `output[i]` is the number of `1`'s in the binary representation of `i`. **Example 1:** ```java Input: n = 4 Output: [0,1,1,2,1] ``` Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 **Constraints:** * `0 <= n <= 1000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the given integer. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A straightforward approach would be to iterate from <code>0</code> to <code>n</code> using <code>i</code>, and for each <code>i</code>, iterate through its bits to count the number of set bits. This would result in an <code>O(n \log n)</code> approach. Can you think of a better way? Maybe you should try identifying a pattern by observing the bitwise representation of consecutive numbers. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> For example, to compute set bits for <code>7</code>, add <code>1</code> to the count of set bits in <code>3</code>, which was previously computed by adding <code>1</code> to the count of set bits in <code>1</code>. Observing the pattern, for numbers less than <code>4</code>, add <code>1</code> to the count from two positions before. For numbers less than <code>8</code>, add <code>1</code> to the count from four positions before. Can you derive a dynamic programming relation from this? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We find an offset for the current number based on the number before <code>offset</code> positions. The dynamic programming relation is <code>dp[i] = 1 + dp[i - offset]</code>, where <code>dp[i]</code> represents the number of set bits in <code>i</code>. The offset starts at <code>1</code> and updates when encountering a power of <code>2</code>. To simplify the power of <code>2</code> check, if <code>offset * 2</code> equals the current number, we update <code>offset</code> to the current number. </p> </details>

Given a 32-bit unsigned integer `n`, reverse the bits of the binary representation of `n` and return the result. **Example 1:** ```java Input: n = 00000000000000000000000000010101 Output: 2818572288 (10101000000000000000000000000000) ``` Explanation: Reversing `00000000000000000000000000010101`, which represents the unsigned integer `21`, gives us `10101000000000000000000000000000` which represents the unsigned integer `2818572288`. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(1)</code> time and <code>O(1)</code> space. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Given a 32-bit integer, what is the position of bit <code>i</code> after reversing the bits? Maybe you should observe the bit positions before and after reversal to find a pattern. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> After reversing the bits, the bit at position <code>i</code> moves to position <code>31 - i</code>. Can you use this observation to construct the reversed number efficiently? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We initialize <code>res</code> to <code>0</code> and iterate through the bits of the given integer <code>n</code>. We extract the bit at the <code>i</code>-th position using <code>((n >> i) & 1)</code>. If it is <code>1</code>, we set the corresponding bit in <code>res</code> at position <code>(31 - i)</code> using <code>(res |= (1 << (31 - i)))</code>. </p> </details>

Given an array `nums` containing `n` integers in the range `[0, n]` without any duplicates, return the single number in the range that is missing from `nums`. **Follow-up**: Could you implement a solution using only `O(1)` extra space complexity and `O(n)` runtime complexity? **Example 1:** ```java Input: nums = [1,2,3] Output: 0 ``` Explanation: Since there are 3 numbers, the range is [0,3]. The missing number is 0 since it does not appear in nums. **Example 2:** ```java Input: nums = [0,2] Output: 1 ``` **Constraints:** * `1 <= nums.length <= 1000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(1)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force approach would iterate through the range of numbers from <code>0</code> to <code>n</code>, checking if each number is present in the given array. If a number is missing, it is returned. This results in an <code>O(n^2)</code> solution. Can you think of a better way? Maybe a data structure could help optimize this process. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use a hash set by inserting the given array elements into it. Then, we iterate through the range of numbers from <code>0</code> to <code>n</code> and use the hash set for <code>O(1)</code> lookups to find the missing number. Can you think of a way to further optimize this? Maybe a bitwise operator could be useful. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can use bitwise XOR. When two identical numbers are XORed, the result is <code>0</code>. Using this property, we can efficiently find the missing number. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We first compute the bitwise XOR of numbers from <code>0</code> to <code>n</code>. Then, we iterate through the array and XOR its elements as well. The missing number remains in the final XOR result since all other numbers appear twice—once in the range and once in the array—while the missing number is XORed only once. </p> </details>

Given two integers `a` and `b`, return the sum of the two integers without using the `+` and `-` operators. **Example 1:** ```java Input: a = 1, b = 1 Output: 2 ``` **Example 2:** ```java Input: a = 4, b = 7 Output: 11 ``` **Constraints:** * `-1000 <= a, b <= 1000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(1)</code> time and <code>O(1)</code> space. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force approach would use the addition operator. Can you think of a way to perform addition without using it? Maybe you should consider solving this using bit manipulation. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use the bitwise XOR operator to perform addition. If both <code>a</code> and <code>b</code> have <code>1</code> at the same bit position, the sum at that position is <code>0</code>, and a carry of <code>1</code> is generated. If the bits are different, the sum at that position is <code>1</code>. Additionally, we account for the carry from the previous step in the next iteration. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We iterate bit by bit from <code>0</code> to <code>31</code> since the given integers are 32-bit. We track the carry, initially set to <code>0</code>, and initialize the result as <code>res</code>. During iteration, the XOR of the bits at the <code>i</code>-th position of both integers and the carry determines the current bit of <code>res</code>. How can you handle negative numbers? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> To handle negative numbers, if the final result exceeds the maximum positive 32-bit integer, it means the number should be negative. We adjust it using bitwise operations: flipping the bits with <code>res ^ ((2 ^ 32) - 1)</code> and applying <code>~</code> to restore the correct two’s complement representation. This ensures the result correctly represents signed 32-bit integers. </p> </details>

You are given a signed 32-bit integer `x`. Return `x` after reversing each of its digits. After reversing, if `x` goes outside the signed 32-bit integer range `[-2^31, 2^31 - 1]`, then return `0` instead. Solve the problem without using integers that are outside the signed 32-bit integer range. **Example 1:** ```java Input: x = 1234 Output: 4321 ``` **Example 2:** ```java Input: x = -1234 Output: -4321 ``` **Example 3:** ```java Input: x = 1234236467 Output: 0 ``` **Constraints:** * `-2^31 <= x <= 2^31 - 1` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(1)</code> time and <code>O(1)</code> space. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A straightforward approach would be to convert the given integer to a string, reverse it, convert it back to an integer using a long type, and return 0 if the result exceeds the integer range. Can you think of a better way? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We initially declare the result <code>res</code> as an <code>int</code> with a value of <code>0</code>. We iterate through the given integer, extracting digits one by one. Before appending a digit to <code>res</code>, we consider multiple cases. Can you determine them? Maybe you should think about overflow. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> Let <code>MAX</code> be the maximum positive integer and <code>MIN</code> be the minimum negative integer. We iterate through each digit and check for overflow before updating <code>res</code>. If <code>res > MAX / 10</code> or <code>res < MIN / 10</code>, return <code>0</code>. If <code>res == MAX / 10</code> and the current digit is greater than <code>MAX % 10</code>, return <code>0</code>. If <code>res == MIN / 10</code> and the current digit is less than <code>MIN % 10</code>, return <code>0</code>. Otherwise, append the digit to <code>res</code> and continue. </p> </details>