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 main() { if(~0 == (unsigned int)-1) printf(“You can answer this if you know how values are represented in memory”); }

1 Answers  

void main() { static int i=5; if(--i){ main(); printf("%d ",i); } }

1 Answers  

Write a Program that Inputs 10 Numbers in an Array and Show the Maximum Number

2 Answers   Ace Info,

main() { printf("\nab"); printf("\bsi"); printf("\rha"); }

3 Answers  

void main() { printf(“sizeof (void *) = %d \n“, sizeof( void *)); printf(“sizeof (int *) = %d \n”, sizeof(int *)); printf(“sizeof (double *) = %d \n”, sizeof(double *)); printf(“sizeof(struct unknown *) = %d \n”, sizeof(struct unknown *)); }

1 Answers  

#include <stdio.h> #define a 10 main() { #define a 50 printf("%d",a); }

2 Answers  

main() { int c=- -2; printf("c=%d",c); }

1 Answers   TCS,

Write a prog to accept a given string in any order and flash error if any of the character is different. For example : If abc is the input then abc, bca, cba, cab bac are acceptable, but aac or bcd are unacceptable.

5 Answers   Amazon, Microsoft,

how can i search an element in an array

2 Answers   CTS, Microsoft, ViPrak,

main() { int i =10, j = 20; clrscr(); printf("%d, %d, ", j-- , --i); printf("%d, %d ", j++ , ++i); } a. 20, 10, 20, 10 b. 20, 9, 20, 10 c. 20, 9, 19, 10 d. 19, 9, 20, 10

4 Answers   HCL,

main() { extern int i; i=20; printf("%d",i); }

1 Answers   Value Labs,

Given only putchar (no sprintf, itoa, etc.) write a routine putlong that prints out an unsigned long in decimal.

6 Answers   Fusion Systems GmbH,