An array holds the numbers 1 to n with exactly one missing, in any order. Find the missing number without sorting and without risking overflow.
Solution
main.c
#include <stdio.h>
int missing(const int *a, int len) {
int n = len + 1, x = 0;
for (int i = 1; i <= n; i++)
x ^= i; /* XOR of 1..n */
for (int i = 0; i < len; i++)
x ^= a[i]; /* cancels every number that is present */
return x;
}
int main(void) {
int a[] = {1, 2, 4, 6, 3, 7, 8};
printf("missing number = %d\n", missing(a, 7));
return 0;
}
Output Verified by compiling and running
missing number = 5
x ^ x = 0 and x ^ 0 = x, so XOR-ing 1..n with every element cancels all the numbers that appear twice and leaves the missing one. Unlike the sum formula n(n+1)/2, XOR can never overflow.
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!
We use Google Analytics cookies to see how LearnFrenzy is used and make it better, and Google AdSense to keep it free.
No analytics or ad cookies are set until you accept. Privacy Policy
·
Discussion & Comments 0
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!