Single Number II Problem


Description

LeetCode Problem 137.

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

You mustimplement a solution with a linear runtime complexity and useonly constantextra space.

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= nums.length <= 3 * 10^4
  • -2^31 <= nums[i] <= 2^31 - 1
  • Each element in nums appears exactly three times except for one element which appears once.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int n = nums.size();
        long ans;
        int x, t;
        ans = 0;
        int p = 0;
		// We have 32 bits integers as input
        for(int i = 0; i < 32; i++) {
            t = 0;
            //calculate sum of ith bit for all numbers in nums
            for(int j = 0; j < n;j++) {
                x = nums[j] & 1;
                t = t + x;
                nums[j] = nums[j] >> 1;
            }
            t = t % 3;
            //the bit that does not occur as multiple of 3 is left as a remainder 
            ans = ans + t * pow(2, p);
            p++;
        }
        return ans;
    }
};




Related Posts

Bitwise And Of Numbers Range Problem

LeetCode 201. Given two integers left and right that represent...

Reverse Bits Problem

LeetCode 190. Reverse bits of a given 32 bits unsigned...

Number Of 1 Bits Problem

LeetCode 191. Write a function that takes an unsigned integer...

Single Number Problem

LeetCode 136. Given a non-empty array of integers nums, every...

Single Number II Problem

LeetCode 137. Given an integer array nums whereevery element appears...