CODEWITHSUNDEEP
carraysnumberssequence
user12092018
user12092018

Reputation:

How to find the missing number without using arrays?

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

Upvotes: 0

Views: 887

Answers (3)

Bodo
Bodo

Reputation: 9875

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;
}

Upvotes: 0

nivpeled
nivpeled

Reputation: 1838

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);
}

Upvotes: 5

haccks
haccks

Reputation: 106092

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.

Upvotes: 1

Related Questions