Discussion:
missing integers in an unsorted array
Banoo
2010-01-31 22:54:11 UTC
hi,
can you help me solve the following problem?

You are given an unsorted list of n-1 distinct integers from the range
1 to n. Write a linear-time algorithm to find the missing integer.

Thanks
--
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.
Krishan Malik
2010-02-01 05:01:29 UTC
sum of first N numbers is n(n+1)/2 .
take the sum of given numbers and subtract it from n(n+1)/2.

Thanks
Sri
Post by Banoo
hi,
can you help me solve the following problem?
You are given an unsorted list of n-1 distinct integers from the range
1 to n. Write a linear-time algorithm to find the missing integer.
Thanks
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
--
SK Malik
--
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.
Mario Ynocente Castro
2010-02-01 00:12:48 UTC
You could use a boolean array to mark which numbers you have on the list.
Post by Banoo
hi,
can you help me solve the following problem?
You are given an unsorted list of n-1 distinct integers from the range
1 to n. Write a linear-time algorithm to find the missing integer.
Thanks
--
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
--
Mario Ynocente Castro
20074016B
FIIS - UNI
--
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.
Anurag Bhatia
2010-02-01 02:31:22 UTC
Sum of n numbers = n(n+1)/2
Traverse the array and add up all the numbers.
Subtract that from the sum of n numbers.

--Anurag
Post by Banoo
hi,
can you help me solve the following problem?
You are given an unsorted list of n-1 distinct integers from the range
1 to n. Write a linear-time algorithm to find the missing integer.
Thanks
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
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.
Sathaiah Dontula
2010-02-01 03:00:51 UTC
Use the formula for sum of first n natural numbers to get the missing
number.

Thanks & regards,
Sathaiah Dontula
Post by Banoo
hi,
can you help me solve the following problem?
You are given an unsorted list of n-1 distinct integers from the range
1 to n. Write a linear-time algorithm to find the missing integer.
Thanks
--
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
--
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.
sachin
2010-02-01 11:37:20 UTC
A way to solve this problem would be using xor(exclusive OR)
xor all the elements from 1 to n.Call it A
xor all the elements of the array into a variable B
Now missing element = A xor B
It works this way
xor-ing an element with itself gives 0(p xor p=0)
xor-ing an element with 0 gives the element itself(p xor 0=p)
xor-ing an element with 1 gives the complement of element(p xor
1=complement(p))

Now suppose you are given 4 elements and you have to find the missing
5th element
A=1 xor 2 xor 3 xor 4 xor 5;
B=ar xor ar xor ar xor ar;

let array be {2,5,3,1}
thus, B=1 xor 2 xor 3 xor 5;

Now A xor B = (1 xor 1) xor (2 xor 2) xor (3 xor 3) xor (5 xor 5) xor
4 = 0 xor 0 xor 0 xor 0 xor 4 = 4(the missing element).

