Objective: Given a array of integers, in which every elements occurs even number of times except one number which occurs add number of times. Find out that number.
Example:
int[] A = { 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7 };
Element appearing add number of times: 5
Approach:
we know that A XOR A = 0 so numbers appearing even number of times will be cancelled out and remaining element will the number which is appearing odd number of times.
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class OddOccuringNumber { | |
| public static int findNumber(int [] A){ | |
| int x=0; | |
| for(int i=0;i<A.length;i++){ | |
| x= x^A[i]; | |
| } | |
| return x; | |
| } | |
| public static void main(String[] args) { | |
| int[] A = { 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7 }; | |
| System.out.println("Element appearing add number of times: " + findNumber(A)); | |
| } | |
| } |
Output:
Element appearing add number of times: 5
Code Does not work for this input : {2, 7, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2, 7, 4, 4};
Returns ‘6’ which is not even in the array.
Because your input has two numbers 3 and 5 which occurs odd number of times. Objective of problem is ” Given a array of integers, in which every elements occurs even number of times except one number which occurs add number of times”