Find the number occurring odd number of times in an array

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:

Was this post helpful?

Leave a Reply

Your email address will not be published. Required fields are marked *