How to find missing number in array

Question

#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;
using std::endl;
using std::sort;
int main()
{
    int x = 0;
    int n;                                  // Enter Size of 2 array
    cin >> n;                               // enter 5
    long long *ptr1 = new long long[n - 1]; // size of array must be less than 5 by one n-1
    for (int x = 0; x < n - 1; x++)
    {
        cin >> ptr1[x];
    }
    sort(ptr1, ptr1 + (n - 1));
    for (int z = 1; z < n; z++)
    {
        if (z != ptr1[x])
        {
            cout << z;
            break;
        }
        x++;
    }
    return 0;
}

You're given all positive integers from 1,2,…,n except one integer. Find the missing integer.

Input The first line of input contains an integer n (2≤n≤2×105).

The second line of input contains n−1 distinct integers from 1 to n (inclusive).

Output Print the missing integer. when i try to sumbit this code i get wrong in test 10 but i don't know why! and he didn't show the test so what is wrong?

Answer 1

You can solve this in a more straightforward way if you subtract the numbers that were entered from the expected sum of all numbers 1, 2, ..., n (see comments by @molbdnilo, @Aconcagua and @marcus-müller):

#include <iostream>

int main() {
    std::size_t n;
    std::cin >> n;
    
    std::size_t sum{ n*(n + 1)/2 };
    for (std::size_t idx = 1; idx != n; ++idx) {
        std::size_t thisNumber;
        std::cin >> thisNumber;
        sum -= thisNumber;
    }
    
    std::cout << "Missing number: " << sum << std::endl;
}

Answer 2

I have a three-fold answer:

1. This program leaks memory
2. You included <algorithm> please use it. (Look on cppreference)
3. Spoilers vector, iota, mismatch

Also, you don't reset x before the second loop. That's never going to work unless the missing integer is the last of the array, and not equal to 1

  // for (... z)
    if (z != ptr1[x] /* Here */) {
      // print 1, end loop OR invoke undefined behavior
    }
    x++; // Now x is equal to (n - 1)

Answer 3

There are some problems with your code:

long long *ptr1 = new long long[n - 1]; 

You call new, without delete. This will create a memory leak.

You haven't reinitialized x, so any access to ptr1[x] is out-of-bounds.

Slove all of that, and your code will look like:

#include <iostream>
#include <algorithm>
#include <vector>
int main()
{
    int n;                                  
    cin >> n;                               
    std::vector<int> vec(n-1); // std::vector instead
    for (int x = 0; x < n - 1; x++)
    {
        std::cin >> vec[x];
    }
    std::sort(vec.begin(), vec.end());
    int x = 0; // use another variable instead of reused the old one.
    for (int z = 1; z < n; z++)
    {
        if (z != vec[x])
        {
            std::cout << z;
            break;
        }
        x++;
    }
    return 0;
}

But, this isn't the best approach anyway. As @molbdnilo suggest:

#include <iostream>

int main()
{
    int n;
    std::cin >> n;

    int sum{};
    for (int i = 0; i < n - 1; ++i)
    {
        int tmp;
        std::cin >> tmp;
        sum += tmp;
    }
    std::cout << (n + 1) * n / 2 - sum;
}

Answer 4

Building blocks:

• The expected sum: int expected_sum = n * (n + 1) / 2;
• The sum of all integers fed to the test after you've read n:

  #include <iterator> // istream_iterator
  #include <numeric>  // accumulate
  int sum = std::accumulate(std::istream_iterator<int>(std::cin),
                            std::istream_iterator<int>{}, 0);
  

• Now, expected_sum - sum should give you the missing value.