PROBLEM LINK:
Author: Illisha Singh
Tester: Illisha Singh, Kabir Kanha Arora, Jackson Jose, Vaibhav Gautam, Nishank Suresh
Editorialist: Illisha Singh
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
PROBLEM:
The crux of the problem is to find an element that does not occur thrice in the given array.
Approach 1: Element count based approach
A plausible approach that would also satisfy the given constraints would be by using a map that simply keeps the count of the frequencies of each number. Returning the element that has frequency 1 would suffice.
Hashing of n elements takes O(n) time and involves O(n) space.
Approach 2: Sort the array
Another approach that is not as efficient but would satisfy the constraints would be to sort the input array and for each element A[i], look at the A[i+3]th element and see if the values are same. In case they are not, the unique element has been found.
The time taken to sort(efficiently) would be O(nlogn). The traversal would take O(n) time. Thus, this approach would take O(nlogn) time.
Approach 3: Bit Manipulation
The idea behind this efficient approach is that each number that appears three times would either provide three ‘1’s or three ‘0’s to the associated bit position. The number that appears only once would account for only one 1 or 0 in that bit position.
Let the unique number (that occurs just once) be U.
Looking at the bit position of each number, we have:
~ If U has 1 in that particular bit position, it results into (3p+1) number of 1s in that position, where p = (n-1)/3.
~ If U has 0 in that particular bit position, it results into (3p+1) number of 0s in that position.
We can move ahead with this reasoning to solve in two ways:
a) Use an array to keep a track of each bit
It can be seen that none of the numbers go beyond 32 bits and thus, an array of size 32 where each bit keeps a track of the i^th bit of each number. Finally the positions with 3p+1 ones and zeroes at certain bits would allow us to construct the needed number.
This approach takes O(n) time. Space taken by an array of size 32 is nominal, O(1).
b) Use Bitmask Variables
Make use of ones as a bitmask to represent the ith bit had appears one time.
Use of twos as a bitmask to represent the ith bit had appears two times.
And finally, use of threes as a bitmask to represent the ith bit appears three times.
When the ith bit appears for the third time, one needs to update the ith bit of both ones and twos to 0. Then, the final answer would be the value of ones.
This approach also takes O(n) time but with no extra memory.
SOLUTIONS:
Setter's Solution Approach-1 - C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll elementFreq(ll arr[], int n)
{
unordered_map<int, int> mp;
for (int i = 0; i < n; i++)
mp[arr[i]]++;
for (auto x : mp)
if(x.second==1)
return x.first;
return 0;
}
int main()
{
ll t;
cin >> t;
while (t--) {
ll n;
cin >> n;
ll arr[n] = {0};
for(ll i = 0;i<n;i++)
cin>>arr[i];
cout<<elementFreq(arr, n)<<endl;
}
return 0;
}
Setter's Solution Approach-2 - C++
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sortAndFind( vector <ll> &A)
{
vector<ll> v=A;
sort(v.begin(),v.end());
for(int j=1; j<A.size(); j+=3)
if(!(v[j-1]==v[j] and v[j+1]==v[j]))
return v[j-1];
return v[A.size()-1];
}
int main()
{
ll t;
cin >> t;
while (t--)
{
ll n;
cin >> n;
vector<ll> v(n);
for (auto &x : v)
{
cin >> x;
}
ll ans = sortAndFind(v);
cout << ans << endl;
}
return 0;
}
Setter's Solution Approach-3a - C++
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll bitManipulate(vector<ll> &A)
{
ll n = A.size();
ll countBit[32] = {0};
ll result = 0;
for (ll i = 0; i < 32; i++)
{
for (ll j = 0; j < n; j++)
{
if ((A[j] >> i) & 1)
{
countBit[i]++;
}
}
result |= ((countBit[i] % 3) << i);
}
return result;
}
int main()
{
ll t;
cin >> t;
while (t--)
{
ll n;
cin >> n;
vector<ll> v(n);
for (auto &x : v)
{
cin >> x;
}
ll ans = bitManipulate(v);
cout << ans << endl;
}
return 0;
}
Setter's Solution Approach-3b - C++
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll bitMasking(vector<ll> &A) {
int ones = 0, twos = 0 ;
int common_bit_mask;
for( int i=0; i< A.size(); i++ )
{
twos = twos | (ones & A[i]);
ones = ones ^ A[i];
common_bit_mask = ~(ones & twos);
ones &= common_bit_mask;
twos &= common_bit_mask;
}
return ones;
}
int main()
{
ll t;
cin >> t;
while (t--)
{
ll n;
cin >> n;
vector<ll> v(n);
for (auto &x : v) {
cin >> x;
}
ll ans = bitMasking(v);
cout << ans << endl;
}
return 0;
}
Tester Vaibhav's Solution (Approach 1)- Python
from collections import Counter
T=int(input())
while(T>0):
N=int(input())
A=[int(i) for i in input().split()]
d=Counter(A)
ans=0
for key,value in d.items():
if(value!=3):
ans=key
break
print(ans)
T-=1
Tester Kabir's Solution (Approach 1) - Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
while (t-- > 0) {
int n = scanner.nextInt();
// Create a map, and map frequencies of each number.
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; ++i) {
int temp = scanner.nextInt();
// No need to create an array.
int val = map.getOrDefault(temp, 0);
// Gets the value of this key if present in the map, else 0.
map.put(temp, val + 1);
}
// Find the number which is present just once.
for (int key : map.keySet()) {
if (map.get(key) == 1) {
System.out.println(key);
break;
}
}
}
}
}