Jobs

Interviews

Discussions

Single Number II

#157 Most AskedMedium

Single Number II #157 Most Asked

Medium

Yahoo

14 views

Topics:

ArraysBit Manipulation

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,3,2]
Output: 3

Example 2:

Input: nums = [0,1,0,1,0,1,99]
Output: 99

Constraints:

1 <= nums.length <= 3 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
Each element in nums appears exactly three times except for one element which appears once.

Try coding it in LeetCode

Single Number II

#157 Most AskedMedium

Single Number II #157 Most Asked

Medium

Yahoo

14 views

Topics:

ArraysBit Manipulation

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,3,2]
Output: 3

Example 2:

Input: nums = [0,1,0,1,0,1,99]
Output: 99

Constraints:

1 <= nums.length <= 3 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
Each element in nums appears exactly three times except for one element which appears once.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array? Can I expect negative numbers, zero, or only positive integers?
Is it guaranteed that there will always be exactly one number that appears only once? If not, what should I return if there is no such number?
What is the maximum size of the input array 'nums'?
Are we concerned about integer overflow when performing arithmetic operations?
Does the order of elements in the input array matter?

Brute Force Solution

Approach

The brute force approach to finding the single number involves checking each number against every other number. We're looking for the number that appears only once while all others appear exactly three times. It's like counting how many times each number shows up and picking the one with a count of one.

Here's how the algorithm would work step-by-step:

Take the first number from the list.
Go through the entire list and count how many times this number appears.
If the number appears only once, you've found your answer and can stop.
If it appears three times, move on to the next number in the original list.
Repeat this process for each number in the list until you find the one that appears only once.

Code Implementation

def single_number_brute_force(numbers):
    for current_number in numbers:
        number_of_appearances = 0

        for number in numbers:
            if number == current_number:
                number_of_appearances += 1

        # If the number appears only once, return it.
        if number_of_appearances == 1:
            return current_number

        # If the number appears three times, continue to the next number
        elif number_of_appearances == 3:
            continue

    # This will be reached if there is invalid input
    return None

Big(O) Analysis

Time Complexity

O(n²) – The proposed solution iterates through each of the n numbers in the input array. For each of these n numbers, the solution iterates through the entire array again to count its occurrences. Therefore, the number of operations performed is proportional to n multiplied by n, resulting in n * n operations. Hence, the time complexity is O(n²).

Space Complexity

O(1) – The brute force approach iterates through the list of numbers, but it does not use any auxiliary data structures like lists, hash maps or sets to store intermediate values. It only maintains a count variable to track the number of times each element occurs. This count variable, along with any index variables used for iteration, takes up constant space regardless of the input size N. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The core idea is to track the occurrence of each number's bits without using extra storage for counting each number directly. We achieve this by cleverly using two variables to keep track of which bits have appeared once, twice, or (implicitly) three times. Once a bit appears three times, it's effectively reset, allowing us to isolate the bits that appear only once overall.

Here's how the algorithm would work step-by-step:

Imagine each number as a series of switches (bits), each representing a power of 2.
We'll use two special boxes (variables) to keep track of whether a switch has been flipped once, twice, or three times.
Go through the numbers one by one. For each number, consider each of its switches.
If a switch is flipped for the first time, mark it in the first box.
If that same switch is flipped again, move it from the first box to the second box.
If that switch is flipped a third time, remove it from both boxes.
After processing all the numbers, the switches that are still on in the first box represent the number that only appeared once.

Code Implementation

def single_number_ii(numbers: list[int]) -> int:
    seen_once = 0
    seen_twice = 0

    for number in numbers:
        # If seen_once has the bit, it's the second time.
        seen_twice |= seen_once & number
        
        # Update seen_once with bits that haven't been seen.
        seen_once ^= number

        # Find bits seen three times, clear them in both.
        common_bit_mask = ~(seen_once & seen_twice)

        seen_once &= common_bit_mask
        seen_twice &= common_bit_mask

    return seen_once

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums once. For each number in the array, a fixed number of bitwise operations and updates to the variables 'one' and 'two' are performed. The number of bitwise operations does not depend on the size of the input array, so the dominant factor is the single pass through the n elements of the array. Therefore, the time complexity is directly proportional to the input size n, resulting in O(n).

Space Complexity

O(1) – The solution uses two integer variables (representing the two 'boxes') to track the bits that have appeared once and twice, respectively. The number of these variables does not depend on the size of the input array. Therefore, the space required is constant regardless of the input size N, making the space complexity O(1).

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 or throw an IllegalArgumentException, depending on the requirements.
Array with only one element	Return the single element directly since it must be the unique number.
Array with all elements the same	Return 0 since no single number exists; if error condition is allowed, throw an exception.
Very large array (close to memory limit)	The bit manipulation approach scales well with large arrays avoiding extra memory.
Array contains negative numbers	Bit manipulation works correctly with negative integers through their two's complement representation; other solutions need to handle the sign correctly.
Array contains zero	Zero is treated like any other number and handled correctly by the bit manipulation approach.
Extreme boundary values (Integer.MAX_VALUE, Integer.MIN_VALUE)	Bit manipulation is robust to these extreme values as each bit is processed independently.
Integer overflow potential during intermediate calculations in alternative solutions (e.g., summing)	Bit manipulation or appropriate data types (long) should be used to avoid overflow if summing or other calculation-based solutions are used.

