Question

Find the number occuring odd number of times in a given array of size 'n'

Answer 1

Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time & constant space.

Examples :

Input : arr = {1, 2, 3, 2, 3, 1, 3} Output : 3 Input : arr = {5, 7, 2, 7, 5, 2, 5} Output : 5

A Simple Solution is to run two nested loops. The outer loop picks all elements one by one and inner loop counts number of occurrences of the element picked by outer loop. Time complexity of this solution is O(n2).