There are 𝑁 people standing in a row with some 𝑐𝑜𝑢𝑛𝑡𝑖 (1≤𝑖≤𝑁) number of chocolates in their hands. You have to select a range of people and take all their chocolates with the condition that you should be able to distribute those chocolates equally among 𝑀 boxes.Write a program to determine the maximum number of chocolates that can be placed in a box.Input formatFirst line: 𝑇 (number of test cases)First line in each test case: Two space-separated integers 𝑁 and 𝑀Second line in each test case: 𝑁 space-separated integers (denoting the number of chocolates)Output formatFor each test case, print the maximum number of chocolates that can be placed in a box.Constraints1≤𝑇≤1031≤𝑁,𝑀≤1050≤𝐶𝑜𝑢𝑛𝑡𝑖≤105Sum of 𝑁 over all test cases ≤107Sample input35 31 2 3 4 55 41 2 3 4 55 81 2 3 4 5Sample output530ExplanationIn first case, you can choose the range [1 , 5] as 1+2+3 + 4 + 5 = 20 , each box will have 5 chocolates.In second case, you can choose the range [3 , 5] as 3 + 4 + 5 = 12 , each box will have 3 chocolates.In third case, there is no way to choose any range such that 8 boxes can be filled equally.
Question
There are 𝑁 people standing in a row with some 𝑐𝑜𝑢𝑛𝑡𝑖 (1≤𝑖≤𝑁) number of chocolates in their hands. You have to select a range of people and take all their chocolates with the condition that you should be able to distribute those chocolates equally among 𝑀 boxes.Write a program to determine the maximum number of chocolates that can be placed in a box.Input formatFirst line: 𝑇 (number of test cases)First line in each test case: Two space-separated integers 𝑁 and 𝑀Second line in each test case: 𝑁 space-separated integers (denoting the number of chocolates)Output formatFor each test case, print the maximum number of chocolates that can be placed in a box.Constraints1≤𝑇≤1031≤𝑁,𝑀≤1050≤𝐶𝑜𝑢𝑛𝑡𝑖≤105Sum of 𝑁 over all test cases ≤107Sample input35 31 2 3 4 55 41 2 3 4 55 81 2 3 4 5Sample output530ExplanationIn first case, you can choose the range [1 , 5] as 1+2+3 + 4 + 5 = 20 , each box will have 5 chocolates.In second case, you can choose the range [3 , 5] as 3 + 4 + 5 = 12 , each box will have 3 chocolates.In third case, there is no way to choose any range such that 8 boxes can be filled equally.
Solution
This problem can be solved using the prefix sum and modulus properties. Here is a Python solution:
from collections import defaultdict
def max_chocolates(n, m, a):
prefix_sum = [0]*(n+1)
for i in range(1, n+1):
prefix_sum[i] = (prefix_sum[i-1] + a[i-1]) % m
max_chocolates = 0
count = defaultdict(int)
for i in range(n+1):
max_chocolates = max(max_chocolates, prefix_sum[i])
for j in range(1, min(i+1, m)):
if (prefix_sum[i] - j + m) % m in count:
max_chocolates = max(max_chocolates, (prefix_sum[i] - ((prefix_sum[i] - j + m) % m) + count[(prefix_sum[i] - j + m) % m]) % m)
count[prefix_sum[i]] = i
return max_chocolates
T = int(input())
for _ in range(T):
n, m = map(int, input().split())
a = list(map(int, input().split()))
print(max_chocolates(n, m, a))
This program works by calculating the prefix sum of the array modulo m and storing it in prefix_sum. It then iterates over prefix_sum and for each index i, it calculates the maximum number of chocolates that can be placed in a box if the range ends at i. This is done by checking all possible numbers of chocolates that can be placed in a box (from 1 to min(i+1, m)) and checking if the remaining chocolates (after placing j chocolates in each box) have appeared before in prefix_sum. If they have, the maximum number of chocolates that can be placed in a box is updated. The index of the last occurrence of each number in prefix_sum is stored in count to be used in the calculation. The maximum number of chocolates that can be placed in a box is then printed for each test case.
Similar Questions
Alice and Bob are very good friends and they always distribute all the eatables equally among themselves.Alice has 𝐴A chocolates and Bob has 𝐵B chocolates. Determine whether Alice and Bob can distribute all the chocolates equally among themselves.Note that:It is not allowed to break a chocolate into more than one piece.No chocolate shall be left in the distribution.Input FormatThe first line of input will contain an integer 𝑇T — the number of test cases. The description of 𝑇T test cases follows.The first and only line of each test case contains two space-separated integers 𝐴A and 𝐵B, the number of chocolates that Alice and Bob have, respectively.Output FormatFor each test case, output on a new line YESYES if Alice and Bob can distribute all the chocolates equally, else output NONO. The output is case insensitive, i.e, yesyes, YeSYeS, yESyES will all be accepted as correct answers when Alice and Bob can distribute the chocolates equally.Constraints1≤𝑇≤10001≤T≤10001≤𝐴,𝐵≤1051≤A,B≤10 5 Sample 1:InputOutput41 11 31 21 4YESYESNONOExplanation:Test case 11: Both Alice and Bob already have equal number of chocolates, hence it is possible to distribute the chocolates equally among Alice and Bob.Test case 22: If Bob gives one of his chocolates to Alice, then both of them will have equal number of chocolates, i.e. 22. So, it is possible to distribute the chocolates equally among Alice and Bob.Test case 33: There are total 33 chocolates. These chocolates cannot be divided equally among Alice and Bob.Test case 44: Alice and Bob cannot have equal number of chocolates, no matter how they distribute the chocolates.
You have n𝑛 chocolates. You can perform the following operation each day as long as you have at least one chocolate:Choose any p𝑝 people from an infinite number of people (1≤p≤current amount of chocolates)(1≤𝑝≤current amount of chocolates).While you have at least p chocolates:Give exactly one chocolate to each of p𝑝 person.Move to the next day with the remaining chocolates.It is not necessary to select the same p𝑝 each day. Your task is to determine the maximum number of days you can perform the above operation.InputThe first line contains a single integer t𝑡 (1≤t≤105)(1≤𝑡≤105) — the number of test cases.The first line of each test case contains a single integers n𝑛 (1≤n≤1018)(1≤𝑛≤1018) — described in the statement. OutputFor each test case, print a single integer — described in the statement.
Ashu and Arvind participated in a coding contest, as a result of which they received 𝑁N chocolates. Now they want to divide the chocolates between them equally.Can you help them by deciding if it is possible for them to divide all the 𝑁N chocolates in such a way that they each get an equal number of chocolates?You cannot break a chocolate in two or more pieces.Input FormatThe first line of input will contain a single integer 𝑇T, denoting the number of test cases.The first and only line of each test case contains a single integer 𝑁N — the number of chocolates they received.Output FormatFor each test case output the answer on a new line — "Yes" (without quotes) if they can divide chocolates between them equally, and "No" (without quotes) otherwise.Each letter of the output may be printed in either uppercase or lowercase, i.e, "Yes", "YES", and "yEs" will all be treated as equivalent.Constraints1≤𝑇≤101≤T≤101≤𝑁≤101≤N≤10Sample 1:InputOutput410432YesYesNoYesExplanation:Test case 11: They can divide 1010 chocolates such that both of them get 55 chocolates each.Test case 22: They can divide 44 chocolates such that both of them get 22 chocolates each.Test case 33: There is no way to divide 33 chocolates so that they get equal number of chocolates.Test case 44: They can divide 22 chocolates such that both of them get 11 chocolate each.
Calculate minimum number of such operations needed to ensure that every colleague has the same number of chocolates.
Candy DistributionChef has 𝑁N candies. He has to distribute them to exactly 𝑀M of his friends such that each friend gets equal number of candies and each friend gets even number of candies. Determine whether it is possible to do so.NOTE: Chef will not take any candies himself and will distribute all the candies.Input FormatFirst line will contain 𝑇T, number of test cases. Then the test cases follow.Each test case contains of a single line of input, two integers 𝑁N and 𝑀M, the number of candies and the number of friends.Output FormatFor each test case, the output will consist of a single line containing Yes if Chef can distribute the candies as per the conditions and No otherwise.You may print each character of the string in uppercase or lowercase (for example, the strings yes, Yes, yEs, and YES will all be treated as identical).
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.