Discussion:
Missing Number in an array
(too old to reply)
TUSHAR_MCA
2011-07-18 11:31:52 UTC
Permalink
Given an array of size n. It contains numbers in the range 1 to n.
Each number is present at least once except for 2 numbers. Find the
missing numbers ?
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
varun pahwa
2011-07-18 11:57:32 UTC
Permalink
make two equations as .
suppose numbers to be x,y
x + y = p = (n*(n+1))/2 - (sum of all elements of array).

x^2 + y^2 = q = (n*(n+1)*(2n+1))/6 - (sum of square of all elements of
array).

so 2*x*y can be calculated as (p^2 - q);

so, a quad equation is formed as you now (x + y) and (2*xy).

P.S. :: overflow is not handled.

Please comment.
Post by TUSHAR_MCA
Given an array of size n. It contains numbers in the range 1 to n.
Each number is present at least once except for 2 numbers. Find the
missing numbers ?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Varun Pahwa
B.Tech (IT)
7th Sem.
Indian Institute of Information Technology Allahabad.
Ph : 09793899112
Official Email :: rit2008017-***@public.gmane.org
Another Email :: varunpahwa.iiita-***@public.gmane.org

People who fail to plan are those who plan to fail.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
ashish mann
2011-07-18 12:09:54 UTC
Permalink
A little better way would be
x + y = p = (n*(n+1))/2 - (sum of all elements of array).
x * y = q = n! / (product of all elements of the array).

now solve the quadratic eqn.
z^2 - (sum of the roots)z + (product of the roots) = 0
Post by varun pahwa
make two equations as .
suppose numbers to be x,y
x + y = p = (n*(n+1))/2 - (sum of all elements of array).
x^2 + y^2 = q = (n*(n+1)*(2n+1))/6 - (sum of square of all elements of
array).
so 2*x*y can be calculated as (p^2 - q);
so, a quad equation is formed as you now (x + y) and (2*xy).
P.S. :: overflow is not handled.
Please comment.
Post by TUSHAR_MCA
Given an array of size n. It contains numbers in the range 1 to n.
Each number is present at least once except for 2 numbers. Find the
missing numbers ?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Varun Pahwa
B.Tech (IT)
7th Sem.
Indian Institute of Information Technology Allahabad.
Ph : 09793899112
People who fail to plan are those who plan to fail.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
Aashish Mann
Software Engineer
Vihaan Networks Ltd.,Gurgaon
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
ankit sambyal
2011-07-18 12:48:49 UTC
Permalink
@Ashish : Cud u plz highlight how to write code to solve a quadratic equation ?
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Dumanshu
2011-07-18 13:08:28 UTC
Permalink
Quadratic equation solver: just solve it the way we do on paper, take
coefficients as input and apply formula x = (-b+sqrt(b^2 - 4*a*c))/
2*a...
anything wrong with this?

And for the given problem, it says "atleast" once and not "exactly"
once. So, Ankit's solution of bit vector is the best one.
Post by ankit sambyal
@Ashish : Cud u plz highlight how to write code to solve a quadratic equation ?
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
ankit sambyal
2011-07-18 12:01:24 UTC
Permalink
1. Initialize a bit vector of size n.
2. For every no. set the corresponding bit vector.
3. Now scan through the bit vectors and get the missing numbers
corressponding to the unset bits in the bit vector.


Time complexity : O(n)
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
varun pahwa
2011-07-18 12:11:19 UTC
Permalink
The above solution will work if each other number is exactly once present.
but if that 's not true.
then 4 equations can be formed.
Assuming a,b repeated number where a may or may be equal to b.

then equations will be
x + y = a + b;
x^2 + y^2 = a^2 + b^2.
x.y = a.b
x^3 + y^3 = a^3 + b^3.
now 4 equations 4 variables can be solved.
Post by ankit sambyal
1. Initialize a bit vector of size n.
2. For every no. set the corresponding bit vector.
3. Now scan through the bit vectors and get the missing numbers
corressponding to the unset bits in the bit vector.
Time complexity : O(n)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Varun Pahwa
B.Tech (IT)
7th Sem.
Indian Institute of Information Technology Allahabad.
Ph : 09793899112
Official Email :: rit2008017-***@public.gmane.org
Another Email :: varunpahwa.iiita-***@public.gmane.org

