Blog on algorithms, puzzles, programming .... musings of a computer engineer.
n similar elements in an array
Given an array of 2n elements of which n elements are same and the remaining n elements are all different. Write a C program to find out the value which is present n times in the array. (In linear time, constant extra space)
1 comment:
Solution 1
If extra memory can be used, then simply use a lookup table or hash_set, where the count is updated. O(N)
Solution 2
Sort , O(N log(N))
Post a Comment