CareerCup

Add the numbers bitwise mod 3. I guess too many people were just saying "XOR" without understanding properly.

Explanation for siva.sai.2020's code.

The code works in similar line with the question of "finding the element which appears once in an array - containing other elements each appearing twice". Solution is to XOR all the elements and you get the answer.

Basically, it makes use of the fact that x^x = 0. So all paired elements get XOR'd and vanish leaving the lonely element.
Since XOR operation is associative, commutative.. it does not matter in what fashion elements appear in array, we still get the answer.

Now, in the current question - if we apply the above idea, it will not work because - we got to have every unique element appearing even number of times. So instead of getting the answer, we will end up getting XOR of all unique elements which is not what we want.

To rectify this mistake, the code makes use of 2 variables.
ones - At any point of time, this variable holds XOR of all the elements which have
appeared "only" once.
twos - At any point of time, this variable holds XOR of all the elements which have
appeared "only" twice.

So if at any point time,
1. A new number appears - It gets XOR'd to the variable "ones".
2. A number gets repeated(appears twice) - It is removed from "ones" and XOR'd to the
variable "twice".
3. A number appears for the third time - It gets removed from both "ones" and "twice".

The final answer we want is the value present in "ones" - coz, it holds the unique element.

So if we explain how steps 1 to 3 happens in the code, we are done.
Before explaining above 3 steps, lets look at last three lines of the code,

not_threes = ~(ones & twos)
ones & = not_threes
twos & = not_threes

All it does is, common 1's between "ones" and "twos" are converted to zero.

For simplicity, in all the below explanations - consider we have got only 4 elements in the array (one unique element and 3 repeated elements - in any order).


Explanation for step 1
------------------------
Lets say a new element(x) appears.
CURRENT SITUATION - Both variables - "ones" and "twos" has not recorded "x".

Observe the statement "twos| = ones & x".
Since bit representation of "x" is not present in "ones", AND condition yields nothing. So "twos" does not get bit representation of "x".
But, in next step "ones ^= x" - "ones" ends up adding bits of "x". Thus new element gets recorded in "ones" but not in "twos".

The last 3 lines of code as explained already, converts common 1's b/w "ones" and "twos" to zeros.
Since as of now, only "ones" has "x" and not "twos" - last 3 lines does nothing.



Explanation for step 2.
------------------------
Lets say an element(x) appears twice.
CURRENT SITUATION - "ones" has recorded "x" but not "twos".

Now due to the statement, "twos| = ones & x" - "twos" ends up getting bits of x.
But due to the statement, "ones ^ = x" - "ones" removes "x" from its binary representation.

Again, last 3 lines of code does nothing.
So ultimately, "twos" ends up getting bits of "x" and "ones" ends up losing bits of "x".



Explanation for step 3.
-------------------------
Lets say an element(x) appears for the third time.
CURRENT SITUATION - "ones" does not have bit representation of "x" but "twos" has.

Though "ones & x" does not yield nothing .. "twos" by itself has bit representation of "x". So after this statement, "two" has bit representation of "x".
Due to "ones^=x", after this step, "one" also ends up getting bit representation of "x".

Now last 3 lines of code removes common 1's of "ones" and "twos" - which is the bit representation of "x".
Thus both "ones" and "twos" ends up losing bit representation of "x".



1st example
------------
2, 2, 2, 4

After first iteration,
ones = 2, twos = 0
After second iteration,
ones = 0, twos = 2
After third iteration,
ones = 0, twos = 0
After fourth iteration,
ones = 4, twos = 0

2nd example
------------
4, 2, 2, 2

After first iteration,
ones = 4, twos = 0
After second iteration,
ones = 6, twos = 0
After third iteration,
ones = 4, twos = 2
After fourth iteration,
ones = 4, twos = 0


Explanation becomes much more complicated when there are more elements in the array in mixed up fashion. But again due to associativity of XOR operation - We actually end up getting answer.

Superbly explained.
Let me know if you find better explnation than this!
youtube.com/watch?v=mHfvInveXDQ

Sort the array but in this case time complexity will be n*log(n).

Using memory:
use hash table to store frequency. average complexity O(n), worst case O(n^2).

