FastPrepVolunteer Awards: Totals Divisible by K
Problems/Volunteer Awards: Totals Divisible by K

Volunteer Awards: Totals Divisible by K

Nutanix logoNutanix● HardINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A 2021 report from a virtual off-campus Nutanix hiring loop for an MTS intern role describes this four-part question from the first face-to-face DSA round. Houses in a row hold money. A volunteer whose collected total splits evenly among 3 NGOs earns an award. The parts came one after another. They asked how many volunteers can earn it when any houses may be picked, when only houses next to each other may be picked, when only houses in a range [l, r] count, and when house amounts can also change. The interviewer also asked how the first part changes with k NGOs.

The report gives no input or answer format and no limits on the houses, the amounts or k. It only says there were up to 10^5 range queries. Here k is an input from 1 to 10 and applies to all four parts. Each eligible group of houses counts once and must hold at least one house. The Part 1 count is returned modulo 10^9 + 7. There are up to 2 * 10^4 houses. Each starting amount and new amount is a whole number from 1 to 10^4. Parts 3 and 4 come as one list of up to 2 * 10^4 queries [1, l, r] and [2, i, v], instead of the report's 10^5 range queries. Parts 1 and 2 use the starting amounts. All answers come back in one array.

Our version is about 85% the same as the reported question.

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:

  1. 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 modulo 10^9 + 7.
  2. Part 2. A group must be a run of consecutive houses. Count the runs whose total is divisible by k.
  3. Part 3. A query [1, l, r] asks the Part 2 question when only houses l to r may be used, so it counts the runs that lie fully inside houses l..r.
  4. Part 4. A query [2, i, v] sets the money in house i to v. 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^4
  • 1 <= money[i] <= 10^4
  • 1 <= k <= 10
  • 0 <= queries.length <= 2 * 10^4
  • queries[j].length == 3
  • queries[j][0] is 1 or 2.
  • For [1, l, r]: 1 <= l <= r <= n.
  • For [2, i, v]: 1 <= i <= n and 1 <= 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

Interview reports that mention this question

  • Nutanix Intern Debugging Round and Interviews: 25 Experiences

Nutanix interview experiences

  • Nutanix SWE Intern Phone Screens: 20 Experiences (Part 3 of 3)
  • Nutanix SWE Intern OA Questions: 16 Experiences (Part 2 of 3)
  • Nutanix U.S. SWE Intern Interviews: 54 Experiences (Part 1 of 3)
  • Nutanix SWE OA and Interviews, Level Not Reported: 9 Experiences
All Nutanix interview questionsSee Nutanix hiring insights
Saved
class Solution {
    public int[] countAwardedVolunteers(int[] money, int k, int[][] queries) {
        // Write your code here.
    }
}
Checking account…