Pythonで合計がkで割り切れるペアに配列を分割できるかどうかを確認します

数の配列があり、別の数kがあるとすると、すべてのペアの合計がkで割り切れるように、指定された配列をペアに分割できるかどうかを確認する必要があります。

したがって、入力がarr =[5、15、6、9] k =7のような場合、（5、9）と（15、6）のようなペアを取ることができるため、出力はTrueになります。

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

• n：=配列のサイズ
• nが奇数の場合、
  • Falseを返す
• occurrences：=空の辞書、キーがない場合は、欠落しているキーの値として0を返します
• 0からnの範囲のiについては、
  • オカレンスを増やす[（（array [i] mod k）+ k）modk]を1つ増やします
• 0からnの範囲のiについては、
  • 剰余：=（（array [i] mod k）+ k）mod k
  • 2 *剰余がkと同じ場合、
    • オカレンス[残り]が奇数の場合、
      • Falseを返す
  • それ以外の場合、余りが0と同じ場合、
    • オカレンス[剰余]AND1がゼロ以外の場合、
      • Falseを返す
  • それ以外の場合、occurrences[remainder]がoccurrences[k-remainder]と同じでない場合は、
    • Falseを返す
• Trueを返す

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

例

from collections import defaultdict
def solve(array, k):
   n = len(array)
   if n % 2 != 0:
      return False
   occurrences = defaultdict(lambda : 0)
   for i in range(0, n):
      occurrences[((array[i] % k) + k) % k] += 1
   for i in range(0, n):
      remainder = ((array[i] % k) + k) % k
      if (2 * remainder == k):
         if (occurrences[remainder] % 2 != 0):
            return False
      elif (remainder == 0):
         if (occurrences[remainder] & 1):
            return False
         elif (occurrences[remainder] != occurrences[k - remainder]):
            return False
   return True
arr = [5, 15, 6, 9]
k = 7
print(solve(arr, k))

入力

[5, 15, 6, 9], 7

出力

True