- Given an array of integer containing positive numbers.
- All number in an array is occurring even number of times except one number.
- We would like to find the number which occurs odd number of times.
- Let us understand the problem statement with examples.
- int example1[] = { 1, 1, 2, 2, 3, 4, 4 };
- int example2[] = { 10, 10, 10, 11, 11, 11, 11};
- int example3[] = { 2, 2, 4, 4, 5 };
- In example1, numbers 1,2,4 occurs even number of times and 3 occurs odd times
- In example2, numbers 10 occurs odd number of times and 11 occurs even number of times.
Algorithm: find number occurring odd number of times in an array (java)
- We will use the properties of XOR gate.
- Truth table of “Exclusive-OR” or XOR gate is :
X | Y | Output |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
- Let us apply XOR gate on example1 = { 1, 1, 2, 2, 3, 4, 4 }
- OddNumber = 1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 4 ^ 4
- OddNumber = (1 ^ 1) ^ (2 ^ 2) ^ 3 ^ (4 ^ 4)
- OddNumber = 0 ^ 0 ^ 3 ^ 0
- OddNumber = 3.
Program: find the number occurring odd number of times in an array
package org.learn.arrays; import java.util.Arrays; public class NumberOddTimes { public static void main(String[] args) { int example1[] = { 1 , 1 , 2 , 2 , 3 , 4 , 4 }; String array = Arrays.toString(example1); int oddNumber = getOddNumber(example1); System.out.printf( "1. Number occur odd times in %s is: %d" , array, oddNumber); int example2[] = { 10 , 10 , 10 , 11 , 11 , 11 , 11 }; array = Arrays.toString(example2); oddNumber = getOddNumber(example2); System.out.printf( "\n2. Number occur odd times in %s is: %d" , array, oddNumber); int example3[] = { 2 , 2 , 4 , 4 , 5 }; array = Arrays.toString(example3); oddNumber = getOddNumber(example3); System.out.printf( "\n3. Number occur odd times in %s is: %d" , array, oddNumber); } private static int getOddNumber( int [] elements) { int oddNumber = elements[ 0 ]; int length = elements.length; for ( int index = 1 ; index < length; index++) { oddNumber ^= elements[index]; } return oddNumber; } } |
Output: number occurring odd number of times in integer array (java)
1. Number occur odd times in [1, 1, 2, 2, 3, 4, 4] is: 3 2. Number occur odd times in [10, 10, 10, 11, 11, 11, 11] is: 10 3. Number occur odd times in [2, 2, 4, 4, 5] is: 5 |