Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonを使用して合計が奇数のサブ配列の数を見つけるプログラム

配列arrがあるとします。合計が奇数のサブ配列の数を見つける必要があります。答えが大きすぎる場合は、10 ^ 9+7を法とする結果を返します。

したがって、入力がarr =[8,3,7]の場合、すべてのサブ配列が[[8]、[3]、[7]、[8,3]、[3、 7]、[8,3,7]]これで、それらの合計値は[8,3,7,11,10,18]になるため、3つの奇数の合計値[3,7,11]があります。

これを解決するには、次の手順に従います-

  • freq：=1と0の2つの要素を持つリスト

  • ans：=0

  • プレフィックス：=0

  • arrのxごとに、実行します

    • プレフィックス：=プレフィックス+ x

    • ans：=ans + freq[1XORプレフィックスAND1]

    • freq [prefix AND 1]：=freq [prefix AND 1] + 1

  • ans mod（10 ^ 9 + 7）を返す

理解を深めるために、次の実装を見てみましょう-

例

def solve(arr):
   freq = [1, 0]
   ans = prefix = 0
   for x in arr:
      prefix += x
      ans += freq[1 ^ prefix&1]
      freq[prefix &s; 1] += 1
   return ans % (10**9+7)
arr = [8,3,7]
print(solve(arr))

入力

[8,3,7]

出力

3

  1. Pythonプログラムで数の偶数因子の合計を見つける

    この記事では、以下に示す問題ステートメントの解決策について学習します。 問題の説明 −数値が与えられているので、数値のすべての偶数因子の合計を表示する必要があります。 アプローチ 数値が奇数かどうかを確認し、偶数の因子がないため、0を返します。 数が偶数の場合、計算を実行します。 20を除く他のすべての項は、偶数の因数の合計を生成するために乗算されます。 偶数因子のすべての奇数を削除するために、1である20を無視します。このステップの後、偶数因子のみを取得しました。 2は私たちが利用できる唯一の素数であることに注意してください。 次に、以下の実装を見てみましょう- 例 # math

  2. 数の奇数因子の合計を見つけるためのPythonプログラム

    この記事では、以下に示す問題ステートメントの解決策について学習します- 問題の説明 数値入力nが与えられた場合、タスクは数値の奇数因子の合計を見つけることです。 ここでは、最初にすべての偶数の要因を排除する必要があります。 すべての偶数因子を削除するために、nを2で割り切れるまで繰り返し除算します。このステップの後、数の奇数因子のみを取得します。 以下は実装です- 例 import math def sumofoddFactors( n ):    #prime factors    res = 1    # ignore e