TikTok OA 面试真题解析：Card Packets 追加卡片最少数量

Given an array cardTypes where cardTypes[i] is the number of cards of type i, determine the minimum number of additional cards needed so that the cards can be divided into at least 2 matching packets.

Each packet must contain the same number of cards of each type. You may add cards of any type. Return the minimum total number of additional cards required.

Example

cardTypes = [3, 8, 7, 6, 4]

For 2 packets, add [1, 0, 1, 0, 0] cards to get [4, 8, 8, 6, 4].
This requires 2 additional cards.

For 3 packets, add [0, 1, 2, 0, 2] cards to get [3, 9, 9, 6, 6].
This requires 5 additional cards.

The minimum is 2.

Function Description

Complete the function cardPackets in the editor below.

cardPackets has the following parameter(s):

• int cardTypes[n]: the quantity available of each card type

Returns

• int: the minimum number of additional cards to add

Constraints

• 1 <= n <= 10^5
• 1 <= cardTypes[i] <= 500

这题要求在给定每种卡片数量的情况下，补充尽可能少的卡片，使得所有卡片可以被分成至少 2 组完全相同的 packet。核心思路是枚举 packet 的数量 k（从 2 开始），对每一种 cardTypes[i] 计算补到 k 的倍数所需的最少新增数量，也就是 (k – cardTypes[i] % k) % k，然后求总和并取最小值。因为题目中 cardTypes[i] 的上限只有 500，所以只需要枚举到较合理的范围即可；本质上是一个按余数统计、逐个尝试 packet 数量的贪心枚举问题。样例中 [3,8,7,6,4] 选择 2 个 packet 时只需补 2 张，优于补成 3 个 packet 的 5 张，因此答案是 2。