two arrays, find the missing numbers

Question

Given two arrays, first has 'n' numbers and the second one has 'n-m' numbers; the second array is not in the same order as the first. If there are several numbers with the same value, they end up in the order of the positions in the original array. Also, all the values from the second array are also found in the first array. I have to find the 'm' missing numbers in the order in which they appear in the first array.

input:
7 3
12 34 45 29 100 87 32
100 87 12 34

output: 
45 29 32

#include <iostream>
using namespace std;

int main()
{
    int n, missing_number = 0, m, i, j, v[1201], w[1201];
    cin >> n >> m;
    for (i = 0; i < n; ++i) {
        cin >> v[i];
    }
    for (i = 0; i < n - m; ++i) {
        cin >> w[i];
    }
    for (i = 0; i < n; ++i) {
        missing_number = 1;
        for (j = 0; j < n - m; ++j) {
            if (v[i] == w[j]) {
                missing_number = -1;
            }
        }
        if (missing_number == 1) {
            cout << v[i] << " ";
        }
    }
    if (m == 0)
        cout << "there are no missing numbers";
    return 0;
}

my code doesn't work for repeating numbers like:

7 3 
2 6 1 9 3 2 4
4 1 2 3

where my output should be:

6 9 2

Please also include the incorrect output that your code produces. — cigien, Jan 16 '22 at 23:44
... also, did you do any bughunting? We can use that information if you have any ... — Ted Lyngmo, Jan 16 '22 at 23:45
Have you put in one number at a time to debug your algorithm? — Ted Lyngmo, Jan 16 '22 at 23:50
With [`std::unordered_map`](https://en.cppreference.com/w/cpp/container/unordered_map), you can turn your `O(n²)` algorithm into `O(n)` — Jarod42, Jan 17 '22 at 10:33

digito_evo · Accepted Answer · 2022-01-17T01:33:59.913

Your program seems to be outputting the correct result. However, I felt that I need to refactor your code to improve its readability and remove the bad practices used in it.

The below is the same as your code with a bit of improvement:

#include <iostream>
#include <array>
#include <limits>


int main( )
{
    std::array<int, 1201> arr1; // use std::array instead of raw arrays
    std::array<int, 1201> arr2;

    std::size_t arr1_size { }; // renamed n
    std::size_t arr2_size { }; // renamed m

    std::cin >> arr1_size >> arr2_size;

    if ( arr2_size == 0 ) // this if statement should be here to help end
    {                     // the program early on to prevent the execution
                          // of the for-loops
        std::cout << "There are no missing numbers.\n";
        return 0;
    }

    for ( std::size_t idx { }; idx < arr1_size; ++idx ) // use std::size_t
    {                                                   // for the loop counters
        std::cin >> arr1[ idx ];
    }

    for ( std::size_t idx { }; idx < arr1_size - arr2_size; ++idx )
    {
        std::cin >> arr2[ idx ];
    }

    for ( std::size_t arr1_idx { }; arr1_idx < arr1_size; ++arr1_idx )
    {
        bool isNumberMissing { true }; // this should be of type bool

        for ( std::size_t arr2_idx { }; arr2_idx < arr1_size - arr2_size; ++arr2_idx )
        {
            if ( arr1[ arr1_idx ] == arr2[ arr2_idx ] )
            {
                isNumberMissing = false;

                // this is my trick for solving your code's bug
                arr2[ arr2_idx ] = std::numeric_limits<int>::min( );

                break; // break here to improve performance
            }
        }

        if ( isNumberMissing )
        {
            std::cout << arr1[ arr1_idx ] << " ";
        }
    }

    std::cout << '\n';
}

Sample input/output #1:

7 3
12 34 45 29 100 87 32
100 87 12 34
45 29 32

Sample input/output #2:

7 3
2 6 1 9 3 2 4
4 1 2 3
6 9 2

Note: See Why is "using namespace std;" considered bad practice?

Somewhere along the line, there should be some newlines in the output — after the 'There are no missing numbers' message, for example, and probably elsewhere too. I'm far from convinced that `first_array_elem_count` is a good trade for `n`, especially as you have `arr1` instead of `array_1` or something similar. Maybe `arr1_size` would be a reasonable compromise, parallel to `arr1_idx`. Could you not define the arrays when you know the size they need to be? — Jonathan Leffler, Jan 17 '22 at 00:32
Good. Does the code deal with the problem the OP describes with repeated values? When I type `7 3 / 2 6 1 9 3 2 4 / 4 1 2 3`, I get the output `6 9` instead of `6 9 2` that the OP desires, so I think the 'repeated number' logic is still missing. — Jonathan Leffler, Jan 17 '22 at 01:13
Won't work if `std::numeric_limits::min()` happens in input list though. — Jarod42, Jan 17 '22 at 10:35

two arrays, find the missing numbers

1 Answers1