W/O memory:
sorting, and checking if a[i-1] != a[i+1] for i = 1 to n-2, assuming 0 index array

1. Do a partition.
1. if number of elements on the both sides are exactly divisible by 3 then Pivoted element is the required number.
2. At least one side of pivoted element will be divisible by 3. So take the other side and perform step 1.

Space Complexity - constant, Time Complexity is o(n),
but array will get destroyed.

Check the solution here on stackoverflow
stackoverflow /questions/2497470/given-an-array-of-integers-where-some-numbers-repeat-1-time-some-numbers-repeat

public static void main(String[] args) {
int B[] = {1,1,1,3,3,3,4,4,4,5,5,5,6,6,6,7,8,8,8,9,9,9};
for(int i=0;i<B.length-2; i=i+3){
if(B[i]!=B[i+1] || B[i+1]!=B[i+2]){
n = B[i];
break;
}
}
if(n==0)
System.out.println("Unique no. - " + B[B.length-1]);
else
System.out.println("Unique no. - " + n);

}

HashMap solution:

int B[] = {1,1,1,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,9,9,9,11,11,11,44,44,44,46};
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
for(int i=0; i<B.length;i++){
if(hm.containsKey(B[i])){
hm.put(B[i], hm.get(B[i])+1);
}else{
hm.put(B[i],1);
}
}
Iterator itr = hm.entrySet().iterator();
while(itr.hasNext()){
Map.Entry pairs = (Map.Entry)itr.next();
if((Integer)pairs.getValue() == 1){
System.out.println("Hash Operation - Unique no. - "+pairs.getKey());
break;
}

}

You are welcome!

Explanation for step 1
------------------------
Lets say a new element(x) appears.
CURRENT SITUATION - Both variables - "ones" and "twos" has not recorded "x".

Observe the statement "twos| = ones & x".
Since bit representation of "x" is not present in "ones", AND condition yields nothing. So "twos" does not get bit representation of "x".



@Rama B:
if you consider the sequence 6,2,2,2

After 6 is considered, we have ones=6, twos=0
next comes 2, while doing twos|= ones & x, the and yields 6&2=2 contrary to your statement that the and yields nothing when a new number(this case 2) arrives. Even though the ultimate result comes out to be correct in this sequence also, but looking for an explanation how the correction occurs?

Is the range of numbers in the array known to us ?

No need of sorting.....
....
int SUM=0, a[]={..........}; //
for(i=0;i<SIZE;i++) // SIZE=size of an array
{
SUM+=a[i];
}
for(i=0;i<SIZE;i++)
{
if ( (SUM + 2x)%3==0 && x==a[i] )
return x;
}


complexity=O(n)..

static void Main(string[] args)
        {
            int[] arr = { 1,4,2,1,4,2,1,2,4,5};
            int unique = FindUnique(arr);
            Console.WriteLine(unique);
            Console.ReadLine();
        }
        public static int FindUnique(int[] arr)
        {
            int once = 0; int twice = 0; int Threes; int x = 0;

            for (int i = 0; i < 10; i++)
            {
                x = arr[i];
                twice |= once & x; //add it to twice if it exists in once
                once ^= x; //it exists in once, remove it, otherwise, add it
                Threes = once & twice;  //if x is in once and twice, add it to Threes.
                // and thus 
                once &= ~Threes; //remove x from once
                twice &= ~Threes; //remove x from twice
            }
            return once;
        }

static void Main(string[] args)
{
            int[] arr = { 1,4,2,1,4,2,1,2,4,5};
            int unique = FindUnique(arr);
            Console.WriteLine(unique);
            Console.ReadLine();
}
public static int FindUnique(int[] arr)
{
            int once = 0; int twice = 0; int Threes; int x = 0;

            for (int i = 0; i < 10; i++)
            {
                x = arr[i];
                twice |= once & x;             //add it to twice if it exists in once
                once ^= x;                        //if x exists in once, remove it, otherwise, add it
                Threes = once & twice;    //if x exists in once and twice, add it to Threes. 
                once &= ~Threes;            //remove x from once
                twice &= ~Threes;           //remove x from twice
            }
            return once;
}

bitwise and easier to be understandable

