Posts Single Number II
Post
Cancel

Single Number II

Problem 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. leetcode

Solution

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int singleNumber(int[] nums) {

        int[] arr = new int[32];

        for(int i=0; i<=31; i++){
            int count = countSetForAtPosition(nums, i);
            System.out.println(count);
            if(count%3 != 0) arr[31-i] = 1;
        }

        StringBuffer sb = new StringBuffer();
        for(int i=0; i<arr.length; i++){
            sb.append(arr[i]+"");
        }

        long l = Long.parseLong(sb.toString(), 2);
        int number = (int) l;

        return number;

    }

    public int countSetForAtPosition(int[] nums, int position){

        int c=0;

        for(int i=0; i<nums.length; i++){
            if(checkSetAtPosition(nums[i], position)) c++;
        }

        return c;
    }

    public boolean checkSetAtPosition(int n, int i){
        n = n>>i;
        return (n&1)==1;
    }
}

Another way to 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
26
27
28
29
30
31
32
33
34
35
class Solution {

    public int singleNumber(int[] nums) {

        int ans = 0;

        for(int i=0; i<=31; i++){
            int count = countSetAtPosition(nums, i);
            if(count%3 != 0){
              ans = ans|(1<<i); //1<<i is equivalent of 2^i. We are basically setting the bit at ith position
            }

        }

        return ans;
    }

    public int countSetAtPosition(int[] nums, int position){

        int c=0;

        for(int i=0; i<nums.length; i++){
            if(checkSetAtPosition(nums[i], position)) c++;
        }

        return c;

    }

    public boolean checkSetAtPosition(int n, int i){
        n = n>>i;
        return (n&1)==1;
    }

}
This post is licensed under CC BY 4.0 by the author.