Lonely Integer HackerRank

 Problem Link:

https://www.hackerrank.com/challenges/one-week-preparation-kit-lonely-integer/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=preparation-kits&playlist_slugs%5B%5D=one-week-preparation-kit&playlist_slugs%5B%5D=one-week-day-two

https://www.hackerrank.com/challenges/lonely-integer/problem

Solution:

Approach 1: Using Collections.frequency() method

int a=0;

        for(int i=0;i<aa.size();i++){

            if(Collections.frequency(aa,aa.get(i))==1){

                a=aa.get(i);

                break;

            }

        }

 return a;

        

For unique elements, the frequency will be 1 only. So we will traverse the whole array and find the element with one frequency. 

Once we find it then we will store it in the integer variable and return it.

Time:O(N^2)[Collections.frequency() method is used. For every element, we will see frequency. In the worst case we will traverse the whole array and get the element at last.]

Space:O(N)[ArrayList is Used]

-----------------------------------------------------------------------------------------------------------------------------

Approach 2:

Using Sets

        HashSet<Integer>set=new HashSet<Integer>();

        set.addAll(aa);//add whole collection

        

        

        int sum=0;

        for(int a:set){

            sum=sum+a;

        }

        

        sum=sum*2;

        int sum1=0;

        for(int i=0;i<aa.size();i++){

            sum1=sum1+aa.get(i);

        }

        return sum-sum1;

Here We will use a HashSet which will store every element once irrespective

of their repetitions in given ArrayList.

After that, we will sum up the set and give ArrayList also.

Now we will twice the sum of a set

in a means that every element will be doubled including the unique element too, and store it

in variable sum1.

And now we will make the difference between sum1 and sum of given ArrayList, which ultimately

eliminates the duplicates and their sum and we will be left with one unique element.  

Time:O(N)[Using Set]

Space:O(N) 

--------------------------------------------------------------------------------

Approach 3:

Here we will take xor of all the elements of the array.

Using XOR means that for the same value the cor will return 0 while when 0 will be xor

to unique value, it will return unique value.

Eg arr={1,1,2,2,0,0,7,6,6}

int xor=0;

1^0=1 ->> 1^1=0 --> 0^2=2 --> 2^2=0 --> 0^0=0 --> 0^0=0 --> 0^7=7 --> 7^6=1 ---> 1^6=7

Hence 7 will be output.

public static int lonelyinteger(List<Integer> a) {

        int res=0;

        for(int i=0;i<a.size();i++){

            res=res^a.get(i);

        }

        return res;

    }

Time:O(N) [Traversing the whole array once]

Space:O(1) [No additional space is used]

----------------------------------------------------------------------------------

Thanks For Reading.😇

"Share Further To Increase Knowledge.😊"