package com.thealgorithms.maths;

import java.util.Scanner;

/*
 * Find the 2 elements which are non repeating in an array
 * Reason to use bitwise operator: It makes our program faster as we are operating on bits and not
 * on actual numbers.
 */
public class NonRepeatingElement {

    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            int i, res = 0;
            System.out.println("Enter the number of elements in the array");
            int n = sc.nextInt();
            if ((n & 1) == 1) {
                // Not allowing odd number of elements as we are expecting 2 non repeating
                // numbers
                System.out.println("Array should contain even number of elements");
                return;
            }
            int[] arr = new int[n];

            System.out.println("Enter " + n + " elements in the array. NOTE: Only 2 elements should not repeat");
            for (i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }

            try {
                sc.close();
            } catch (Exception e) {
                System.out.println("Unable to close scanner" + e);
            }

            // Find XOR of the 2 non repeating elements
            for (i = 0; i < n; i++) {
                res ^= arr[i];
            }

            // Finding the rightmost set bit
            res = res & (-res);
            int num1 = 0, num2 = 0;

            for (i = 0; i < n; i++) {
                if ((res & arr[i]) > 0) { // Case 1 explained below
                    num1 ^= arr[i];
                } else {
                    num2 ^= arr[i]; // Case 2 explained below
                }
            }

            System.out.println("The two non repeating elements are " + num1 + " and " + num2);
            sc.close();
        }
    }
    /*
     * Explanation of the code:
     * let us assume we have an array [1,2,1,2,3,4]
     * Property of XOR: num ^ num = 0.
     * 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. Our task is to find num1 and num2 from the result of 3 ^ 4 = 7. We need to
     * find two's
     * complement of 7 and find the rightmost set bit. i.e. (num & (-num)) Two's
     * complement of 7 is 001
     * and hence res = 1. There can be 2 options when we Bitise AND this res with
     * all the elements in our
     * array
     * 1. Result will come non zero number
     * 2. Result will be 0.
     * In the first case we will XOR our element with the first number (which is
     * initially 0)
     * In the second case we will XOR our element with the second number(which is
     * initially 0)
     * This is how we will get non repeating elements with the help of bitwise
     * operators.
     */
}