Empty or null input array

How to Handle:

Return 0 or throw an IllegalArgumentException, depending on the requirements.

Array with only one element

How to Handle:

Return the single element directly since it must be the unique number.

Array with all elements the same

How to Handle:

Return 0 since no single number exists; if error condition is allowed, throw an exception.

Very large array (close to memory limit)

How to Handle:

The bit manipulation approach scales well with large arrays avoiding extra memory.

Array contains negative numbers

How to Handle:

Bit manipulation works correctly with negative integers through their two's complement representation; other solutions need to handle the sign correctly.

Array contains zero

How to Handle:

Zero is treated like any other number and handled correctly by the bit manipulation approach.

Extreme boundary values (Integer.MAX_VALUE, Integer.MIN_VALUE)

How to Handle:

Bit manipulation is robust to these extreme values as each bit is processed independently.

Integer overflow potential during intermediate calculations in alternative solutions (e.g., summing)

How to Handle:

Bit manipulation or appropriate data types (long) should be used to avoid overflow if summing or other calculation-based solutions are used.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array? Can I expect negative numbers, zero, or only positive integers?
Is it guaranteed that there will always be exactly one number that appears only once? If not, what should I return if there is no such number?
What is the maximum size of the input array 'nums'?
Are we concerned about integer overflow when performing arithmetic operations?
Does the order of elements in the input array matter?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first number from the list.
Go through the entire list and count how many times this number appears.
If the number appears only once, you've found your answer and can stop.
If it appears three times, move on to the next number in the original list.
Repeat this process for each number in the list until you find the one that appears only once.

Code Implementation

def single_number_brute_force(numbers):
    for current_number in numbers:
        number_of_appearances = 0

        for number in numbers:
            if number == current_number:
                number_of_appearances += 1

        # If the number appears only once, return it.
        if number_of_appearances == 1:
            return current_number

        # If the number appears three times, continue to the next number
        elif number_of_appearances == 3:
            continue

    # This will be reached if there is invalid input
    return None

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine each number as a series of switches (bits), each representing a power of 2.
We'll use two special boxes (variables) to keep track of whether a switch has been flipped once, twice, or three times.
Go through the numbers one by one. For each number, consider each of its switches.
If a switch is flipped for the first time, mark it in the first box.
If that same switch is flipped again, move it from the first box to the second box.
If that switch is flipped a third time, remove it from both boxes.
After processing all the numbers, the switches that are still on in the first box represent the number that only appeared once.

Code Implementation

def single_number_ii(numbers: list[int]) -> int:
    seen_once = 0
    seen_twice = 0

    for number in numbers:
        # If seen_once has the bit, it's the second time.
        seen_twice |= seen_once & number
        
        # Update seen_once with bits that haven't been seen.
        seen_once ^= number

        # Find bits seen three times, clear them in both.
        common_bit_mask = ~(seen_once & seen_twice)

        seen_once &= common_bit_mask
        seen_twice &= common_bit_mask

    return seen_once

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 or throw an IllegalArgumentException, depending on the requirements.
Array with only one element	Return the single element directly since it must be the unique number.
Array with all elements the same	Return 0 since no single number exists; if error condition is allowed, throw an exception.
Very large array (close to memory limit)	The bit manipulation approach scales well with large arrays avoiding extra memory.
Array contains negative numbers	Bit manipulation works correctly with negative integers through their two's complement representation; other solutions need to handle the sign correctly.
Array contains zero	Zero is treated like any other number and handled correctly by the bit manipulation approach.
Extreme boundary values (Integer.MAX_VALUE, Integer.MIN_VALUE)	Bit manipulation is robust to these extreme values as each bit is processed independently.
Integer overflow potential during intermediate calculations in alternative solutions (e.g., summing)	Bit manipulation or appropriate data types (long) should be used to avoid overflow if summing or other calculation-based solutions are used.

Empty or null input array

How to Handle:

Return 0 or throw an IllegalArgumentException, depending on the requirements.

Array with only one element

How to Handle:

Return the single element directly since it must be the unique number.

Array with all elements the same

How to Handle:

Return 0 since no single number exists; if error condition is allowed, throw an exception.

Very large array (close to memory limit)

How to Handle:

The bit manipulation approach scales well with large arrays avoiding extra memory.

Array contains negative numbers

How to Handle:

Bit manipulation works correctly with negative integers through their two's complement representation; other solutions need to handle the sign correctly.

Array contains zero

How to Handle:

Zero is treated like any other number and handled correctly by the bit manipulation approach.

Extreme boundary values (Integer.MAX_VALUE, Integer.MIN_VALUE)

How to Handle:

Bit manipulation is robust to these extreme values as each bit is processed independently.

Integer overflow potential during intermediate calculations in alternative solutions (e.g., summing)

How to Handle:

Bit manipulation or appropriate data types (long) should be used to avoid overflow if summing or other calculation-based solutions are used.

0/237 Yahoo questions completed

0/237 completed