オールラウンドなデジタル製品

2 つの数値が与えられた場合、私たちのタスクは、指定された数値が他の 2 つの数値を乗算して 3 つの数値すべてが合計 9 桁を形成するかどうかを調べることです。

言い換えれば、特定の数値が他の 2 つの数値と結合されたときに、元の数値の完全な数値を取得するための乗算演算を形成するかどうかを調べる必要があると言えます。

問題に対して複数の解決策が得られる状況に多く遭遇する可能性があり、最適な時間計算量を得るために、最初に見つかった解決策を単純に出力し、反復プロセスを停止します。

解決策: まず、完全な数値とは何かについて説明します -

n 桁の数値は、1 から n までのすべての桁が 1 回だけ使用される場合に限り、パンディジットと呼ばれます。つまり、一度に 1 桁だけを使用して、1 から n までのすべての数値の順列として数値を表すことができます。

たとえば、6745312 は 1 から 7 までのすべての数字を使用するため、7 桁のパン番号です。

次に、いくつかの例を挙げてこの問題を理解しましょう -

リーリー

誰もが知っているように、7254 は 39 と 186 の積として表すことができます。

39、186、および 7254 を加算すると、391867254 が得られます。これには、1 から 9 までのすべての数字が含まれます。各数字は 1 回のみ使用されます。つまり、9 つの数字で構成される完全な数字です。

リーリー ＃＃＃方法＃＃＃

それでは、この問題を解決する方法について説明しましょう-

最初に、積が指定された数値と等しい数値のペアをすべて見つけることを確認します。次に、考えられる解の数値のペアごとに文字列を作成し、3 つの数値 (元の数値とその積をその数値にする 2 つの因数) をすべて保存します。

それでは、ソリューションに有効なアルゴリズムを見つけてみましょう。

ステップ 1
• - ループを繰り返して、その数値の因子のすべてのペアを確認します。

ステップ 2
• -因子の各部分について、元の数値と 2 つの因子を含む文字列を作成します。

ステップ 3
• - sort() 関数を使用して、形成された文字列を並べ替えます。

ステップ 4
• - 次に、別の文字列「123456789」を作成します

ステップ 5
• - 2 つの文字列を比較し、同じであれば true を返します。

  ＃＃＃例＃＃＃

  このメソッドのコードは次のとおりです -
リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量

- 1 から sqrt(n) まで反復する単一ループを使用しているため、この解の時間計算量は O(N^1/2)

になります。

空間複雑度

- コードには追加のメモリが必要ないため、空間複雑度は線形、つまり O(1) です。

この記事では、すべての数値とは何か、また、指定された数値とその因数 (ペア) を乗算して文字列に結合したときに 9 桁の数値になるかどうかを確認する効率的な方法について説明します。 すべての数値。

以上がオールラウンドなデジタル製品の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。