One Odd Occurring

Easy
0/40
Average time to solve is 13m
profile
Contributed by
26 upvotes
Asked in companies
Nagarro SoftwareCapegemini Consulting India Private LimitedJUSPAY

Problem statement

Given an array ‘ARR’ of ‘N’ integers, where all the elements occur an even number of times and only one number occurs an odd number of times.


Find and return the number which occurs an odd number of times.


For example: 
'N' = 5, 'ARR' = [1, 2, 3, 2, 3]
Output: 1

Except for number 1, all numbers occur an even number of times.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer, 'N', representing the size of the array.

The second line contains 'N' space-separated integers.
Output format : 
The only line contains a single integer representing the number occurring odd number of times.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Sample Input 1 :
9
4 5 6 5 6 9 9 4 4
Sample Output 1 :
4
Explanation Of Sample Input 1 :
5, 6, and 9 occur an even number of times, and only 4 occur odd number of times.
Sample Input 2 :
5
1 1 1 1 1
Sample Output 2 :
1
Constraints :
1 <= 'N' <= 10^5

1 <= 'ARR[i]' <= 10^5

Time Limit: 1 sec
Hint

Can we try brute force?

Approaches (3)
Brute Force

Approach: 

 

We will run two nested loops and count the occurrence of every element.

If at any moment, we are getting the count as odd, we will just print that element.
 

Algorithm :  

 

  • For i = 0 to ‘N’
    • Initialize ‘count’ variable as 0
    • For j = 0 to ‘N’
      • If ‘ARR[j]’ is equal to ‘ARR[i]’
        • Increase ‘count’
    • If the ‘count’ is odd, return the ‘ARR[i]’

 

Time Complexity

O(N^2), Where ‘N’ size of the array.

As we are checking for each of the number in the array and for each check, we are again iterating the whole array to find the frequency, the time complexity will be O(N^2)

Space Complexity

O(1).


We are only using a single variable to store count, the space complexity will be O(1).

Code Solution
(100% EXP penalty)
One Odd Occurring
Full screen
Console