問題: 「最初の 3 桁の合計が最後の 3 桁の合計と等しい 6 桁の数を見つけるアルゴリズム」
インタビューでこの問題に遭遇し、最善の解決策を知りたい. これは私が今まで持っているものです。
アプローチ 1: もちろん、ブルート フォース ソリューションは、各数字 (100,000 から 999,999 の間) について、最初の 3 桁と最後の 3 桁の合計が等しいかどうかを確認することです。はいの場合、そのようなすべての数のカウントを保持する特定のカウンターをインクリメントします。
しかし、これは 900,000 個の数字すべてをチェックするため、非効率的です。
アプローチ 2: そのような数は「どの数」ではなく「いくつ」と尋ねられるため、より適切に行うことができます。数字を 2 つの部分に分割します。最初の 3 桁 (100 から 999 まで) と最後の 3 桁 (000 から 999 まで) です。したがって、候補番号のいずれかの部分の 3 桁の合計は 1 から 27 の範囲になる可能性があり
ますstd::map<int, int>
。
* ここで、最初の部分の各数値について、その合計を見つけ、対応するマップを更新します。
* 同様に、2 番目の部分の更新されたマップを取得できます。* ここで、対応するペア (たとえば、キー 4 のマップ 1 の値とキー 4 のマップ 2 の値) を乗算し、それらを合計すると、答えが得られます。
このアプローチでは、最終的に 1K の数字をチェックすることになります。
私の質問は、どうすればさらに最適化できるでしょうか? より良い解決策はありますか?