Redirecting to
NADOS


  Prev   Next

All Repeating Except One







Who is a true Optimist? Someone who figures that taking a step backward after taking a step forward is not a disaster; it's more like a cha-cha.

All Repeating Except One

Welcome Back Reader!

In this article we will discuss the next problem based on 'Bit Manipulation' i.e. 'All Repeating Except One'.
This is a very easy and an interesting problem.

Before you move any further, it is advised that you give this problem a fair try.
Let's jump to the problem.

Important Links : Problem Link, Solution Video Link

Understanding the problem:

In this problem you are given an array of numbers. All numbers occur twice in the array except one.
All you need to do is to find that number by traversing only once in the array and without using any extra space.



Sample Input: 5
23 27 23 17 17

Sample Output: 27
Why? Because in the given input array, 27 is the only value that occurs once.



For better understanding of the question, watch part of the video lecture.

Aproach:
Moving On:
  • The problem here deals with finding the non-repeating number in the input array wherein every other number repeats itself exactly twice.
  • Here we will use the property of XOR to get our result. Using this operator makes this problem very easy and interesting to solve.
  • The truth table of XOR clearly depicts that for same operands it returns 0 and for different operands it returns 1.
  • Similar properties are seen while dealing with decimal numbers using this operator.
  • As in binary, similar numbers give 0 on performing XOR operation between them, like 1 ^ 1 = 0 and 0 ^ 0 = 0.
  • Similarly in decimal, the same numbers give 0 on performing XOR operation like 5 ^ 5 = 0 (0101 ^ 0101 = 0000). Let's call this property P1.
  • Also any decimal number on performing XOR operation with 0 gives the number itself as result, like 5 ^ 0 = 5 (0101 ^ 0000 = 0101). Let's call this property P2.
  • One more thing to keep in mind is that the XOR operator is cumulative in nature i.e. say 5 ^ 3 ^ 5 is the same as 5 ^ 5 ^ 3. Let's call this property P3.
  • Now coming back to our problem as we know that every number repeated twice except our desired number, this implies that the XOR of the number with itself will lead to zero.
  • So if we take the XOR of the entire array then all the duplicates would get cancelled out and the one that will be remaining will be our desired result.

For example: XOR = (23 ^ 27 ^ 23 ^ 17 ^ 17)
= (23 ^ 23 ^ 27 ^ 17 ^ 17) using P3
= ((23 ^ 23) ^ 27 ^ (17 ^ 17))
= (0 ^ 27 ^ 0) using P2
= 27 using P1

For better understanding of the question, watch part of the video lecture.

Let's try to code this!

img
import java.io.*; import java.util.*; public class Main { public static void main(String[] args){ Scanner scn = new Scanner(System.in); int n = scn.nextInt(); int[] arr = new int[n]; for(int i = 0 ; i < n; i++){ arr[i] = scn.nextInt(); } int ans = 0; for(int i = 0 ; i < n; i++){ ans ^= arr[i]; } System.out.println(ans); } }
java; true";
Analysis
Time Complexity: O(n)

The time complexity for the function is linear as we are traversing on every element of the array.

Space Complexity: O(1)

The space complexity for the function is constant.

We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.

Trust me it will just get easier to understand after you have watched the solution video.
You can contact us via our website. Doubts, suggestions and feedback are always welcomed.
It is also advised that you follow the sequence of modules and questions which is there on our website.
Keep practicing more and more problems daily. Meditate enough on each step of each problem.

All Repeating Except One
Author: Nikita Aggarwal
 
Run
Id Name