Flipkart Interview Question Software Engineer / Developers
@Aditya: His logic is correct and as he wrote:
"Traverse once again and print indices whose value is positive."
this will print all missing numbers in the array.
Here is the logic:
Scan through the array. Every time you encounter a number(call it N), make the number at index N negative(if it is not negative). Thus when whole array has been traversed, only indexes corresponding to missing numbers will be positive, which can be printed in another scan.
The basic trick is that all numbers are positive and by making numbers negative we are keeping track of all numbers visited. If negative numbers were allowed, the above trick wouldn't have worked.
@Aditya: His logic is correct and as he wrote:
"Traverse once again and print indices whose value is positive."
this will print all missing numbers in the array.
Here is the logic:
Scan through the array. Every time you encounter a number(call it N), make the number at index N negative(if it is not negative). Thus when whole array has been traversed, only indexes corresponding to missing numbers will be positive, which can be printed in another scan.
The basic trick is that all numbers are positive and by making numbers negative we are keeping track of all numbers visited. If negative numbers were allowed, the above trick wouldn't have worked.
problems with aravinds86 code.
1) First it does not detect duplicate.
2) it is not O(1) in space as the file has to be read in array. Also the array can be much much bigger than n in case the number of numbers not very large though in the range from 1 to 1M.
3) The ideal solution would be O(n) in space and O(n) time. In case the nubmer of numbers is very less compared to 1M we shall use HashMap, otherwise we can use an array of size 1M.
0(1) space and o(n) time
- aravinds86 October 16, 2010for(i = 1 to n){
t = a[i] > 0) ? a[i] : a[i]*-1;
if( a[t] > 0 )
a[t] = a[t]*-1;
}
Traverse once again and print indices whose value is positive.