Description
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.
Examples:
Example 1:
Input: nums = [2,2,3,2]
Output: 3
Example 2:
Input: nums = [0,1,0,1,0,1,99]
Output: 99Solution in Python
To solve the problem of finding the single element in an array where every element appears three times except for one using Python, we need to use a bit manipulation approach. This approach ensures linear runtime complexity and constant space complexity.
Approach:
- Bit Manipulation with Counters:
- We can count the number of 1s for each bit position across all numbers.
- If a bit position’s count of 1s is not a multiple of 3, that bit belongs to the unique element.
- Bitwise Operations:
- We will use two integers,
onesandtwos, to keep track of the bits that have appeared once and twice, respectively. - For each number in the array, we update
onesandtwosaccordingly to ensure that bits appearing three times are reset.
- We will use two integers,
Python
from typing import List
class Solution:
def singleNumber(self, nums: List[int]) -> int:
# Initialize counters for bits appearing once and twice
ones, twos = 0, 0
# Iterate through each number in the array
for num in nums:
# Update `ones` and `twos` with the current number
ones = (ones ^ num) & ~twos
twos = (twos ^ num) & ~ones
# The number that appears once will be stored in `ones`
return onesExplanation:
- Initialization:
onesandtwosare initialized to 0. These variables will keep track of the bits that have appeared once and twice, respectively.
- Iterate through the Array:
- For each number in the array, we update
onesandtwos. ones = (ones ^ num) & ~twos: This updatesoneswith the current number while removing the bits that are already tracked intwos.twos = (twos ^ num) & ~ones: This updatestwoswith the current number while removing the bits that are already tracked inones.
- For each number in the array, we update
- Final Result:
- After processing all numbers,
oneswill hold the bits of the unique number that appears exactly once, as bits appearing three times will be reset.
- After processing all numbers,
This solution ensures a linear runtime complexity O(n) and uses only constant extra space O(1).
Solution in Javascript
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
// Initialize counters for bits appearing once and twice
let ones = 0, twos = 0;
// Iterate through each number in the array
for (let num of nums) {
// Update `ones` and `twos` with the current number
// ones keeps track of bits that have appeared once
// twos keeps track of bits that have appeared twice
ones = (ones ^ num) & ~twos;
twos = (twos ^ num) & ~ones;
}
// The number that appears once will be stored in `ones`
return ones;
};Solution in Java
Java
class Solution {
public int singleNumber(int[] nums) {
// Initialize counters for bits appearing once and twice
int ones = 0, twos = 0;
// Iterate through each number in the array
for (int num : nums) {
// Update `ones` and `twos` with the current number
// `ones` tracks bits that have appeared once
// `twos` tracks bits that have appeared twice
// `ones ^ num` toggles the bits in `ones` based on current `num`
// `~twos` ensures we clear bits that have appeared twice
ones = (ones ^ num) & ~twos;
twos = (twos ^ num) & ~ones;
}
// The number that appears once will be stored in `ones`
return ones;
}
}Solution in C#
C#
public class Solution {
public int SingleNumber(int[] nums) {
// Initialize counters for bits that appear once and twice
int ones = 0, twos = 0;
// Iterate through each number in the array
foreach (int num in nums) {
// Update `ones` and `twos` with the current number
// `ones` tracks bits that have appeared once
// `twos` tracks bits that have appeared twice
// XOR `ones` with current number and clear bits appearing in `twos`
ones = (ones ^ num) & ~twos;
// XOR `twos` with current number and clear bits appearing in `ones`
twos = (twos ^ num) & ~ones;
}
// The number that appears once will be stored in `ones`
return ones;
}
}