|
| 1 | +package Maths; |
| 2 | +import java.util.Scanner; |
| 3 | + |
| 4 | +/* |
| 5 | + * Find the 2 elements which are non repeating in an array |
| 6 | + * Reason to use bitwise operator: It makes our program faster as we are operating on bits and not on |
| 7 | + * actual numbers. |
| 8 | + */ |
| 9 | +public class NonRepeatingElement { |
| 10 | + |
| 11 | + public static void main(String[] args) { |
| 12 | + |
| 13 | + Scanner sc = new Scanner(System.in); |
| 14 | + int i, res = 0; |
| 15 | + System.out.println("Enter the number of elements in the array"); |
| 16 | + int n = sc.nextInt(); |
| 17 | + if((n & 1) == 1) |
| 18 | + { |
| 19 | + //Not allowing odd number of elements as we are expecting 2 non repeating numbers |
| 20 | + System.out.println("Array should contain even number of elements"); |
| 21 | + return; |
| 22 | + } |
| 23 | + int arr[] = new int[n]; |
| 24 | + |
| 25 | + System.out.println("Enter "+n+" elements in the array. NOTE: Only 2 elements should not repeat"); |
| 26 | + for(i = 0; i <n;i++){ |
| 27 | + arr[i] = sc.nextInt(); |
| 28 | + } |
| 29 | + |
| 30 | + try{ |
| 31 | + sc.close(); |
| 32 | + }catch(Exception e){ |
| 33 | + System.out.println("Unable to close scanner"+e); |
| 34 | + } |
| 35 | + |
| 36 | + //Find XOR of the 2 non repeating elements |
| 37 | + for(i = 0 ; i < n; i++) |
| 38 | + res^=arr[i]; |
| 39 | + |
| 40 | + //Finding the rightmost set bit |
| 41 | + res = res & (-res); |
| 42 | + int num1=0,num2=0; |
| 43 | + |
| 44 | + for(i = 0 ; i < n; i++){ |
| 45 | + if((res & arr[i]) > 0)//Case 1 explained below |
| 46 | + num1^=arr[i]; |
| 47 | + else |
| 48 | + num2^=arr[i];//Case 2 explained below |
| 49 | + |
| 50 | + } |
| 51 | + |
| 52 | + System.out.println("The two non repeating elements are "+num1+" and "+num2); |
| 53 | + |
| 54 | + } |
| 55 | + |
| 56 | + /* |
| 57 | + Explanation of the code: |
| 58 | + let us assume we have an array [1,2,1,2,3,4] |
| 59 | + Property of XOR: num ^ num = 0. |
| 60 | + If we XOR all the elemnets of the array we will be left with 3 ^ 4 as 1 ^ 1 and 2 ^ 2 would give 0. |
| 61 | + Our task is to find num1 and num2 from the result of 3 ^ 4 = 7. |
| 62 | + We need to find two's complement of 7 and find the rightmost set bit. i.e. (num & (-num)) |
| 63 | + Two's complement of 7 is 001 and hence res = 1. |
| 64 | + There can be 2 options when we Bitise AND this res with all the elements in our array |
| 65 | + 1. Result will come non zero number |
| 66 | + 2. Result will be 0. |
| 67 | + In the first case we will XOR our element with the first number (which is initially 0) |
| 68 | + In the second case we will XOR our element with the second number(which is initially 0) |
| 69 | + This is how we will get non repeating elements with the help of bitwise operators. |
| 70 | + */ |
| 71 | +} |
0 commit comments