int findIntOnceOfThrees(int* A, int n)
	{
		int M[32]={0x01};
		for(int i= 1; i<32; i++)
		{
			M[i] = M[0] << i;
		}

		int C[32] = {0};
		for(int i=0; i<n; i++)
		{
			for(int j=0; j<32; j++)
			{
				if (A[i] & M[j])
				{
					C[j] = (C[j]+1)%3;
				}
			}
		}
		int ret = 0;
		for(int i=0; i<32; i++)
		{
			if (C[i])
			{
				ret |= M[i];
			}
		}
		return ret;
	}

I've jus ACed the same problem in leetcode.
Here is my code:

public class Solution {
    public int singleNumber(int[] A) {
        if(A.length <1) return 0;
        int result = 0;
        int count = 0;      //adding binary digits at the same place
        for(int j = 0; j < 32; j++){
            for(int i = 0; i < A.length; i++){
                if(((A[i] >> j) & 1) == 1)
                    count++;
            }
        result |= ((count % 3) << j);   //this gives binary digit of the single one at Jth place.
        count = 0;
        }
        return result;
    }

}
Basically used the top answer strategy, adding numbers up bitwise, mod 3 get the bit for the single one.
Time complexity O(n), space complexity O(1);

Algo:-
new element - > xor with 'ones'
element repeated twice - > remove from 'ones' and xor with 'twos'
element repeated thrice -> remove from both 'ones' and 'twos'
return ones

