c++ - 配列内の 2 つの欠損値を見つける方法は?

Question

重複の可能性:
簡単な面接の質問が難しくなった: 与えられた数字 1..100 で、不足している数字を見つける

就職面接の質問. 2 つの欠損値を除いて、1 から N までのすべての値を持つ、サイズが N-2 の配列があるとします。(N>0)

欠落している 2 つの数値を見つけるためのアルゴリズムが必要です。これは、配列を 1 回だけトラバースします。

Answer 1

// Receiving array with values from 1 to N (NOT 0 to N-1)
// N is max value & # of values, NOT size of arr (arr is in size N-2)
void Find2Numbers(unsigned arr[], size_t N, unsigned & n1, unsigned & n2)
{
    unsigned sum = N*(N+1)/2;  // sum of elements
    double pro = 1;  // Products will be calculated within the loop, because fact(N) can be very large

    for(size_t i = 0 ; i < N-2 ; i++)
    {
        pro *= (i+1);  // mult by i+1 to get factorial
        pro /= arr[i];  // divide by arr[i] to find n1*n2
        sum -= arr[i];
    }
    pro *= (N-1)*N;  // 2 missing indexes, as arr is missing 2 elements
    // sum = n1+n2
    // pro = n1*n2  =>
    n1 = (sum+sqrt(sum*sum-4*pro))/2;
    n2 = (sum-sqrt(sum*sum-4*pro))/2;
}