Find the number occurring odd number of times in an array

Last updated on March 14th, 2017 at 11:14 am

Previous
Next

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:

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.

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.

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:

When you run above program, you will get below output:

Previous
Next

Join Our News Letter - Stay Updated

Subscribe to Awesome Java Content.

Add Comment

Join Our News Letter - Stay Updated

Subscribe to Awesome Java Content.
You can like our facebook page Java2blog