137. Single Number II

MediumBit ManipulationArray
Leetcode Link

Problem Description

Given an array of integers nums, where all elements appear exactly three times except for one unique element that appears only once, the challenge is to identify the unique element. The requirements are to solve this problem with a linear time complexity, meaning the solution should scale proportionally with the size of the input array and use only constant extra space, which implies that the memory used should not scale with input size.

Intuition

To solve this problem efficiently, we need an approach that can process each number and update our tracking variables without saving the entire input or creating additional structures that grow with the input size. Using bitwise operations allows us to operate at the bit level and manipulate individual bits independently of the value or range of the numbers in the array, resulting in a constant extra space usage.

The key understanding in solving this problem is recognizing that if we add up the same bits of all numbers in nums, since all but one number appears three times, the sum of bits in any position must be a multiple of three if the unique number does not contribute a bit in that position.

Here's the breakdown of our algorithm using bitwise logic:

  • We will use two bitwise markers, a and b, to keep track of the counts of bits.
  • We'll iterate through every bit of each number and update a and b to keep track of the counts modulo 3.
  • The rules for updating a and b are determined by the current value of a, b, and the bit value in our current number, c.
  • We use a series of bitwise AND, OR, and XOR operations to maintain the invariant that after processing each bit of each number, b will have a bit set if and only if the corresponding bit in the unique number is set.
  • The final answer is the value of b, as it represents the bits that are unique to the number appearing only once.

The provided solution successfully uses the digital circuit approach with a simulation of a 3-state machine for each bit position. This approach smartly uses bitwise operators to achieve the linear time complexity with constant extra space, as it does not matter how large the numbers are but rather the number of them.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which two pointer technique does Quick Sort use?

Solution Approach

The solution approach outlined involves two main algorithms: bit manipulation and the simulation of a digital logic circuit. This combines computer science fundamentals with ideas from electrical engineering to "count" occurrences of bits.

Let's break down the algorithm:

  • We initialize two integer variables, a and b, which are both initially 0. These variables will represent different states of the count for each bit in our numbers.
  • We use a for loop to iterate over each number c in the given nums array. Each iteration involves processing the current number at the bit level.
  • For each bit position i, we apply bitwise operations to update the state variables a and b. The rules for updating these variables are based on the current state (a, b) and the current bit (c).

We'll be using this logical circuit to simulate the updates:

  • The new value of a (a_i) is determined by the logical expression a_i = (~a & b & c) | (a & ~b & ~c) which corresponds to the truth table conditions for the case when the modulo 3 result is 2.
  • The new value of b (b_i) is determined by b_i = ~a & (b ^ c), which simplifies the updating process.

If we match this against the truth table in the reference, it makes sure that after processing all numbers, b contains the bits set only for the unique number that does not appear three times.

The mentioned truth table can be used to extract the logical expressions for new a_i and new b_i, which are then implemented in the code using bitwise operators AND (&), OR (|), and XOR (^).

It's crucial to realize that the simulation of the logical circuit ensures that with each input (each number in the array), the states a and b are updated in such a way that all bits that should be discarded are reset after being counted three times.

In the end, b will hold the bits that signify the unique number which has not been counted three times, which we return as the result. It's interesting to note that the algorithm is oblivious to the number of bits in the integers involved or the elements' range in the array. It handles the state solely based on the counts per bit, which is why it has a linear runtime and constant space complexity.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement recursion?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Imagine our input array of integers nums is [2, 2, 3, 2]. Here, all elements appear exactly three times except for 3, which appears once. We need to find this unique element.

  1. We start with two variables a and b, both set to 0. These variables track bit counts across the numbers in different states.

  2. We process each number in the array, one bit at a time. Since our array is [2, 2, 3, 2], we'll look at these numbers in binary:

    • 2 in binary is 10
    • 3 in binary is 11

  3. For the first number (which is 2 or 10 in binary):

    • We perform bitwise operations to update a and b.
    • As per our rules, after processing, a remains 0 and b becomes 10 (2 in decimal), since we're seeing 2 for the first time.

  4. We process the second number (also 2):

    • We update a and b again. Now, a becomes 10 and b resets to 0, which tracks that we've seen 2 twice.

  5. The third number is 3 (11 in binary):

    • Updating a and b with 3 changes nothing in a, because the unique bits brought by 3 don't align with bits from 2 which were in a. For b, it absorbs the new unique bits, so b changes to 11.

  6. Finally, we process the last number, another 2:

    • This time, the bits in a align with the incoming bits of 2, and both variables a and b get updated. a will be reset to 0, and b will also be reset to 0 for the bits where 2 contributed, leaving only the bits from the unique number which is 3.

  7. After the final iteration, a is 0, and b is 11 (which is 3 in decimal). This final value of b is the unique element that does not appear three times in the array.

So, we conclude that the unique element in the array [2, 2, 3, 2] is 3.

This walk-through demonstrates that at each iteration, the algorithm correctly updates the state variables a and b by applying the rules from our truth table and logical expressions, leading to the correct identification of the unique number with linear time complexity and constant space usage.

Solution Implementation

