LearnFrenzy
Sign in Take a free test

Arrays · Array Programs · Question 8

Find the missing number in an array using XOR in C Solution, output & explanation

  • Program
  • Medium
  • 0 comments
  • Answer explained
  • Moderated community
Question 8 Back to Exercise

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.

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!

Post your comment

Comments appear after a quick review by our team.

Search LearnFrenzy

Esc

Quick links