Interested to Buy Any Domain ? << Click Here >> for more details...
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.
- 21 Answers
- 65068 Views
- ABC, eBay, Goldman Sachs, Google, HUP, Microsoft, TATA, I also Faced
- E-Mail Answers
Answers were Sorted based on User's Feedback
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 ? | 55 Yes | 13 No |
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 ? | 29 Yes | 7 No |
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 | 12 No |
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 ? | 23 Yes | 9 No |
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 ? | 19 Yes | 14 No |
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 |
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 |
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 |
Answer / ronstar luan
We need not sort this array and we need save space.
{2, 4, 5, 1, 3} m=2;
{2, 2, 5, 1, 3} m=4;
{2, 2, 5, 4, 3} m=1;
{1, 2, 5, 4, 3} m=2;
--------------------
{1, 2, 5, 4, 3} m=5;
{1, 2, 5, 4, 5} m=3;
{1, 2, 3, 4, 5} m=5;
--------------------
| Is This Answer Correct ? | 4 Yes | 3 No |
int main() { int x=10; printf("x=%d, count of earlier print=%d", x,printf("x=%d, y=%d",x,--x)); getch(); } ================================================== returns error>> ld returned 1 exit status =================================================== Does it have something to do with printf() inside another printf().
main() { int i, j; scanf("%d %d"+scanf("%d %d", &i, &j)); printf("%d %d", i, j); } a. Runtime error. b. 0, 0 c. Compile error d. the first two values entered by the user
main() { { unsigned int bit=256; printf("%d", bit); } { unsigned int bit=512; printf("%d", bit); } } a. 256, 256 b. 512, 512 c. 256, 512 d. Compile error
main() { char s[ ]="man"; int i; for(i=0;s[ i ];i++) printf("\n%c%c%c%c",s[ i ],*(s+i),*(i+s),i[s]); }
How to use power function under linux environment.eg : for(i=1;i<=n;i++){ pow(-1,i-1)} since it alerts undefined reference to 'pow'.
void main() { int const * p=5; printf("%d",++(*p)); }
3 Answers Infosys, Made Easy, State Bank Of India SBI,
main() { char *p = “ayqm”; printf(“%c”,++*(p++)); }
29 Answers IBM, TCS, UGC NET, Wipro,
#include<stdio.h> main() { struct xx { int x=3; char name[]="hello"; }; struct xx *s=malloc(sizeof(struct xx)); printf("%d",s->x); printf("%s",s->name); }
main() { 41printf("%p",main); }8
Finding a number which was log of base 2
main() { float me = 1.1; double you = 1.1; if(me==you) printf("I love U"); else printf("I hate U"); }
how to check whether a linked list is circular.
C Code 
