配列ペアがkで割り切れるか、Pythonを使用していないかを確認するプログラム

numsという配列があり、この配列には偶数の要素が含まれ、別の値kがあるとします。各ペアの合計がkで割り切れるように、numを正確にn/2ペアに分割する必要があります。可能であればtrueを返し、そうでない場合はfalseを返します。

したがって、入力がnums =[9,5,3,4,7,10,20,8] k =3のような場合、（9,3）、（5）のようなペアを作成できるため、出力はTrueになります。 、7）、（4,20）、（8,10）、すべてのペアの合計は3で割り切れます。

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

• dp：=新しいリスト

• count：=0

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

  • t：=k-（x mod k）

  • tがkと同じ場合、

    • count：=count + 1

  • それ以外の場合

    • dpの最後にtを挿入します

• count mod 2が0と同じでない場合、

  • Falseを返す

• リストを並べ替えるdp

• 低：=0

• 高：=dpのサイズ-1

• 低<高、実行

  • dp [low] + dp [high]がkと同じでない場合、

    • Falseを返す

  • 低：=低+ 1

  • 高：=高-1

• Trueを返す

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

例

def solve(nums, k):
   dp=[]
   count=0
   for x in nums:
      t=k-(x % k)
      if t == k:
         count+=1
      else:
         dp.append(t)
   if count % 2 != 0:
      return False
   dp.sort()
   low = 0
   high = len(dp)-1
   while low < high:
      if dp[low] + dp[high] != k:
         return False
      low += 1
      high -= 1
   return True
nums = [9,5,3,4,7,10,20,8]
k = 3
print(solve(nums, k))

入力

[9,5,3,4,7,10,20,8], 3

出力

True