FastPrep
Problem · Array

Redistribute Megaseeds

Learn this problem
● MediumRubrik logoRubrikINTERNOA

Problem statement

You are given num crates in a line, where seeds[i] is the number of seeds in crate i. At least one crate is non-empty.

In one operation, move one seed from a crate to its immediately adjacent crate on the left or right.

Choose any integer div > 1 and redistribute the seeds so that every crate contains a multiple of div. Seeds cannot be created or removed.

Return the minimum number of operations over all valid choices of div. If no such divisor exists, return -1.

Function

redistributeMegaseeds(num: int, seeds: int[]) → long

Examples

Example 1

num = 4seeds = [0, 1, 0, 1]return = 2

Choose div = 2 and move the seed from crate 3 left twice. The final counts can be [0, 2, 0, 0].

Example 2

num = 3seeds = [1, 2, 3]return = 1

Choose div = 3 and move one seed from crate 0 to crate 1, producing [0, 3, 3].

Constraints

  • The number of crates, 1 <= num <= 10^6.
  • The initial number of seeds in each crate, 0 <= seeds[i] <= 10^6.
  • Out of seeds[0], seeds[1], seeds[2], ..., seeds[num-1], at least one is assured to be greater than 0.

    • More Rubrik problems

    drafts saved locally
    public long redistributeMegaseeds(int num, int[] seeds) {
  // write your code here
}
    num4
    seeds[0, 1, 0, 1]
    expected2
    checking account