Interview Questions And Answers 
-
Given an array t[100] which contains numbers between 1 and 99. Return the duplicated value. Try both O(n) and O(n-square).
12,148 Views |
(13 votes, avg: 4)
Loading ...
Answers »
Our Sponsors
Our Sponsors
Traverse array to compute sum.
Subtract 99*100/2, the sum of integers between 1 and 99)
If we want to do it in O(n), we can use hashing woith hash function as %100.
If >1 values hash to the same bucket, then they are duplicates
The above solution (summation of array) is wrong as I could have a completely different set of number between 1 & 99 in a repeating fashion which would give me a sum of 1..99. Hence the program would say there is n duplication but in fact there is.
O(n) algo is …
create a new array of b[100] elements..initialise all elements to 0
int b[100];
for ( i=0;i<100;i++)
b[i]=0;
int tm;
for ( i=0;i<100;i++)
{ tm=t[i] ;
if b[tm]== 1;
return(o);
else b[tm]=1;
}
printf(” there is no duplication”);
O(n square ) … just sort all numbers and check if two consecutive numbers are same by traversing the sorted array..
Your’s is a good solution vira, and it would work for the general case of an array of size 100, but with only 99 distinct numbers, find the repeat. But the question spacifically tells us that they are numbered 1 to 99.
Thus, I think that hottypete’s answer is the correct on b/c it only makes one pass, and only requires an extra variable. So, code wise:
given array a: int a[100]
int sum = (99 * 100) / 2; // sum of numbers from 1 to 99
int total = 0;
for(int i = 0; i
NOOO! Hottypete’s answer is wrong.
Imagine you have two elements of 1 and 97, the sum will be equal to having two elements of 49. Unless the questions indicates that all number is unique except for the duplicated number, the sum method does not work.
well…add all the numbers you get from your array of 100. the sum of 1…99 is 4950, (remember sum of the first n natural numbers), subtract 4950 from the sum we get and eureka, we have the duplicate number as the answer!
I think best solution will be to count the occurences of individual integers.
For that we can have a count array (int count[100] = {0}) .. initilize all variables to ZERO. Then travel the given array & keep on incrementing the value at the index if a value of that index has found.. after traversing the whole arrary we will have occurence count for each & every member .. wich can further be used to find the repititive or unique entries.
For O(n^2)
int DuplicateNumber(int *array,int size)
{
for(int i=0;i
Hey guys.. you all are good in algo.. but some of you who suggest keeping track of occurence and creating one more array is not really good. think what if it contain (n > 2^16-1)
so i think goos solution is summation when sply it is given that
it only contain integer from 1 to (n-1) each once and one of them is repeated.
I think its a better idea to sort the numbers in assending order … If two consecutive numbers are the same … voila … thats the answer.
The algo can be somthing like this:
int array[100] = {1 … 99};
int sorted[100];
sorted = sort(array); //in assending
for(int i = 0; i
I think answer 5 is the best.
if anybody thinks than sum will solve the issue. then please solve my this problem.
int arr[100] = 1; // support this assign value of 1 to all elements in array.
now find the duplicate from your algo..
“Subtract 99*100/2, the sum of integers between 1 and 99″
if anybody has answer to my question, please email this to n_K_goyal@yahoo.com.
Thanks in advance.
I think the best answer is to create a corresponding array of equal size. Then loop through the first array and for each number in the first array, assign a 1 to the “index” of that number in the second array. When you hit an entry in the second array that already has been assigned a 1 then you know it is a duplicate.
This is generally faster because in the best case the duplicate is the first and second value of the array and you are done almost immediately. The worst case is one pass through the original array.
Summing the values always requires a full table scan and therefore on average will be slower over a random distribution of numbers in the first array.
The Num is : Summation of fist n numbers - Summation of all array nums , in which 99 are unique n one is duplicate.
i.e dup = n(n+1) /2 - sum( a[1] to a[n] )
where n = 100 in above ques
sry n = 99
Solution 1: (O(Log N)) - Assumption the input array is sorted, ascending and no elements are missing
if you look at the array index and the value, the difference will be 1, if there are no duplicates. If the element contains duplicate, that element and from that element forward the difference would be 0. So the solution is to find the duplicateusing Binary Search, dividing the array in to two and checking for the difference.
Solution 2: O(N)
I think you can pick the last value in this case 99, then, do (99*100)/2. Then sum up the values in the array. Get the difference between the two and you will get the duplicate value.
Put the values into the set. The first break should be the duplicata values. O(n) will be the worst case scenario.
if summation is the answer, then:
int arr[5] = {1,2,3,4,4};
then which is duplicate
This is a pigeon hole problem.
Basically each number goes in exactly one spot in the array. For example, 42 goes in array[41]. So if 42 appears twice in the array then both of them are going to try to get into array[41].
Therefore walk the array and pigeon-hole every number you see, the duplicate will get pigeon-holed twice.
Solution:
int PigeonHole(int a[100])
{
for(int i = 0; i
This is a problem for which the bitmap datastructure is ideal. This datastructure is illustrated in “Programming Pearls” by Jon Bentley.
Here is the solution.
1. Initialize a bitmap (an array) with size=100. Initialize all entries to zero.
2. Loop through the array and for every number, increment its index value in the bitmap by 1.
3. Loop through the bitmap array and print out all indices whose entry is greater than 1.
Here is the Python code for this.
def duplicate(l):
“”" Return numbers which are duplicated in the given list “”"
# Initialize a bitmap to zeros
bitmap = [0]*len(l)
# Traverse list and for a number increment its bit
# index by 1, if already 1 count it as duplicate.
dups = []
for num in l:
bitmap[num] += 1
# Loop through bitmap and print all numbers whose
# count is more than 1
for x in range(len(bitmap)):
if bitmap[x]>1:
dups.append(x)
return dups
calculate the sum in 1 traversal…..
lets say we get S.
now find diff= 4950-S
so 100-(4950-S) gives u the value of the element repeated…
correct me if i am wrong….
1. The summation method will work only if there is only 1 duplicate, for more than 1 duplicate the sum will still match.
eg= 2,2,3,3 sum =10 which is same as 1,2,3,4 sum =10
2. The argument that (N-1)-(summation - (a[0]+a[1]+..a[n-1]) will give the duplicate number is also wrong.
The difference:
(summation - (a[0]+a[1]+..a[n-1]) just gives the difference between duplicate number and missing number.
eg: 1,2,2,3,4
array sum=12
actual sum of 5 nos = 15
Difference = 15-12=3
Subtract from n-1 , we get 5-3 = 2
Duplicate number 2 is correct , just by chance.
now take,
array as 1,1,2,3,5,
actual sum = 12 , again we will get 2 as the duplicate number, which is wrong.
Further the method suggested in which we do hashing / pigeon hole will work for any situation (one or more duplicates) but requires O(n) of storage.
As suggested by anand , the bitmap approach of bentley can be used to reduce the storage size
copy whole array in hash table one by one …..and count with every value….if value repeated increment the count
in next step….
search the count value greater then 1……
return it……that is repeated in list…
complexcity is o(n)
Leave an Answer/Comment