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.

#define DIM( array, type) sizeof(array)/sizeof(type) main() { int arr[10]; printf(“The dimension of the array is %d”, DIM(arr, int)); }

1 Answers  

main() { int i=_l_abc(10); printf("%d\n",--i); } int _l_abc(int i) { return(i++); }

2 Answers  

Finding a number which was log of base 2

1 Answers   NetApp,

Given n nodes. Find the number of different structural binary trees that can be formed using the nodes.

16 Answers   Aricent, Cisco, Directi, Qualcomm,

How can you relate the function with the structure? Explain with an appropriate example.

0 Answers  

Write a function to find the depth of a binary tree.

13 Answers   Adobe, Amazon, EFI, Imagination Technologies,

main( ) { void *vp; char ch = ‘g’, *cp = “goofy”; int j = 20; vp = &ch; printf(“%c”, *(char *)vp); vp = &j; printf(“%d”,*(int *)vp); vp = cp; printf(“%s”,(char *)vp + 3); }

1 Answers  

How to swap two variables, without using third variable ?

104 Answers   AB, ADP, BirlaSoft, Cisco, Cygnet Infotech, HCL, Hewitt, Honeywell, HP, IBM, Infosys, Manhattan, Microsoft, Mobius, Percept, Satyam, SofTMware, TCS, Wipro, Yamaha,

#define assert(cond) if(!(cond)) \ (fprintf(stderr, "assertion failed: %s, file %s, line %d \n",#cond,\ __FILE__,__LINE__), abort()) void main() { int i = 10; if(i==0) assert(i < 100); else printf("This statement becomes else for if in assert macro"); }

1 Answers  

main() { int i=-1,j=-1,k=0,l=2,m; m=i++&&j++&&k++||l++; printf("%d %d %d %d %d",i,j,k,l,m); }

1 Answers  

write a program for area of circumference of shapes

0 Answers  

Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it.

9 Answers   Microsoft,