Given an array of size N in which every number is between 1
and N, determine if there are any duplicates in it. You are
allowed to destroy the array if you like.




Answers were Sorted based on User's Feedback



Given an array of size N in which every number is between 1 and N, determine if there are any dupli..

Answer / zhixingren

The following algorithm works. It is O(n) and no extra
storage required
public static bool HaveDuplicate(int[] nums)
{
for (int i = 0; i < nums.Length; i++)
{
int tmp = nums[i];
if (tmp < 0)
tmp = -tmp;

if (nums[tmp - 1] < 0)
{
return true;
}
else
{
nums[tmp - 1] = -nums[tmp - 1];
}
}
return false;
}
}

Is This Answer Correct ?    50 Yes 11 No

Given an array of size N in which every number is between 1 and N, determine if there are any dupli..

Answer / ashutosh k

You can use intermediate step for count sort.

Take a new array B of size N, initialize all values to 0.
and then
for each i from 1 to N,
if((++B[A[i]]) > 1) - there are duplicates.

--- Time complexity O(n)

Is This Answer Correct ?    28 Yes 7 No

Given an array of size N in which every number is between 1 and N, determine if there are any dupli..

Answer / monika

the formula given for summation shud be (n*(n+1))/2

but it will solve the problem only if we have one duplicate.
if we have many duplicates then we can still get the
correct summation
for ex:
1 2 2 5 5

it has two duplicates but still total is 5*(5+1)/2=15

Is This Answer Correct ?    28 Yes 11 No




Given an array of size N in which every number is between 1 and N, determine if there are any dupli..

Answer / shri

#include<stdio.h>
void main()
{
int a[3],j,i,n;
clrscr();
printf("enter n");
scanf("%d",&n);
printf("enter els");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]==a[j])
printf("elements %d and %d are same",i+1,j+1);
}
}
}

Is This Answer Correct ?    19 Yes 7 No

Given an array of size N in which every number is between 1 and N, determine if there are any dupli..

Answer / raghuram

guys..sort the array using quicksort..and check adjacent
elements..u can know there are duplicates or
not..complexity-O(nlogn)+n-1

Is This Answer Correct ?    20 Yes 10 No

Given an array of size N in which every number is between 1 and N, determine if there are any dupli..

Answer / anyone

If you mark places with zero, you will lose the original
value in that place which, eventually, leads to errors...

Assume an array starting as: 1-5-5-...

After first step array would be: 1-0-5-...

You will get stuck at the second step since every element
that you marked with zero will lead to the position 0.

Converting to negative makes more sense...

Is This Answer Correct ?    14 Yes 9 No

Given an array of size N in which every number is between 1 and N, determine if there are any dupli..

Answer / miraj

When its given you are allowed to destroy the array..do
think in that direction..


Read the first element go to that position, read that
position and mark it zero.. keep doing so...

If at any place we find zero.. that means array contains
duplicate.

Is This Answer Correct ?    18 Yes 14 No

Given an array of size N in which every number is between 1 and N, determine if there are any dupli..

Answer / michael

hey scrubs, use a hash map

loop through array {
if(hash[x] == x] return true// is dupe
else hash.add(x,x);
}

max O(n)

Is This Answer Correct ?    6 Yes 4 No

Given an array of size N in which every number is between 1 and N, determine if there are any dupli..

Answer / somebody

@Michael

Moron you are using extra space there.that is obvious.using
extra space many tough problems can be solved.without extra
space tell some better methods.

Is This Answer Correct ?    5 Yes 3 No

Given an array of size N in which every number is between 1 and N, determine if there are any dupli..

Answer / sankalan

sum all those no. say you get x
say there is a b (repeated) in place of a
so a-b = n(n+1)/2 - x=m(say)
sum the squares of those nos
say you get y
a^2-b^2 = 1/6(n+1)(2n+1)-y=n(say)
(a^-b^2)/(a-b)=a+b=m/n
to get a ((a+b)+(a-b))/2
to get b ((a+b)-(a-b))/2

Is This Answer Correct ?    1 Yes 0 No

Post New Answer



More C Code Interview Questions

main() { signed int bit=512, mBit; { mBit = ~bit; bit = bit & ~bit ; printf("%d %d", bit, mBit); } } a. 0, 0 b. 0, 513 c. 512, 0 d. 0, -513

3 Answers   HCL, Logical Computers,


write a program in c language to get the value of arroy keys pressed and display the message which arrow key is pressed?

1 Answers  


main() { register int a=2; printf("Address of a = %d",&a); printf("Value of a = %d",a); }

3 Answers  


main(int argc, char **argv) { printf("enter the character"); getchar(); sum(argv[1],argv[2]); } sum(num1,num2) int num1,num2; { return num1+num2; }

1 Answers  


How can u say that a given point is in a triangle? 1. with the co-ordinates of the 3 vertices specified. 2. with only the co-ordinates of the top vertex given.

1 Answers  






why java is platform independent?

12 Answers   Wipro,


main() { void swap(); int x=10,y=8; swap(&x,&y); printf("x=%d y=%d",x,y); } void swap(int *a, int *b) { *a ^= *b, *b ^= *a, *a ^= *b; }

2 Answers  


Cluster head selection in Wireless Sensor Network using C programming language.

0 Answers  


What are the following notations of defining functions known as? i. int abc(int a,float b) { /* some code */ } ii. int abc(a,b) int a; float b; { /* some code*/ }

1 Answers  


how to concatenate the two strings

1 Answers  


Given a spherical surface, write bump-mapping procedure to generate the bumpy surface of an orange

0 Answers  


Sir... please give some important coding questions asked by product companies..

0 Answers  






Categories