• 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

Stickler thief

flattens 2 D linked list to a single sorted link list

Reverse a Linked List in groups of given size

Number of Islands BFS/DFS

Interfaces in C++ (Abstract Classes in C++)

Best Java Book | Top Java Programming Book for Beginners

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

Print vertical sum of all the axis in the given binary tree

Daughter’s Age VeryGood Puzzle

C++ OOPs Part1

How strtok() Works

Find if a binary tree is height balanced ?

The Magic HackerEarth Nirvana solutions Hiring Challenge

N teams are participating. each team plays twice with all other teams. Some of them will go to the semi final. Find Minimum and Maximum number of matches that a team has to win to qualify for finals ?

SAP Off Campus Hiring_ March 2015 Sample Questions

TicTacToe Game As Asked in Flipkart

Regular Expression Matching

Maximum sum contiguous subarray of an Array

Longest Increasing Subsequence

System Design: Designing a LLD for Hotel Booking

Hackerearth : Counting Subarrays

Naurki.com Security Breach

Sequence Finder Dynamic Programming

Fibonacci Hashing & Fastest Hashtable

Linked List V/S Binary Search Tree

Memory Efficient LinkedList

Print all nodes that are at distance k from a leaf node

Top 10 Interviews Techniqes for Campus Interview in IIT NIT BITS for MTech

SAP Off Campus Hiring_ March 2015 Computer Skills

C Program for TAIL command of UNIX

Copyright © 2025 · Genesis Framework · WordPress · Log in