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

Score After Flipping Matrix Problem

LeetCode 861. You are given an m x n binary...

Chalkboard Xor Game Problem

LeetCode 810. You are given an array of integers nums...

Bitwise ORs Of Subarrays Problem

LeetCode 898. We have an array arr of non-negative integers....

Binary Gap Problem

LeetCode 868. Given a positive integer n, find and return...

K-Th Symbol In Grammar Problem

LeetCode 779. We build a table of n rows (1-indexed)....