People who fail to plan are those who plan to fail.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Aakash Johari
2011-07-18 12:13:18 UTC
Permalink
@varun: can you write the code for one?
Post by varun pahwa
The above solution will work if each other number is exactly once present.
but if that 's not true.
then 4 equations can be formed.
Assuming a,b repeated number where a may or may be equal to b.
then equations will be
x + y = a + b;
x^2 + y^2 = a^2 + b^2.
x.y = a.b
x^3 + y^3 = a^3 + b^3.
now 4 equations 4 variables can be solved.
Post by ankit sambyal
1. Initialize a bit vector of size n.
2. For every no. set the corresponding bit vector.
3. Now scan through the bit vectors and get the missing numbers
corressponding to the unset bits in the bit vector.
Time complexity : O(n)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Varun Pahwa
B.Tech (IT)
7th Sem.
Indian Institute of Information Technology Allahabad.
Ph : 09793899112
People who fail to plan are those who plan to fail.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Aakash Johari
2011-07-18 12:14:15 UTC
Permalink
Yes, you will have to write a quad eq. solver. It's easy to write.
Post by Aakash Johari
@varun: can you write the code for one?
Post by varun pahwa
The above solution will work if each other number is exactly once present.
but if that 's not true.
then 4 equations can be formed.
Assuming a,b repeated number where a may or may be equal to b.
then equations will be
x + y = a + b;
x^2 + y^2 = a^2 + b^2.
x.y = a.b
x^3 + y^3 = a^3 + b^3.
now 4 equations 4 variables can be solved.
Post by ankit sambyal
1. Initialize a bit vector of size n.
2. For every no. set the corresponding bit vector.
3. Now scan through the bit vectors and get the missing numbers
corressponding to the unset bits in the bit vector.
Time complexity : O(n)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Varun Pahwa
B.Tech (IT)
7th Sem.
Indian Institute of Information Technology Allahabad.
Ph : 09793899112
People who fail to plan are those who plan to fail.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
-Aakash Johari
(IIIT Allahabad)
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
varun pahwa
2011-07-18 12:27:18 UTC
Permalink
sorry that would not work. only it could work if each element is present
exactly once.
Post by Aakash Johari
Yes, you will have to write a quad eq. solver. It's easy to write.
Post by Aakash Johari
@varun: can you write the code for one?
Post by varun pahwa
The above solution will work if each other number is exactly once
present. but if that 's not true.
then 4 equations can be formed.
Assuming a,b repeated number where a may or may be equal to b.
then equations will be
x + y = a + b;
x^2 + y^2 = a^2 + b^2.
x.y = a.b
x^3 + y^3 = a^3 + b^3.
now 4 equations 4 variables can be solved.
Post by ankit sambyal
1. Initialize a bit vector of size n.
2. For every no. set the corresponding bit vector.
3. Now scan through the bit vectors and get the missing numbers
corressponding to the unset bits in the bit vector.
Time complexity : O(n)
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Varun Pahwa
B.Tech (IT)
7th Sem.
Indian Institute of Information Technology Allahabad.
Ph : 09793899112
People who fail to plan are those who plan to fail.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
-Aakash Johari
(IIIT Allahabad)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Varun Pahwa
B.Tech (IT)
7th Sem.
Indian Institute of Information Technology Allahabad.
Ph : 09793899112
Official Email :: rit2008017-***@public.gmane.org
Another Email :: varunpahwa.iiita-***@public.gmane.org

People who fail to plan are those who plan to fail.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Nishant Mittal
2011-07-18 12:31:24 UTC
Permalink
1.Calculate XOR of all the array elements.
2.XOR the result with all numbers from 1 to n =>x1
3.After 2nd step, all elements would nullify each other except 2 missing
elements(let x and y) and x1 will contain XOR of x and y
4.All the bits that are set in x1 will be set in either x or y. Get the
rightmost set bit from x1.
5.divide the elements of the array in two sets – one set of elements with
same bit set and other set with same bit not set. By doing so, you will get
x in one set and y in another set.
6.XOR all the elements of 1st set with the numbers between 1 to n which have
same bit set and XOR the 2nd set with the numbers between 1 to n which have
same bit not set. Now result of both set will have the desired result
Post by varun pahwa
sorry that would not work. only it could work if each element is present
exactly once.
Post by Aakash Johari
Yes, you will have to write a quad eq. solver. It's easy to write.
Post by Aakash Johari
@varun: can you write the code for one?
Post by varun pahwa
The above solution will work if each other number is exactly once
present. but if that 's not true.
then 4 equations can be formed.
Assuming a,b repeated number where a may or may be equal to b.
then equations will be
x + y = a + b;
x^2 + y^2 = a^2 + b^2.
x.y = a.b
x^3 + y^3 = a^3 + b^3.
now 4 equations 4 variables can be solved.
Post by ankit sambyal
1. Initialize a bit vector of size n.
2. For every no. set the corresponding bit vector.
3. Now scan through the bit vectors and get the missing numbers
corressponding to the unset bits in the bit vector.
Time complexity : O(n)
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Varun Pahwa
B.Tech (IT)
7th Sem.
Indian Institute of Information Technology Allahabad.
Ph : 09793899112
People who fail to plan are those who plan to fail.
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
-Aakash Johari
(IIIT Allahabad)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Varun Pahwa
B.Tech (IT)
7th Sem.
Indian Institute of Information Technology Allahabad.
Ph : 09793899112
People who fail to plan are those who plan to fail.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
ankit sambyal
2011-07-18 12:34:45 UTC
Permalink
@Nishant : If the array contains duplicate elements, ur algo will fail !!!
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
ankit sambyal
2011-07-18 12:31:46 UTC
Permalink
@varun : My solution does not fail if every other number is not
present exactly once.

