Volunteer Awards: Totals Divisible by K
Updated
Problem statement
There are n houses in a row, numbered from 1 to n. House i holds money[i - 1]. Volunteers collect money for k NGOs. A volunteer picks a non-empty group of houses and collects all the money in each chosen house once. The volunteer earns an award if the total can be shared equally among the k NGOs, which means the total is divisible by k.
Many volunteers may visit the same house, but no two volunteers pick exactly the same group. So the number of volunteers who can earn an award is the number of different groups whose total is divisible by k. Answer four parts:
- Part 1. A group can be any set of houses. Count the groups whose total is divisible by
k. The count can be huge, so return it modulo10^9 + 7. - Part 2. A group must be a run of consecutive houses. Count the runs whose total is divisible by
k. - Part 3. A query
[1, l, r]asks the Part 2 question when only housesltormay be used, so it counts the runs that lie fully inside housesl..r. - Part 4. A query
[2, i, v]sets the money in houseitov. Later queries use the new amount.
Parts 1 and 2 use the starting money. Then process queries in order. Return an array with the Part 1 answer, then the Part 2 answer, then the answer to every [1, l, r] query in the order they appear.
Function
countAwardedVolunteers(money: int[], k: int, queries: int[][]) → int[]Examples
Example 1
money = [1,2,3,4]k = 3queries = [[1,1,4],[2,2,5],[1,2,3],[1,1,4]]return = [5,4,4,1,4]Part 1: the groups whose total is divisible by 3 are {3}, {1, 2}, {2, 4}, {1, 2, 3} and {2, 3, 4}, with totals 3, 3, 6, 6 and 9. That makes 5.
Part 2: the runs are [3], [1, 2], [1, 2, 3] and [2, 3, 4], with totals 3, 3, 6 and 9, so the count is 4.
Query [1, 1, 4] covers every house, so it also gives 4. Then [2, 2, 5] changes house 2 to 5, and the money becomes [1, 5, 3, 4].
Query [1, 2, 3] uses houses 2 and 3, which hold 5 and 3. The runs [5], [3] and [5, 3] total 5, 3 and 8, and only [3] works, so the answer is 1.
Query [1, 1, 4]: now the runs [1, 5], [1, 5, 3], [5, 3, 4] and [3] total 6, 9, 12 and 3, so the answer is 4.
Example 2
money = [5,5,2]k = 2queries = []return = [3,3]With k = 2, a total works when it is even. Part 1: {2}, {5, 5} and {5, 5, 2} total 2, 10 and 12, so the count is 3. Part 2: the runs [2], [5, 5] and [5, 5, 2] are even, while [5], [5] and [5, 2] are not, so the count is also 3. There are no queries.
Example 3
money = [7,7,7]k = 1queries = [[1,2,3]]return = [7,6,3]With k = 1, every total works. Part 1 counts every non-empty group of 3 houses: 2^3 - 1 = 7. Part 2 counts every run: 3 + 2 + 1 = 6. The query uses houses 2 and 3, which have 3 runs, so it gives 3.
Constraints
1 <= n == money.length <= 2 * 10^41 <= money[i] <= 10^41 <= k <= 100 <= queries.length <= 2 * 10^4queries[j].length == 3queries[j][0]is1or2.- For
[1, l, r]:1 <= l <= r <= n. - For
[2, i, v]:1 <= i <= nand1 <= v <= 10^4.
More Nutanix Onsite Interview questions
- Design Hit CounterONSITE INTERVIEW · Seen Oct 2026
- Peak Process MemoryONSITE INTERVIEW · Seen Aug 2026
- Minimum Operations to Transform ArrayONSITE INTERVIEW · Seen Jun 2026
- Count Connected Components in an Undirected GraphONSITE INTERVIEW · Seen Aug 2025
- LRU CacheONSITE INTERVIEW · Seen Aug 2025
- Running Median of a Multilevel Linked List in Level OrderONSITE INTERVIEW · Seen Aug 2025
- Custom Array IteratorONSITE INTERVIEW · Seen Dec 2024
- Collapse Runs of Repeated CharactersONSITE INTERVIEW · Seen Nov 2022
- Anagram Words in a SentenceONSITE INTERVIEW · Seen Apr 2022
- Sudoku SolverONSITE INTERVIEW · Seen Feb 2022
Similar questions at other companies
- Maximum Subarray Sum with Equal EndpointsGoogle · ONSITE INTERVIEWGoogle interview questions
- Count Divisible Power SumsGoodScore · ONSITE INTERVIEW
- Digit SumBank of New York Mellon · OA
- Count Subarrays with a Perfect-Square ProductMicrosoft · OAMicrosoft interview questions
- Tallest BillboardAmazon · ONSITE INTERVIEW
- Prefix Matrix Products and AutogradOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
- Max Points on a LineLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Partition a Card Deck into FifteensMeta · ONSITE INTERVIEWMeta interview questions
- Pro-Rata Order BookIMC Trading · ONSITE INTERVIEWIMC Trading interview questions
- Dynamic Fixed-K Score LeaderboardCoinbase · ONSITE INTERVIEWCoinbase interview questions