0

I have to find a missing number in a sequence of numbers. The input consists of a positive integer n, between 0 and 35000, and n unique numbers with range [0..n]. (So this range contains n+1 numbers).

I already tried some things with sum={n*(n+1)}/2 and then misNum=sum-SumOfNum;, but I couldn't find a way to make this work.

I wrote some code, but not with the examples I mentioned before. Obviously, this code is not complete, but I don't know how to make it complete.

#include <stdio.h>
#include <stdlib.h>

int main (int argc, char *v[])  {
    int length;
    int num; 

    scanf("%d", &length);
    /*scanf(???)*/

    int goal=length;
    int i;

    for(i=0; i!=length; i++){
        goal=goal+i-num[i];
    };
   return goal;
}

Input and outcome should be:

Input: 2 "enter" 0 2. Output: 1

Input: 3 "enter" 0 3 1. Output: 2

Improve this question
2
  • Do you have to check that the sequence of numbers matches the expectation, i.e. that the numbers are in the correct range, that their count is correct and that you don't have duplicate numbers? (The last one may be impossible without using an array.) Commented Sep 24, 2019 at 8:39
  • But the possible duplicate is for C# not C. Commented Sep 24, 2019 at 10:31

3 Answers 3

Reset to default
5

Sum of all numbers from 0 to n is

n(a1+an)/2 = (in your case a1 = 0 and an = n+1) n*(n+1)/2

so the missing number is n*(n+1)/2 - (sum of input numbers after the length)

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* v[]) {
    int length;
    int i = 0;
    int sum = 0;

    scanf_s("%d", &length);

    // calculate arithmetic series sum
    auto series_sum = ((length + 1) * (length)) / 2;

    while (i < length)
    {
        int next;
        scanf_s("%d", &next);

        sum += next;
        ++i;
    }

    printf("missing num is %d ", series_sum - sum);
}
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

You have n number of integers to be scanned. Use mathematical equation to calculate the sum of first n+1 natural numbers. Then run a loop for n times and then run a loop to add all the n numbers scanned. Then subtract this sum with the sum of n+1 natural number. Result will be the missing number.

Improve this answer

Comments

0

The calculation from the question is also correct and can be made to work with a few modifications.

#include <stdio.h>
#include <stdlib.h>

int main (int argc, char *v[])  {
    int length;
    int num; 

    // printf("enter maximum number: ");
    scanf("%d", &length);

    int goal=length;
    int i;

    for(i=0; i!=length; i++){
        // printf("number[%d]: ", i);
        if(scanf("%d", &num) != 1) { 
            fprintf(stderr, "invalid input\n");
            return 1;
        }
        if((num < 0) || (num > length)) {
            fprintf(stderr, "invalid number %d\n", num);
            return 2;
        }

        goal=goal+i-num;
    };
    // printf("missing number: ");
    printf("%d\n", goal);
    return 0;
}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.