Even occurring elements
PROBLEM :
Given an array that contains odd number of occurrences for all numbers except for a few elements which are present even number of times. Find the elements which have even occurrences in the array in O(n) time complexity and O(1) extra space.
Note: In some array, array contains only odd number then you have to print only a blank new line.
Input:
The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consist of two lines. The first line of each test case consists of an integer N, where N is the size of array.
The second line of each test case contains N space separated integers denoting array elements.
Output:
Corresponding to each test case, in a new line, print the elements which have even occurrences in the array.
Constraints:
1 = T = 100
1 = N = 200
1 = A[i] = 63
Example:
Input
3
11
9 12 23 10 12 12 15 23 14 12 15
5
23 12 56 34 32
4
10 34 10 56
Output
12 23 15
10
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
#include<iostream>
using namespace std;
int main()
{
int t,no,arr[200],i ;
cin>>t ;
while(t--)
{
cin>>no ;
for(i=0;i<no;i++)
cin>>arr[i] ;
int hash[64]={0} ;
for(i=0;i<no;i++)
hash[arr[i]]++ ;
for(i=0;i<no;i++)
{
if(hash[arr[i]]%2==0)
{
cout<<arr[i]<<" " ;
hash[arr[i]]=-1 ;
}
}
cout<<endl ;
}
return 0;
}
---------------------------------------------------------------------------------
Given an array that contains odd number of occurrences for all numbers except for a few elements which are present even number of times. Find the elements which have even occurrences in the array in O(n) time complexity and O(1) extra space.
Note: In some array, array contains only odd number then you have to print only a blank new line.
Input:
The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consist of two lines. The first line of each test case consists of an integer N, where N is the size of array.
The second line of each test case contains N space separated integers denoting array elements.
Output:
Corresponding to each test case, in a new line, print the elements which have even occurrences in the array.
Constraints:
1 = T = 100
1 = N = 200
1 = A[i] = 63
Example:
Input
3
11
9 12 23 10 12 12 15 23 14 12 15
5
23 12 56 34 32
4
10 34 10 56
Output
12 23 15
10
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
#include<iostream>
using namespace std;
int main()
{
int t,no,arr[200],i ;
cin>>t ;
while(t--)
{
cin>>no ;
for(i=0;i<no;i++)
cin>>arr[i] ;
int hash[64]={0} ;
for(i=0;i<no;i++)
hash[arr[i]]++ ;
for(i=0;i<no;i++)
{
if(hash[arr[i]]%2==0)
{
cout<<arr[i]<<" " ;
hash[arr[i]]=-1 ;
}
}
cout<<endl ;
}
return 0;
}
---------------------------------------------------------------------------------
Comments
Post a Comment