If a bit is already set, if we again set it, there's no harm.. The
algo works perfectly f9..
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
SAMMM
2011-07-18 12:37:48 UTC
Permalink
#include<stdio.h>
int main()
{

int a[]={1,2,3,5,2}; // 2 isrepeated and 4 is missing
int i=0,x=0,j=0,bit;
while(i<5)
{
j^=i+1;j^=a[i];
i++;
}

bit=j&~(j-1); //set bits

i=0;j=0;

while(i<5)
{
if(bit&(i+1)) x^=(i+1); //two set are needed to iterate
else j^=(i+1); //two set are needed to iterate
i++;
}
i=0;
while(i<5)
{
if(bit&a[i]) x^=a[i]; //two set are needed to iterate
else j^=a[i]; //two set are needed to iterate
i++;
}

printf("%d %d",x,j);
return 0;
}

Hav a look .... The trick is in the set bit [ bit=j&~(j-1); //set
bits]
Post by TUSHAR_MCA
Given an array of size n. It contains numbers in the range 1 to n.
Each number is present at least once except for 2 numbers. Find the
missing numbers ?
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Nishant Mittal
2011-07-18 12:42:10 UTC
Permalink
@ankit...i m assuming that array of size n contains n-2 elements with 2
elements missing
Post by SAMMM
#include<stdio.h>
int main()
{
int a[]={1,2,3,5,2}; // 2 isrepeated and 4 is missing
int i=0,x=0,j=0,bit;
while(i<5)
{
j^=i+1;j^=a[i];
i++;
}
bit=j&~(j-1); //set bits
i=0;j=0;
while(i<5)
{
if(bit&(i+1)) x^=(i+1); //two set are needed to iterate
else j^=(i+1); //two set are needed to iterate
i++;
}
i=0;
while(i<5)
{
if(bit&a[i]) x^=a[i]; //two set are needed to iterate
else j^=a[i]; //two set are needed to iterate
i++;
}
printf("%d %d",x,j);
return 0;
}
Hav a look .... The trick is in the set bit [ bit=j&~(j-1); //set
bits]
Post by TUSHAR_MCA
Given an array of size n. It contains numbers in the range 1 to n.
Each number is present at least once except for 2 numbers. Find the
missing numbers ?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
ankit sambyal
2011-07-18 12:43:52 UTC
Permalink
@Nishant: Read the question carefully. It says "Each number is present
at least once except for 2 numbers".
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
ankit sambyal
2011-07-18 12:45:52 UTC
Permalink
Sry for the typo in my previous mail.
@Nishant: Read the question carefully. It says "Each number is present
at least once except for 2 numbers".
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Nishant Mittal
2011-07-18 12:53:28 UTC
Permalink
ok then 1st remove duplicates from the array in O(n) then apply my algo...
Post by ankit sambyal
@Nishant: Read the question carefully. It says "Each number is present
at least once except for 2 numbers".
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
SkRiPt KiDdIe
2011-07-18 13:03:07 UTC
Permalink
Nishant. Your algorithm works for finding repeated nos. in a [n+2] array
where [1-n] are present atleast once and the same number is not being
repeated twice.

Reanalyze the question.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Nishant Mittal
2011-07-18 13:10:24 UTC
Permalink
@SkRiPt KiDdIe... I think you need to analyze my algo again.... it will work
for both the cases...
Post by SkRiPt KiDdIe
Nishant. Your algorithm works for finding repeated nos. in a [n+2] array
where [1-n] are present atleast once and the same number is not being
repeated twice.
Reanalyze the question.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
ankit sambyal
2011-07-18 13:06:25 UTC
Permalink
@nishant : Time complexity ?????? will increase too much
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Nishant Mittal
2011-07-18 13:11:05 UTC
Permalink
@ankit.... for removing duplicates=O(n)+O(n)
Post by ankit sambyal
@nishant : Time complexity ?????? will increase too much
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Nishant Mittal
2011-07-18 13:12:44 UTC
Permalink
and for finding missing 2 elements= O(n)+O(n)+O(n)+O(n)
so total will be O(n)
but there will be no overflow


