Table of Contents
If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
In this post, we will see how to find number occurring odd number of times in the array.
Problem:
You are given a array of integer. All numbers occur even number of times except one. You need to find the number which occurs odd number of time. You need to solve it with o(n) time complexity and o(1) space complexity.
For example:
|
1 2 3 4 |
int array[] = new int[]{20, 40, 50, 40, 50, 20, 30, 30, 50, 20, 40, 40, 20}; Number which occurs odd number of times is : 50 |
Solution:
Solution 1: Use two for loops and compare elements:
This is brute force solution for this problem but it takes o(n*n) time complexity.
Solution 2 : Use Hashing
You can use key as number and count as value and whenever key is repeated , you can increment counter by 1.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
int getOddTimesElementHashing(int ar[]) { int i; HashMap<Integer,Integer> elements=new HashMap<Integer,Integer>(); for (i = 0; i < ar.length; i++) { int element=ar[i]; if(elements.get(element)==null) { elements.put(element, 1); } else elements.put(element, elements.get(element)+1); } for (Entry<Integer,Integer> entry:elements.entrySet()) { if(entry.getValue()%2==1) { return entry.getKey(); } } return -1; } |
but above solution takes o(n) of space complexity.
Solution 3: Use XOR operation:
You can do bitwise XOR operation for all elements and it will give you element which occurs odd number of times in the end.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
int getOddTimesElement(int ar[]) { int i; int result = 0; for (i = 0; i < ar.length; i++) { result = result ^ ar[i]; } return result; } |
Above algorithms solves the problem with O(n) time complexity and o(1) space complexity and this is best solution for above program.
Java program to find the number occurring odd number of times in an array:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
package org.arpit.java2blog; //Java program to find the element occurring odd number of times public class NumberOddTimesMain { int getOddTimesElement(int ar[]) { int i; int result = 0; for (i = 0; i < ar.length; i++) { // XOR operation result = result ^ ar[i]; } return result; } public static void main(String[] args) { NumberOddTimesMain occur = new NumberOddTimesMain(); int array[] = new int[]{20, 40, 50, 40, 50, 20, 30, 30, 50, 20, 40, 40, 20}; System.out.println("Number which occurs odd number of times is : "+occur.getOddTimesElement(array)); } } |
|
1 2 3 |
Number which occurs odd number of times is : 50 |
