美丽的索恩

Question

如果一个整数序列的每个元素都可以被4整除，那么这个序列就是美丽的。在一个步骤中，您可以选择这个序列的任意两个元素，将它们从序列中移除，并将它们的和附加到序列中。计算使给定序列美观所需的最小步骤数，否则打印-1（如果这不可能）。在

for i in range(int(input())):
    n=int(input())
    arr=list(map(int,input().split()))
    if((sum(arr))%4)!=0:
        print(-1)
        continue
    else:
        counter=[]
        for i in range(n):
            if arr[i]%4!=0:
                counter.append(arr[i])
            else:
                continue

        x=sum(counter)
        while(x%4==0):
            x=x//4

        print(x)

我的方法：如果数组的和不能被4整除，那么数组就不可能是漂亮的，否则如果数组mod 4的和等于0，我计算数组中mod by 4不等于零的元素并将它们追加到列表中，然后求出列表的和，然后将和除以4，直到它的商模4不等于零。什么我做错了？在

在编辑：我有一个有效的工作脚本

^{pr2}$

Answer 1

下面是一个与Ralf Kleberhoff建议的方向基本一致的O（N）实现：

from collections import Counter

def beautify(seq):
    # only mod4 is interesting, count 1s, 2s, and 3s
    c = Counter(x % 4 for x in seq)
    c1, c2, c3 = c.get(1, 0), c.get(2, 0), c.get(3, 0)
    steps22, twos = divmod(c2, 2)  # you have either 0 or 1 2s left
    steps13, ones_or_threes = min(c1, c3), abs(c1 - c3)
    if not twos and not ones_or_threes % 4:
        # 3 steps for every quadruple of 1s or 3s
        return steps22 + steps13 + 3 * ones_or_threes // 4  
    if twos and ones_or_threes % 2 == 2:
        # 2 extra steps to join the remaining 2 1s or 3s with the remaining 2
        return steps22 + steps13 + 3 * ones_or_threes // 4 + 2
    return -1

Answer 2

我不太清楚你的问题是什么，但也许你可以改变一下解决问题的方法。你的逻辑似乎很好，但似乎你试图一次完成所有事情，如果你把它分解成碎片，这个问题就会容易得多。它看起来很适合分而治之/递归方法。我自己也自由地解决了这个问题，因为这似乎是一个有趣的问题。在

以下建议

您可以做的第一件事是编写一个函数，查找两个数的和可以被k整除，然后返回它们：

def two_sum(numbers, k):
    n = len(numbers)

    for i in range(0, n):
        for j in range(i+1, n):
            if (numbers[i] + numbers[j]) % k == 0:
                return numbers[i], numbers[j]
    return None

此外，上面的函数是O(n^2)，这可以使效率更高。在

其次，您可以编写一个递归函数，它使用上述函数，并且有一个基本情况，即当列表中的所有数字都可以被k整除时，它停止递归，因此列表变得“漂亮”。以下是一种方法：

^{pr2}$

上述代码的程序

• 基本情况：如果列表中的所有项当前都可以被k整除，则返回当前累计的count。在
• 否则，从two_sum()获得一对和可被k整除的整数
• remove()列表中的这两个数字，append()到列表的末尾。在
• 最后，再次调用rec_helper()，使用新的修改后的列表，count递增1，即count + 1。count这是最小步骤数。在

最后，您现在可以编写一个主调用函数：

def beautiful_array(numbers, k):
    if sum(numbers) % k != 0:
        return -1

    return rec_helper(numbers, k, 0)

它首先检查列表中数字的sum()是否可以被k整除，然后继续调用rec_helper()。如果它没有通过这个测试，函数只返回-1，并且列表不能被设置为“漂亮”。在

上述代码的行为

>>> beautiful_array([1, 2, 3, 1, 2, 3, 8], 4)
3
>>> beautiful_array([1, 3, 2, 2, 4, 8], 4)
2
>>> beautiful_array([1, 5, 2, 2, 4, 8], 4)
-1

注意：上面的代码示例只是建议，您可以按照您想要的方式进行操作或使用。它也不处理input()，因为我相信代码中的主要问题是方法。我不想创建一个全新的解决方案来处理您的输入。如果上面的代码有问题，或者你什么都不懂，请在下面评论。在

Answer 3

首先是一些观察：

• 为了实现4可除性，我们可以用它们除以4的余数来替换所有的数字，所以我们只需要处理0、1、2和3的值。在
• 顺序无关紧要，数一数0、1、2和3就足够了。在
• 有一对立即给出可被4整除的和：（1，3）和（2，2）。这样一对的每一个存在都需要一个步骤。在
• 有三元组（1，1，2）和（3，3，2）需要两个步骤。在
• 有四个步骤（1，1，1）和（3，3，3，3），需要三个步骤。在

算法：

• 计算余数-0（可以省略）、余数-1、余数-2和余数-3。在
• 如果总数（从计数中）不能被4整除，就没有解。在
• 对于上面描述的所有N元组，找出它们适合计数的频率；将得到的步数相加，从计数中减去消耗的数字。在

最后，余数1、余数2和余数3计数应为零。在