Two Numbers With Odd Occurrences Geeks For Geeks
Problem Link:
https://practice.geeksforgeeks.org/problems/two-numbers-with-odd-occurrences5846/1/
Solution 1: Using XOR Operator
class Solution
{
public int[] twoOddNum(int arr[], int n)
{
int xor=0;
for(int i=0;i<arr.length;i++){
xor=xor^arr[i];
}
int sn=(xor&(~(xor-1)));
int sum1=0;
int sum2=0;
for(int i=0;i<arr.length;i++){
if((arr[i]&sn)!=0){
sum1=sum1^arr[i];
}
else{
sum2=sum2^arr[i];
}
}
int arr1[]=new int[2];
arr1[0]=Math.max(sum1,sum2);
arr1[1]=Math.min(sum2,sum1);
return arr1;
}
}
TIME:O(N)[GFG Time:0.9/7.1]
SPACE:O(N)[Array of size n is in usage]
AUXILLARY SPACE: More than O(1) and less than O(N) (Precisely: O(2+1) ie O(3))[Array of fixed size 2 is in usage (O(2)) and constants are used O(1)].
TOTAL TEST CASES:10035
APPROACH:
1. Here In question, it is given two numbers will be distinct while all others will be there with even frequency.
We know x^x=0
So all rest numbers when cor with themselves will give result as 0.
2. First we find out the xor of all the elements of the given array. And store it in res.
This res will be simply the xor of both distinct elements.
eg arr= {1,2,3,4,4,5,5,2,2,2,1,1,1,7}
frequency of 1->4
frequency of 2->4
frequency of 3->1
frequency of 4->2
frequency of 5->2
frequency of 7->1
For 1: 1^1=0 ---> 0^1=1 and in last --> 1^1=0
Similarly for 2,5,4, it will be 0 as an even number of times they are present.
At last res=3^7 ie
3 = 0011
7 = 0111
3^7= 0100
Here 3^7 will be 4.
3. Now we should understand that xor gives output as 1 when one input is 0 and another input is 1.
0^1 =1
So we need to divide the given array into two subarrays. Once subarray of the set bit as 1 and other of 0.
For that, we need to find out the last set bit in number ie xor of 2 distinct number of array, which is 4 in above example.
For 4 last set bit is at 3rd position from last. So we need to divide the given array elements in such a way that in their binary representation the 3 bit from the right should be either 0 or 1.
For that we follow a procedure.
xor=4(0100)
xor-1=3(0011)
~(xor-1)=~3(1100)
xor&~(xor-1)=(4&(~3)) ie
sn=0100& 1100= 0100
And now we need to divide using the array using this value or sn.
4. We take two-variable sum1 and sum 2 to initialize with 0.
If while traversing array we get arr[i]&sn as 0 it means last bit is not set and hence we put in group 1.
If while traversing array we get arr[i]&sn as not equal to 0 it means last bit is set so we put in group 2.
Later we have to take the xor of all elements of group 1 to find out the first unique element and xor of elements of group 2 to find out the second unique element.
5. To save some space instead of creating two subarrays and doing the xor of their elements later, We directly do the xor of elements present in then when we will traverse the array (which is meant to be divided) and store the result in sum1 and sum2.
6.arr= {1,2,3,4,4,5,5,2,2,2,1,1,1,7}
for(int i=0;i<arr.length;i++){
if(arr[i]&sn==0){ // last bit is not set
sum1=sum1^arr[i];
}
else{
sum2=sum2^arr[i];
}
}
Now we store these values in an array and return them.
7. Twist in this question is they want the first element of returning an array as a greater value than the second.
So for that we use Math.max(sum1,sum2) function and Math.min(sum1,sum2) function.
IN GIST
1. Find xor value of the array (It will be ultimately xor of both unique elements)
2. Find the last set bit and store in sn. Using :
a) xor &(~(xor-1))
3. Divide the given array into two subarrays. One of last bit as a set and one of last bit as unset.
4. Take the xor of elements of both arrays and store the values as sum1 and sum2.
5. Use returnarr[0]=Math.max(sum1, sum2) and returnarr[1]=Math.min(sum1,sum2).
6.return returnarr;
-----------------------------------------------------------------------------------------------------------------------------
Solution 2: Using HashMap
class Solution
{
public int[] twoOddNum(int arr[], int n)
{
HashMap<Integer,Integer>map=new HashMap<Integer,Integer>();
for(int i=0;i<arr.length;i++){
if(map.containsKey(arr[i])){
map.put(arr[i],map.get(arr[i])+1);
}
else
map.put(arr[i],1);
}
int index=0;
int arr1[]=new int[2];
for(int a:map.keySet()){
if((map.get(a)&1)!=0){
arr1[index++]=a;
}
}
if(arr1[0]<arr1[1]){
arr1[0]=arr1[0]^arr1[1];
arr1[1]=arr1[0]^arr1[1];
arr1[0]=arr1[0]^arr1[1];
return arr1;
}
else{
return arr1;
}
}
}
TIME:O(N)[GFG Time:1.6/7.1]
SPACE:O(N)[Array of size n is in usage]
AUXILLARY SPACE: More than O(1) and less than O(N) (Precisely: O(2+1) ie O(3))[Array of fixed size 2 is in usage (O(2)) and constants are used O(1)].
TOTAL TEST CASES:10035
Difference between both approaches:
This approach takes more time than the previous one because in this approach we are doing a search also. While traversing we are searching also whether that element is present in the map or not. The search in map takes constant time but then too it has some value due to which time now is 1.7 while earlier it was 0.9.
-------------------------------------------------------------------------------------------------------------------
"Thanks For Reading.😇"
"Share Further To Increase Knowledge Treasure.😊"
Comments
Post a Comment