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

Answer / ashish

srry.....few mistakes in above soln.....


just add as many n(length of array) to an index as much it
has duplicates i.e. if array has size 7 and no. 5 is written
3 times then add 7 three times.so that after first loop
completion, you can just take division (a[5-1]/7 in this
case.so u got 3.also original data at a[5-1] cant be loss
bcoz u can just tak (a[5-1]%len) nd u get the original data)


//array is a[]
//len=length of array


for(i=0;i<len;i++)
{
b=a[i]%len;
a[b-1]=a[b-1]+len;
}
//printing output
for(i=0;i<len;i++)
{
cout<<i+1<<" occurs: "<<(a[i]/len)<<endl;
}

Answer / faykarta

I'm nearly 100% sure that the only way to do this without
allocating more space is to loop through the entire array
checking elements against each other. Because its an
iterative method it can be optimised for linear memory access.

consider:

for(i = 0; i < N; ++i)
{
for(j = i + 1; j < N; ++j)
{
if(array[i] == array[j])
{
//index look up avoided through compiler optimisation???
return true;
}
}
}
return false;

*(Cache Integrity)The optimisation could be made using
pointer arithmetic or iterator style traversal in C/C++ anyway.

You could perform a custom sort operation that throws out
but i think it will be about the same algorithmic complexity
with less linear memory access and more complex code....

consider: (havent tested this one)

for(i = 0; i < N; ++i)
{
j = array[i] - 1;
while(j != i)
{
//check
if(array[i] == array[j])
{
return true;
}
//swap
array[i] ^= array[j] ^= array[i] ^= array[j];
j = array[i] - 1;
}
}
return false;

Any thoughts on these?
I would stick with brute force method.

Answer / foobar

You can use a hashtable, populate the keys from 1 to n.

while you re reading, mark the number you read and increment
their values by 1. if if you see the same number again,
fail. that s a dup. runs in O(n).

or you can use bucket sort.

Answer / hitesh

#include<iostream>
using namespace std;
int main()
{
int a[5],j,temp,flag,i,s ;
cout<<"Enter the size of the array :";
cin>>s; // size

for( i=0;i<s;i++){
cout<<"Enter the "<<i+1<<" element :";
cin>>a[i];
}

for( int i=0;i<s;i++){
temp=a[i];
for(j=i+1;j<s;j++){

if(a[j]==temp)
{flag=1;
break;
}
}

}
if(flag==1){cout<<"Duplicacy is there !! The duplicate number is :"<<temp;
}
else
cout<<"No duplicate value";
return 0;

}

Answer / madhu h gopala

@arr = (6,7,4,1,9,8,7,1);
print scalar @arr;
%seen = map {$_ => 1} @arr;
print scalar keys %seen

If the size of the array varies then there are duplicates

Answer / ashish

just add as many n(length of array) to an index as much it
has duplicates i.e. if array has size 7 and no. 5 is written
3 times then add 7 three times.so that after first loop
completion, you can just take division (a[5-1]/7 in this
case.so u got 3.)


//array is a[]
//len=length of array


for(i=0;i<len;i++)
{
b=a[i]%len;
a[b-1]=a[b-1]+7;
}
//printing output
for(i=0;i<len;i++)
{
cout<<i+1<<" occurs: "<<(a[i]/7)<<endl;
}

Answer / someone

Answer # eight by Zhixingren has one issue
consider following case
[3,3,1,4,5]

Here after processing first number value at index 2 will be
negative and after processing second number it will become
positive again

so when we process index it will have positive value and
code will not detect duplicate.

Mark no as negative if it is not negative will solve the
problem.

Answer / yegullelew

I have tried it with c#. It is of O(2n)~O(n)
public bool tellIfDuplicate(params int[] nums)
{
for (int i = 0; i < nums.Length; i++)
{
if (nums[i] != i + 1)
{
int temp = nums[i];
nums[i] = nums[nums[i] - 1];
nums[nums[i] - 1] = temp;
}
}
for(int i=0;i<nums.Length;i++)
if(nums[i]!=i+1)
return true;
return false;
}

Answer / murugesh

If there are no duplicates, Sum of numbers should be equal
to (N(N+1))/2.

Otherwise, duplicate is present.

No duplicate:
------------

Say N = 5

{1,2,3,4,5}

5(6)/2 = 15

1+2+3+4+5 = 15

Therefore no duplicate.

Duplicate:
---------

{1,2,3,4,1}

Sum = 11

which is not equal to 15 (N(N+1)/2)

Therefore duplicate present.

void pascal f(int i,int j,int k) { printf(“%d %d %d”,i, j, k); } void cdecl f(int i,int j,int k) { printf(“%d %d %d”,i, j, k); } main() { int i=10; f(i++,i++,i++); printf(" %d\n",i); i=10; f(i++,i++,i++); printf(" %d",i); }

1 Answers  

main() { char *p = “ayqm”; char c; c = ++*p++; printf(“%c”,c); }

1 Answers  

write a simple calculator c program to perform addition, subtraction, mul and div.

0 Answers   United Healthcare, Virtusa,

Find the largest number in a binary tree

7 Answers   Infosys,

Finding a number which was log of base 2

1 Answers   NetApp,

why java is platform independent?

13 Answers   Wipro,

main() { int i; printf("%d",scanf("%d",&i)); // value 10 is given as input here }

2 Answers   IBM,

Is there any difference between the two declarations, 1. int foo(int *arr[]) and 2. int foo(int *arr[2])

1 Answers  

How we print the table of 3 using for loop in c programing?

7 Answers  

#include<stdio.h> int main() { int x=2,y; y=++x*x++*++x; printf("%d",y); } Output for this program is 64. can you explain how this output is come??

1 Answers  

struct point { int x; int y; }; struct point origin,*pp; main() { pp=&origin; printf("origin is(%d%d)\n",(*pp).x,(*pp).y); printf("origin is (%d%d)\n",pp->x,pp->y); }

1 Answers  

main() { char *str1="abcd"; char str2[]="abcd"; printf("%d %d %d",sizeof(str1),sizeof(str2),sizeof("abcd")); }

1 Answers