code:-
public int singleNumber(int[] A) {
int ones = 0, twos = 0;
for(int i = 0; i < A.length; i++){
ones = (ones ^ A[i]) & ~twos;
twos = (twos ^ A[i]) & ~ones;
}
return ones;

Algo:-
new element - > xor with 'ones'
element repeated twice - > remove from 'ones' and xor with 'twos'
element repeated thrice -> remove from 'twos'
return ones

code:-

public int singleNumber(int[] A) {
    int ones = 0, twos = 0;
    for(int i = 0; i < A.length; i++){
        ones = (ones ^ A[i]) & ~twos;
        twos = (twos ^ A[i]) & ~ones;
    }
    return ones;

I found it pretty complicated to understand the above logic when elements were scattered eg 4,3,4,3,4. I found the solution 2 by geeksforgeeks simpler to understand for people like me. "geeksforgeeks.org/find-the-element-that-appears-once/"

Explanation directly from geekForGeeks
Let us consider the example array {5, 5, 5, 8}. The 101, 101, 101, 1000
Sum of first bits%3 = (1 + 1 + 1 + 0)%3 = 0;
Sum of second bits%3 = (0 + 0 + 0 + 0)%0 = 0;
Sum of third bits%3 = (1 + 1 + 1 + 0)%3 = 0;
Sum of fourth bits%3 = (1)%3 = 1;

def special(lst):
    ones = 0
    twos = 0
    for x in lst:
        twos |= ones&x
        ones ^= x
    return ones^twos

int find(int[] A) {
  int[] cnt = new int[32];

  for(int x : A) {
    for(int i = 0; i < 32; i++) {
      cnt[i] += (x >> i) & 1;
    }
  }

  int res = 0;
  for(int i = 0; i < 32; i++) {
    res += (cnt[i] % 3 == 0 ? 0 : 1) << i;
  }

  return res;
}

int get_uniq(const vector<int> &v, size_t k)
{
    size_t s = sizeof(int) * 8;
    vector<int> bits(s);

    for (const int el: v)
    {
        for (size_t j = 0; j < s; ++j)
        {
            bits[j] += (el & (1 << j)) >> j;
        }
    }

    int res = 0;
    for (size_t j = 0; j < s; ++j)
    {
        if (bits[j] % k == 1)
        {
            res |= (1 << j);
        }
    }
    return res;
}

class Solution:
def occurs(self,A):
A.sort()
if len(A)>1:
if A[0]<>A[1]:
return A[0]
f=0
for i in xrange(1,len(A)-1):
f=1
if A[i-1]<>A[i] and A[i]<>A[i+1]:
return A[i]
if f==1:
if A[len(A)-2]<>A[len(A)-1]:
return A[len(A)-1]
return -1


ss=Solution()
print ss.occurs([2, 1, 2, 3, 12, 1, 1, 2, 3, 3])


output 12

package Algorithm.Bit;

public class ElementAppearsOnce {

static int getInteger(int arr[], int n){
int result = 0;
int x, sum;
for(int i=0;i<32;i++){
sum = 0;
x = (1<<i);
for(int j=0;j<n;j++){
if((arr[j] & x) ==0)
sum++;
}
if(sum%3==0)
result = result|x;
}

return result;
}

public static void main(String args[]){
int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
int n = arr.length;
int res = getInteger(arr, n);
System.out.println(res);
}

}

package Algorithm.Bit;

public class ElementAppearsOnce {
	
	static int getInteger(int arr[], int n){
		int result = 0;
		int x, sum;
		for(int i=0;i<32;i++){
			sum = 0;
			x = (1<<i);
			for(int j=0;j<n;j++){
				if((arr[j] & x) ==0)
					sum++;
			}
			if(sum%3==0)
				result = result|x;
		}
		
		return result;
	}
	
	public static void main(String args[]){
		int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
		int n = arr.length;
		int res = getInteger(arr, n);
		System.out.println(res);
	}

}

bullshit

#include <stdio.h>
#define INT_SIZE 32

int getSingle(int arr[], int n)
{
	// Initialize result
	int result = 0;

	int x, sum;

	// Iterate through every bit
	for (int i = 0; i < INT_SIZE; i++)
	{
	// Find sum of set bits at ith position in all
	// array elements
	sum = 0;
	x = (1 << i);
	for (int j=0; j< n; j++ )
	{
		if (arr[j] & x)
			sum++;
	}

	// The bits with sum not multiple of 3, are the
	// bits of element with single occurrence.
	if (sum % 3)
		result |= x;
	}

	return result;
}

// Driver program to test above function
int main()
{
	int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
	int n = sizeof(arr) / sizeof(arr[0]);
	printf("The element with single occurrence is %d ",
			getSingle(arr, n));
	return 0;
}

#include <stdio.h>
#define INT_SIZE 32

int getSingle(int arr[], int n)
{
// Initialize result
int result = 0;

int x, sum;

// Iterate through every bit
for (int i = 0; i < INT_SIZE; i++)
{
// Find sum of set bits at ith position in all
// array elements
sum = 0;
x = (1 << i);
for (int j=0; j< n; j++ )
{
if (arr[j] & x)
sum++;
}

// The bits with sum not multiple of 3, are the
// bits of element with single occurrence.
if (sum % 3)
result |= x;
}

return result;
}

// Driver program to test above function
int main()
{
int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("The element with single occurrence is %d ",
getSingle(arr, n));
return 0;
}

Can someone please advise why below code is not the optimal solution ?

def FindNonDuplicate(alist):
    for num in alist:
        count[num] = count.get(num, 0) + 1
    print(count.items())
    return [k for k, v in count.items() if v != 3]

def FindNonDuplicate(alist):
    for num in alist:
        count[num] = count.get(num, 0) + 1
    print(count.items())
    return [k for k, v in count.items() if v != 3]

the concept is same as the "all but one element appearing twice" question and can be extended to any number "all element but one appearing thrice" or even "all but one appearing 5 times" - the even number questions will follow same algorithm as "all but one element appearing twice".

The idea is save the number of times a value has appeared so far in different variables:
ones stores all elements that have appeared only once
twos stores all elements that have appeared twice
and when a value appears 3 times, we remove it from ones and twos.
In the end we will be left with the only value that appears only once in variable "ones"

test test11

est test

A[0]=A[0]^A[i];
cout<<A[0]<<endl;

1. Brute Force - O(n^2) - No extra memory
2. Sort - O(nlogn) - No extra Memory
3. Hash - O(n) - Extra Memory
4. XOR - O(n) - No Extra Memory

for eg. [2,1,4,5,1,4,2,2,4,1]=>5
steps: 1. XOR all elements, that will give unique sum say X
Unique Sum,X= 2^1^4^5^1^4^2^2^4^1 = 1+2+4+5=12
2. Calculate total sum, Y = 26
3. Ans Z = (Y-(X*3))/2= (26-(12*3))/2= 5

enjoy!!