c++ - 检查数组中的所有对是否都可以被 k 整除

Question

Given an array of integers and a number k, write a function that returns true if given array can be divided into pairs such that sum of every pair is divisible by k.

这段代码对所有测试用例都产生了正确的结果，除了一个我找不到其中的故障。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) {
      cin >> arr[i];
    }
    int k;
    cin >> k;
    int flag[n] = {0};
    int p = 0;
    int q = 0;
    if (n % 2 != 0) {
      cout << "False" << endl;
    } else {
      for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
          if ((arr[i] + arr[j]) % k == 0 && flag[j] == 0) {
            p = 1;
            flag[j] = 1;
          }
        }
        if (p == 0) {
          q = 1;
          cout << "False" << endl;
          break;
        }
      }
      if (q == 0) {
        cout << "True" << endl;
      }
    }
  }
  return 0;
}

Answer 1

代码中错误的一大来源是困惑的代码。那么我们如何清理代码呢？我们将其模块化。这意味着分解代码，使代码的每个部分都能很好地完成一项工作。让我们看看它是什么样子。

检查某物是否能被 k 整除的函数:

bool isDivisible(int number, int divisor) {
    return number % divisor == 0; 
}

检查所有对的函数:逻辑如下:

1. 取列表中的第一个数字；调用 n0。
2. 对于每个剩余的数字 n1，检查它加上第一个数字是否可以被 k 整除
3. 当我们找到 n1 使得 n0 + n1 可以被 k 整除时，A。如果剩下的剩余数也可以拆分成可整除的对，返回trueb.否则，继续搜索

4.如果我们已经搜索了所有数字，则返回 false。

bool pairsDivisible(int* nums, int count, int k) {
    if(count == 0) return true;
    if(count % 2 != 0) return false; // count must be even

    // 1.
    int n0 = nums[0]; 

    // 2.
    for(int i = 1; i < count; i++) {
        int n1 = nums[i]; 

        // 3.
        if(isDivisible(n0 + n1, k)) {
            // Move the ith number so it's now nums[1]
            std::swap(nums[1], nums[i]); 

            if(pairsDivisible(nums + 2, count - 2, k)) {
                return true; // 3.a
            } else {
                // Reset the array
                std::swap(nums[1], nums[i]); 
            }
        }
    }
    return false; 
}