可能なペアの数から、元の配列のサイズを取得します

あなたの問題は小さな代数に要約され、O(1)時間内に解決することができます。最初に、関数はペアの順列の数ではなく、ペアの組み合わせの数を与えることに注意してください。いずれにせよ、以下のロジックは順列に対応するために簡単に変更できます。

組み合わせの数の式を書くことから始めますkを選択します。

n = 1000およびr = 2に設定すると、次のようになります。

1000! / (2!(998)!) = 1000 * 999 / 2 = 499500

と同じようにnumberOfPossiblePairs(1000)。

演習に進むと、この例ではr = 2であるため、次のようになります。

total = n! / ((n - 2)! * 2!)

ここで単純化します。

total = (n * (n - 1)) / 2

total * 2 = n^2 - n

n^2 - n - 2 * total = 0

これで、2次方程式を適用してnを解くことができます。

ここで、x = n、a = 1、b = -1、およびc = -2 *合計があり、次のようになります。

n = (-(-1) +/- sqrt(1^2 - 4 * 1 * (-2 * total))) / 2

正の数のみに関心があるため、負の解は除外します。コードには次のようなものがあります（注：OPはJavaを使用しているようで、私はここでは専門家ではありません...以下はC++）：

int originalNumber(int total) {
    int result;
    result = (1 + std::sqrt(1 - 4 * 1 * (-2 * total))) / 2;
    return result;
}

結果が整数でない場合に最も近い値を返すというボーナスの質問については、整数に強制変換する前に、結果を単純に丸めることができます。

int originalNumber(int total) {
    int result;
    double temp;
    temp = (1 + std::sqrt(1 - 4 * 1 * (-2 * total))) / 2;
    result = (int) std::round(temp);
    return result;
}

ここで、のような値500050が渡されると、実際の結果は1000.55であり、上記はを返し1001ますが、最初のソリューションはを返し1000ます。