Regards
Sachin
--
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.
srinivas chintagunta
2010-02-05 05:37:17 UTC
I think this works if elements are sorted . Is it correct?
Post by sachin
A way to solve this problem would be using xor(exclusive OR)
xor all the elements from 1 to n.Call it A
xor all the elements of the array into a variable B
Now missing element = A xor B
It works this way
xor-ing an element with itself gives 0(p xor p=0)
xor-ing an element with 0 gives the element itself(p xor 0=p)
xor-ing an element with 1 gives the complement of element(p xor
1=complement(p))
Now suppose you are given 4 elements and you have to find the missing
5th element
A=1 xor 2 xor 3 xor 4 xor 5;
B=ar xor ar xor ar xor ar;
let array be {2,5,3,1}
thus, B=1 xor 2 xor 3 xor 5;
Now A xor B = (1 xor 1) xor (2 xor 2) xor (3 xor 3) xor (5 xor 5) xor
4 = 0 xor 0 xor 0 xor 0 xor 4 = 4(the missing element).
Regards
Sachin
--
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
--
Srinivas Chintagunta,
--
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.
Terence
2010-02-05 06:12:43 UTC
No. This works for all cases. Xor is commutative.
Post by srinivas chintagunta
I think this works if elements are sorted . Is it correct?
A way to solve this problem would be using xor(exclusive OR)
xor all the elements from 1 to n.Call it A
xor all the elements of the array into a variable B
Now missing element = A xor B
It works this way
xor-ing an element with itself gives 0(p xor p=0)
xor-ing an element with 0 gives the element itself(p xor 0=p)
xor-ing an element with 1 gives the complement of element(p xor
1=complement(p))
Now suppose you are given 4 elements and you have to find the missing
5th element
A=1 xor 2 xor 3 xor 4 xor 5;
B=ar xor ar xor ar xor ar;
let array be {2,5,3,1}
thus, B=1 xor 2 xor 3 xor 5;
Now A xor B = (1 xor 1) xor (2 xor 2) xor (3 xor 3) xor (5 xor 5) xor
4 = 0 xor 0 xor 0 xor 0 xor 4 = 4(the missing element).
Regards
Sachin
--
Groups "Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
--
Srinivas Chintagunta,
--
Groups "Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
--
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.
atul verma
2010-02-05 06:18:02 UTC
Yup Terence is right.
Post by Terence
No. This works for all cases. Xor is commutative.
I think this works if elements are sorted . Is it correct?
Post by sachin
A way to solve this problem would be using xor(exclusive OR)
xor all the elements from 1 to n.Call it A
xor all the elements of the array into a variable B
Now missing element = A xor B
It works this way
xor-ing an element with itself gives 0(p xor p=0)
xor-ing an element with 0 gives the element itself(p xor 0=p)
xor-ing an element with 1 gives the complement of element(p xor
1=complement(p))
Now suppose you are given 4 elements and you have to find the missing
5th element
A=1 xor 2 xor 3 xor 4 xor 5;
B=ar xor ar xor ar xor ar;
let array be {2,5,3,1}
thus, B=1 xor 2 xor 3 xor 5;
Now A xor B = (1 xor 1) xor (2 xor 2) xor (3 xor 3) xor (5 xor 5) xor
4 = 0 xor 0 xor 0 xor 0 xor 4 = 4(the missing element).
Regards
Sachin
--
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
--
Srinivas Chintagunta,
--
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
--
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
--
--
Atul Verma
--
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.
Anil Kishore
2010-02-01 06:01:37 UTC
This is clearly explained in the previous mail isn't it ? .. Anyway,
sum of 1..n is S = n*(n+1)/2 . So, find the sum of all elements in the given
input array, say the sum is T, this sum is almost same as S, its just less
than S by the missing number. so, ( S - T ) will give the answer. Are you
looking for something else ?

- AK
Post by Banoo
hi,
can you help me solve the following problem?
You are given an unsorted list of n-1 distinct integers from the range
1 to n. Write a linear-time algorithm to find the missing integer.
Thanks
--
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
--
Anil Kishore
--
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.
Agraj Mangal
2010-02-04 17:35:54 UTC
The XOR solution is better than the SUM method as SUM could result in
overflow and hence wrong answer, which would not happen with XOR solution.

Please correct me if i m wrong.
Post by Anil Kishore
This is clearly explained in the previous mail isn't it ? .. Anyway,
sum of 1..n is S = n*(n+1)/2 . So, find the sum of all elements in the
given input array, say the sum is T, this sum is almost same as S, its just
less than S by the missing number. so, ( S - T ) will give the answer. Are
you looking for something else ?
- AK
Post by Banoo
hi,
can you help me solve the following problem?
You are given an unsorted list of n-1 distinct integers from the range
1 to n. Write a linear-time algorithm to find the missing integer.
Thanks
--
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
--
Anil Kishore
--
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
--
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.
atul verma
2010-02-05 05:58:33 UTC
Yes Doing XOR Is much better idea. Using SUM method we may face overflow
problem which could be solved by strin implementation of a Number(extra
memory)
So its better to go with first solution.-

Atul
Post by Agraj Mangal
The XOR solution is better than the SUM method as SUM could result in
overflow and hence wrong answer, which would not happen with XOR solution.
Please correct me if i m wrong.
Post by Anil Kishore
This is clearly explained in the previous mail isn't it ? .. Anyway,
sum of 1..n is S = n*(n+1)/2 . So, find the sum of all elements in the
given input array, say the sum is T, this sum is almost same as S, its just
less than S by the missing number. so, ( S - T ) will give the answer. Are
you looking for something else ?
- AK
Post by Banoo
hi,
can you help me solve the following problem?
You are given an unsorted list of n-1 distinct integers from the range
1 to n. Write a linear-time algorithm to find the missing integer.
Thanks
--
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
--
Anil Kishore
--
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
--
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