On Mon, Jul 18, 2011 at 6:41 PM, Nishant Mittal
Post by Nishant Mittal
@ankit.... for removing duplicates=O(n)+O(n)
Post by ankit sambyal
@nishant : Time complexity ?????? will increase too much
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
SkRiPt KiDdIe
2011-07-18 13:26:02 UTC
Permalink
@Nishant:

1 4 5 4 5 n=5

1 2 3 4 5

after xor i.e. your x1 answer contains (2^3^1^1).The missing elements are
included in xor as well along with repeating elements.

Hope now you got it. You are giving solution for a question which i have
defined in previous post. and your algo will fail when
the final xor has no set bit i.e. same number is being repeated twice.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
SkRiPt KiDdIe
2011-07-18 13:26:41 UTC
Permalink
Post by TUSHAR_MCA
Post by SkRiPt KiDdIe
1 4 5 4 5 n=5
1 2 3 4 5
after xor i.e. your x1 answer contains (2^3^4^5).The missing elements are
included in xor as well along with repeating elements.
Hope now you got it. You are giving solution for a question which i have
defined in previous post. and your algo will fail when
the final xor has no set bit i.e. same number is being repeated twice.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Nishant Mittal
2011-07-18 13:57:26 UTC
Permalink
@SkRiPt KiDdIe... see my 3rd post...i've mentioned that 1st we have to
remove duplicate numbers....
Post by TUSHAR_MCA
Post by TUSHAR_MCA
Post by SkRiPt KiDdIe
1 4 5 4 5 n=5
1 2 3 4 5
after xor i.e. your x1 answer contains (2^3^4^5).The missing elements
are included in xor as well along with repeating elements.
Hope now you got it. You are giving solution for a question which i have
defined in previous post. and your algo will fail when
the final xor has no set bit i.e. same number is being repeated twice.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
KRISHNA
2011-07-18 20:23:08 UTC
Permalink
Algorithm:

1. Given array A[], Set B[], sum=0,repeatedNumb=0;
2. for index i to n
B[ A[i] -1 ] = B[ A[i] -1]+1
sum=sum+A[i]
3. for index i to n
if B[i]=2
repeatedNumb=i+1
break;

4. Nsum=n*(n+1)/2
5. missingNumb=Nsum+repeatedNumb-sum


Step-2 to3, finding the repeatedNum, complexity=O(n)+O(n)
Step4: finding the Nsum, complexity=O(n) if formula is not used


Thanks,
Krishna
Post by TUSHAR_MCA
1 4 5 4 5    n=5
1 2 3 4 5
after xor i.e. your x1 answer contains (2^3^4^5).The missing elements are
included in xor as well along with repeating elements.
Hope now you got it. You are giving solution for a question which i have
defined in previous post. and your algo will fail when
the final xor has no set bit i.e.  same number is being repeated twice.
 --
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Yogesh Yadav
2011-07-19 01:00:08 UTC
Permalink
a[]={1,2,3,4,5} //real a[]


a[]={1,2,3,4,3} //unreal a[]...as 2 numbers not present once...3
is 2 times and 5 is 0 times


step 1: sum=n*(n+1)/2

sum real a[]=5*6/2=15

sum unreal a[]=1+2+3+4+3=13

this means if a is 1 number nd b is 2nd then we know a-b=sum
real a[]- sum unreal a[]

step 2: now square both arrays

repeat step 1

now we know a^2-b^2=sum real a[]- sum unreal a[]

step 3: we know a-b & a^2-b^2....solve for a and b
Post by KRISHNA
1. Given array A[], Set B[], sum=0,repeatedNumb=0;
2. for index i to n
B[ A[i] -1 ] = B[ A[i] -1]+1
sum=sum+A[i]
3. for index i to n
if B[i]=2
repeatedNumb=i+1
break;
4. Nsum=n*(n+1)/2
5. missingNumb=Nsum+repeatedNumb-sum
Step-2 to3, finding the repeatedNum, complexity=O(n)+O(n)
Step4: finding the Nsum, complexity=O(n) if formula is not used
Thanks,
Krishna
Post by TUSHAR_MCA
Post by SkRiPt KiDdIe
1 4 5 4 5 n=5
1 2 3 4 5
after xor i.e. your x1 answer contains (2^3^4^5).The missing elements
are
Post by TUSHAR_MCA
Post by SkRiPt KiDdIe
included in xor as well along with repeating elements.
Hope now you got it. You are giving solution for a question which i
have
Post by TUSHAR_MCA
Post by SkRiPt KiDdIe
defined in previous post. and your algo will fail when
the final xor has no set bit i.e. same number is being repeated
twice.
Post by TUSHAR_MCA
--
You received this message because you are subscribed to the Google
Groups
Post by TUSHAR_MCA
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Continue reading on narkive:
Loading...