1class Solution:
2    def singleNumber(self, nums: list[int]) -> int:
3        # `once` tracks bits that have appeared once
4        # `twice` tracks bits that have appeared twice
5        once = twice = 0
6      
7        for num in nums:
8            # Update `once` and `twice` with current number `num`
9            # `once` should only hold bits that are exactly seen once so far
10            # And `twice` should only hold bits that are exactly seen twice so far
11            # Bits seen three times should be cleared from both `once` and `twice`
12          
13            # First, calculate `once` considering the current number `num`
14            # Use `twice` to mask bits that are already seen two times before
15            # because we want to ignore the third time
16          
17            # The operations can be explained as:
18            # If `once` is already set, and current bit of num is 0, keep `once`
19            # If `once` is not set, and `twice` and current bit is set, set `once`
20            # This updates bit in `once` only if bit in `num` is 1 and wasn't part
21            # of `twice`, or if bit in `num` is 0 and bit was already set in `once`.
22            once_new = (~once & twice & num) | (once & ~twice & ~num)
23          
24            # Next, calculate `twice` considering the current number `num`
25            # Bits in `once` are used to clear bits that appear for the third time
26            # This updates bits in `twice` only if bit in `num` is different from bit in `twice`
27            # and bit in `once` is 0, to ensure it's not the third time we see this bit.
28            twice_new = ~once & (twice ^ num)
29          
30            # Update `once` and `twice`
31            once, twice = once_new, twice_new
32          
33        # Return the number that appears only once
34        # All bits in `once` have now appeared either 0 or 3 times, which will end up with 0
35        # All bits in `twice` have now appeared exactly once or twice, which end up with 0
36        # Only the single number will set bits in `twice`
37        return twice
38
1class Solution {
2    public int singleNumber(int[] nums) {
3        int bit1 = 0;  // This will hold the XOR of all the elements which appear exactly once
4        int bit2 = 0;  // This will hold the XOR of all the elements which appear exactly twice
5      
6        for (int num : nums) {
7            // These intermediate values store the new values of bit1 and bit2
8            int newBit1 = (~bit1 & bit2 & num) | (bit1 & ~bit2 & ~num);
9            int newBit2 = ~bit1 & (bit2 ^ num);
10          
11            // Update bit1 and bit2 with their new values for the next iteration
12            bit1 = newBit1;
13            bit2 = newBit2;
14        }
15      
16        // At the end, bit2 will be the value that appears exactly once as 
17        // bit1 will store the XOR of the element which appears thrice which is 0.
18        return bit2;
19    }
20}
21
1#include <vector>
2
3class Solution {
4public:
5    int singleNumber(std::vector<int>& nums) {
6        int onlyOnce = 0; // Variable for the element that appears only once
7        int twiceState = 0; // Variable for the element that appears twice
8      
9        // Iterate over each element in the input vector
10        for (int num : nums) {
11            // Update `onlyOnce` only if `twiceState` is not set. This is part of tracking
12            // the element that appears once. If `twiceState` is set, reset `onlyOnce`.
13            int newOnlyOnce = (~onlyOnce & twiceState & num) | (onlyOnce & ~twiceState & ~num);
14          
15            // Update `twiceState`: it should be set if `onlyOnce` is not set and `num` is unique (XOR operation).
16            // If `num` is already in `onlyOnce`, then it should be cleared.
17            int newTwiceState = ~onlyOnce & (twiceState ^ num);
18          
19            // Update the states with the newly calculated values
20            onlyOnce = newOnlyOnce;
21            twiceState = newTwiceState;
22        }
23        // Since the problem guarantees one number appears exactly once and the others appear exactly three times,
24        // the `onlyOnce` variable will end up with the single appearing number. 
25        return twiceState; // The element that appears once is found in `twiceState` at the end of the loop
26    }
27};
28
1function singleNumber(nums: number[]): number {
2    let bitwiseA = 0; // Initialize 'bitwiseA' which will hold a bitwise representation
3    let bitwiseB = 0; // Initialize 'bitwiseB' which will hold another bitwise representation
4
5    // Loop through each number in the array
6    for (const num of nums) {
7        // Calculate the new value of 'bitwiseA' based on current 'bitwiseA', 'bitwiseB', and current num.
8        // It uses bitwise NOT (~), AND (&), and OR (|) operations.
9        const newBitwiseA = (~bitwiseA & bitwiseB & num) | (bitwiseA & ~bitwiseB & ~num);
10      
11        // Calculate the new value of 'bitwiseB' based on current 'bitwiseB' and num.
12        // It uses bitwise NOT (~), AND (&), and XOR (^) operations.
13        const newBitwiseB = ~bitwiseA & (bitwiseB ^ num);
14      
15        // Update 'bitwiseA' and 'bitwiseB' with the newly computed values.
16        bitwiseA = newBitwiseA;
17        bitwiseB = newBitwiseB;
18    }
19
20    // Since every element appears three times except for one element which appears once,
21    // 'bitwiseB' will hold the single number that appears only once at the end of the loop.
22    return bitwiseB;
23}
24
Not Sure What to Study? Take the 2-min Quiz：

How does merge sort divide the problem into subproblems?

Time and Space Complexity

The time complexity of the provided code is O(n), where n is the length of the input list nums. This is because there is a single loop that iterates through all the elements of the array once.

The space complexity of the code is O(1) as it uses a constant amount of space. The variables a, b, aa, and bb do not grow with the input size, hence the space used remains constant regardless of the size of the input array.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