数値を 4 で割り切れるには、削除する必要がある最小桁数

この記事では、興味深い計算問題、「数値を 4 で割り切れるようにするために削除する必要がある最小桁数」を検討します。この質問は、コーディング コンテストやアルゴリズム ベースの面接でよく聞かれる質問であり、問​​題解決スキルを向上させるための優れた練習になります。

まず、問題文を理解しましょう。数値があり、私たちのタスクは、残りの数値が 4 で割り切れるように最小桁数を削除することです。

概念的な理解

問題は数論の分野にあります。理解すべき重要な事実は、数値が 4 で割り切れるのは、最後の 2 桁が 4 で割り切れる場合に限ります。この事実は問題を解決する上で極めて重要です。

アルゴリズムの説明

この問題を解決するアルゴリズムには次の手順が含まれます -

• 数値を文字列に変換します。

• 文字列の末尾から開始して、最後の 2 文字で構成される数値が 4 で割り切れるかどうかを確認します。

• 「はい」の場合は、削除された桁数を返します。そうでない場合は、最後の文字を削除し、カウントを増やします。

• 数値が 4 で割り切れるか、1 桁だけが残るまで、この操作を繰り返します。

＃＃＃例＃＃＃

これはアルゴリズムの C 実装です -

リーリー ＃＃＃出力＃＃＃ リーリー

minRemovals 関数では、カウンター カウントを 0 に初期化し、削除されたビット数を追跡​​します。次に、数値 (文字列) の末尾から反復処理を行い、数値の最後の 2 桁が 4 で割り切れるかどうかを確認します。そうである場合はカウントを返し、そうでない場合はカウントを返します。そうでない場合は、カウントをインクリメントし、次の反復を続行します。

main 関数はプログラムへのエントリ ポイントとして機能し、入力数値を定義し、数値が 4 で割り切れるように削除する最小桁数を出力します。

テストケースの例

1351 という数字を例に考えてみましょう。最後の 2 桁 (51) を調べると、4 で割り切れないことがわかります。したがって、最後の桁 (1) を削除して、数値 135 を取得します。もう一度確認すると、最後の 2 桁 (35) がまだ 4 で割り切れないことがわかります。したがって、最後の数字 (5) を削除し、数字 13 を残します。最後の 2 桁 (13) は 4 で割り切れないため、最後の桁 (3) を削除します。ここで、4 で割り切れない数字 1 が残りますが、これ以上数字を削除することはできません。したがって、削除する必要がある最小桁数は 3 です。

時間と空間の複雑さ

このアルゴリズムの時間計算量は O(n) です。ここで、n は数値の桁数です。アルゴリズムで追加のデータ構造を使用していないため、空間複雑度は O(1) です。

＃＃＃結論は＃＃＃

この記事では、一般的なコンピューティングの問題、つまり数値を 4 で割り切れるようにするために削除する必要がある最小桁数を決定する問題について詳しく説明します。数論からの重要な洞察を使用して、簡潔な C ソリューションを開発します。

以上が数値を 4 で割り切れるには、削除する必要がある最小桁数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。