Software Architect
BAN USERyes! That can be done if there is any restriction on memory usage.
- Software Architect June 05, 2012There are many ways to solve this problem. Following ways can be used for this.
1) If change in position of numbers is allowed, then Sort the list of numbers and remove the duplicates. Sorting will require at least n*log(n) time if quick sort or merge sort is used.
2) Iterate through list n^2 times removing the duplicate elements by choosing a seed and then comparing that seed against each number. But this is not effient method.
3) Using hashing, we can map the numbers to some less number of bucket and then compare the numbers in each bucket and arrive at a list of unique number.
4) Take bit map of number. Because we know that it is 32 bit integer, we require 2^32 bits to represent the bit map image and initialize the image to all 0. On first occurrance of number, set corresponding bit of bit map to 1. If number appears again then remove it from list. This will be O(1), but requires constant memory space i.e. 2^32 bits = 2^29 bytes = 512 Megabytes.
Because, bit map will be used. Which will be of fixed length. In this case each bit will represent presence or absence of the number. The memory usage of 512 MB is extra memory that is required for the processing apart from the array of numbers.
- Software Architect June 05, 2012