Split the Bill in Cents

easy

A payments platform splits money all the time: a marketplace order between sellers, a refund across the items it covers, a fee between partners. Money cannot be split into fractions of a cent, and the parts must always add up to exactly the total: a cent created or lost on every split becomes real money at a billion transactions.

Split total cents into parts proportional to weights using the largest remainder method:

Each part first gets floor(total * weights[i] / W) cents, where W is the sum of the weights.
The cents left over are handed out one each to the parts with the largest fractional remainder (the part of total * weights[i] / W that was rounded away), largest first. Parts with equal remainders are served in index order.

Return the amount of every part, in cents.

Example

total = 1000 ($10.00), weights = [1, 1, 1]. Each part gets 333 cents first, which leaves 1 cent over. All three remainders are equal (one third of a cent each), so the first part takes it. The answer is [334, 333, 333], which adds up to 1,000.

Example 1

Input

[
  "1000",
  "[1,1,1]"
]

Output

[334,333,333]

Explanation. The example.

Example 2

Input

[
  "100",
  "[50,30,20]"
]

Output

[50,30,20]

Explanation. An exact split leaves nothing over.

Example 3

Input

[
  "101",
  "[1,1]"
]

Output

[51,50]

Explanation. The odd cent goes to the first part on a tie.

Example 4

Input

[
  "1000",
  "[2,1,0]"
]

Output

[667,333,0]

Explanation. A zero weight gets nothing; the larger remainder wins the cent.

Example 5

Input

[
  "0",
  "[3,4]"
]

Output

[0,0]

Explanation. Nothing to split.

Example 6

Input

[
  "7",
  "[1,1,1,1,1,1,1,1,1,1]"
]

Output

[1,1,1,1,1,1,1,0,0,0]

Explanation. Fewer cents than parts.

Example 7

Input

[
  "999999999",
  "[1000000,999999,1]"
]

Output

[499999999,499999500,500]

Explanation. Large amounts: the products need 64-bit integers.

Example 8

Input

[
  "4",
  "[1,2,1,2]"
]

Output

[1,1,1,1]

Explanation. Equal remainders are broken by index.

Example 9

Input

[
  "12345",
  "[7]"
]

Output

[12345]

Explanation. A single part takes everything.

Follow-up: Finance asks that the same split always gives the extra cents to the same parts, whatever order the items are listed in. What would you tie-break on instead of the index, and why can't you use the amount alone?

Constraints:

- `0 <= total <= 10^9` - `1 <= weights.length <= 10^5` - `0 <= weights[i] <= 10^6`, and at least one weight is positive. - The parts must add up to `total` exactly.

Views: 2