• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Find the element that appears once others appears thrice

January 27, 2015 by Dhaval Dave

Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once.
Expected time complexity is O(n) and O(1) extra space.
Examples:
Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
Output: 2

We know that
when we XOR same number twice, we can get 0.
XOR operation is associative, commutative.It does not matter in what fashion elements appear in array, we still get the answer.

Method 1)

So in order to get One element which appears once,
We need to take care of two variable.
Once, Twice and Thrice.

Algo :

1) Whenever we get element,   XOR’d to the variable “ones”.
2) Now if its repeated number it will be removed from “ones” and we xor it to “twice”.
3) A number appears twice will be removed from once, twice and stored in “thrice”
4) To remove all those are in common to “ones” and “twice” What we do is…

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

= > Now as we want to store twice appearing number as well, we need to perform them first so that before it gets 0 in ones, we store it.

Sample Code

for( i=0; i< 10; i++ ) 
{ 
x = B[i]; 
twos |= ones & x ; 
ones ^= x ; 
not_threes = ~(ones & twos) ; 
ones &= not_threes ; 
twos &= not_threes ; 
} 

printf(“n unique element = %d n“, ones ); 
return 0; 

Lets Trace values for input {12, 1, 12,1, 1, 12, 2}

  • Iteration =0 step = 1,two=0 
    Iteration =0 step = 2 ,ones=12 
    Iteration =0 step = 3 ,not_threes=-1 
    Iteration =0 step = 4 ,ones=12 
    Iteration =0 step = 5 ,twos=0 
  • 
    Iteration =1 step = 1,two=0 
    Iteration =1 step = 2 ,ones=13 
    Iteration =1 step = 3 ,not_threes=-1 
    Iteration =1 step = 4 ,ones=13 
    Iteration =1 step = 5 ,twos=0 
  • 
    Iteration =2 step = 1,two=12 
    Iteration =2 step = 2 ,ones=1 
    Iteration =2 step = 3 ,not_threes=-1 
    Iteration =2 step = 4 ,ones=1 
    Iteration =2 step = 5 ,twos=12 
  • 
    Iteration =3 step = 1,two=13 
    Iteration =3 step = 2 ,ones=0 
    Iteration =3 step = 3 ,not_threes=-1 
    Iteration =3 step = 4 ,ones=0 
    Iteration =3 step = 5 ,twos=13
  •  
    Iteration =4 step = 1,two=13 
    Iteration =4 step = 2 ,ones=1 
    Iteration =4 step = 3 ,not_threes=-2 
    Iteration =4 step = 4 ,ones=0 
    Iteration =4 step = 5 ,twos=12 
  • 
    Iteration =5 step = 1,two=12 
    Iteration =5 step = 2 ,ones=12 
    Iteration =5 step = 3 ,not_threes=-13 
    Iteration =5 step = 4 ,ones=0 
    Iteration =5 step = 5 ,twos=0 
  • 
    Iteration =6 step = 1,two=0 
    Iteration =6 step = 2 ,ones=2 
    Iteration =6 step = 3 ,not_threes=-1 
    Iteration =6 step = 4 ,ones=2 
    Iteration =6 step = 5 ,twos=0 
    
     Finally unique element = 2 
    


Method 2)

Check that input
{12,     1,       12,      1,       1,        12,      2} and its binary
{1100, 0001, 1100, 0001, 0001, 1100, 0010}

Sum of Unit digit = 0+1+0+1+1+0+0 = 3 % 3 = 0
Sum of Decimal digit = 0+0+0+0+0+0+1 = 1%3 =1
so
BitWise OR of ALL VALUES where Sum%3 != 0 is answer.

#define INT_SIZE  8
int getSingle(int arr[], int n)
{

    int result = 0;
    int x, sum,i,j;
    for (i = 0; i < INT_SIZE; i++)
    {
      sum = 0;
      x = (1 << i);
      for (j=0; j< n; j++ )
      {
          if (arr[j] & x)
            sum++;
      }
      if (sum % 3){
        result |= x;
        printf(“X=%dn”,x);
     
      }
    }

    return result;
}

int main()
{
    int arr[] = {12, 1, 12, 1, 1, 12, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf(“The element with single occurrence is %d “,
            getSingle(arr, n));
    return 0;
}

Output

X=1
X=2
The element with single occurrence is 3 

Similar Articles

Filed Under: Amazon Interview Question, Interview Questions, Microsoft Interview Questions, problem Tagged With: Array, Bit Arithmeticm

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

robot standing at first cell of an M*N matrix. It can move only in two directions, right and down. In how many ways, it can reach to the last cell i.e. (M, N) Code it

Right view of Binary tree

Convert number to words java

Sort an array according to the order defined by another array

Maximum occurred Smallest integer in n ranges

Maximum of all subarrays of size k

Python Array String

Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles

Check Binary Tree is Binary Search Tree or not

Test Cases for Round Function

Maximum size of square sub matrix with all 1’s in a binary matrix

Password Predictor

Singly linked list

Daughter’s Age VeryGood Puzzle

Find shortest distances between every pair of vertices ( Dynamic Programming Floyd Warshall Algorithm)

System Design: Designing a LLD for Hotel Booking

Microsoft BING Interview Experience

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

TicTacToe Game As Asked in Flipkart

The Magic HackerEarth Nirvana solutions Hiring Challenge

Given a sorted array and a number x, find the pair in array whose sum is closest to x

Regular Expression Matching

Count Possible Decodings of a given Digit Sequence

Trapping Rain Water

Find an index i such that Arr [i] = i in array of n distinct integers sorted in ascending order.

Search element in a matrix with all rows and columns in sorted order

VMWare SDEII Interview

The greedy coins game Dynamic Programming

Find the smallest window in a string containing all characters of another string

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

Copyright © 2025 · Genesis Framework · WordPress · Log in