FastPrep
Problem · Array

TikTok Credits Distribution Challenge

Learn this problem
● MediumTiktokOA
See Tiktok hiring insights

Problem statement

In the grand finale of a prestigious TikTok tournament, the organizers have prepared several boxes filled with TikTok credits as prizes for the participants. They know exactly how many participants will compete in the tournament and want to ensure that every participant receives an equal number of TikTok credits to avoid any disappointment. The rules of the tournament are strict: once a prize box is opened, all the TikTok credits inside it must be distributed.

A way consists of choosing a non-empty subset of prize boxes. The credits from all chosen boxes can be distributed equally when their total is divisible by participants. Count the number of such subsets and return the result modulo 10^9 + 7. If no non-empty subset works, return 0.

Function

canDistributeCredits(participants: int, credits: int[]) → int

Complete the function canDistributeCredits.

  • int participants: the number of participants
  • int credits[n]: the number of credits in each box

Returns

int: the number of valid non-empty subsets modulo 10^9 + 7.

Examples

Example 1

participants = 6credits = [12, 18, 24, 36]return = 15

Every credit value is divisible by 6, so the sum of every non-empty subset is also divisible by 6. Four boxes have 2^4 - 1 = 15 non-empty subsets.

Example 2

participants = 5credits = [7, 3, 6]return = 1

The only valid non-empty subset is {7, 3}, whose total is 10 and is divisible by 5.

Constraints

  • 1 <= n <= 10^6
  • 1 <= participants <= 10^3
  • 1 <= credits[i] <= 10^9
  • n * participants <= 10^7

More Tiktok problems

drafts saved locally
public int canDistributeCredits(int participants, int[] credits) {
  // write your code here
}
participants6
credits[12, 18, 24, 36]
expected15
checking account