0850MediumArrayHash TableGreedyCounting

Fewest Redials to Level Two Tallies

Tracked in this browser only

Trains the technique from

LeetCode 1775Equal Sum Arrays With Minimum Number of Operations

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Two dice trays are logged as nums1 and nums2, and every entry is a face value from 1 to 6.

One redial picks a single entry in either tray and sets it to any face value from 1 to 6. Return the fewest redials that make the two trays total the same amount, or -1 when no number of redials can. A redial count is never negative, so -1 can only mean it is impossible.

Examples

Example 1

Input: nums1 = [1, 2, 3, 4, 5, 6], nums2 = [1, 1, 2, 2, 2, 2]
Output: 3

The trays total 21 and 10, a gap of 11. Setting the 1 of the second tray to 6 and one of its 2s to 6 raises it to 19, and dropping the 6 of the first tray to 1 lowers that tray to 16. Three redials leave both at the same amount.

Example 2

Input: nums1 = [1, 1, 1, 1, 1, 1, 1, 1], nums2 = [6]
Output: -1

The first tray totals at least 8 whatever is redialled, while the second can never exceed 6, so the two can never be levelled.

Example 3

Input: nums1 = [3], nums2 = [3]
Output: 0

The trays already total the same amount, so no redial is needed.

Constraints

1 <= nums1.length <= 10^5
1 <= nums2.length <= 10^5
1 <= nums1[i] <= 6
1 <= nums2[i] <= 6

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def fewest_redials(nums1: list[int], nums2: list[int]) -> int:

Java

public int fewestRedials(int[] nums1, int[] nums2)

The intended approach

Time O(n + m) using a tally of the six face values rather than a sort.Space O(1) beyond the input: the tally holds six counts.

The larger a tray gets, the more its total is boxed in: a tray of m entries totals between m and 6m, so if one tray's floor exceeds the other's ceiling no redial can ever close the gap. Otherwise, name the tray with the smaller total the low one. Raising an entry of the low tray from v to 6 gains 6 - v, and lowering an entry of the high tray from v to 1 gains v - 1, so gather every available gain, take the biggest first, and count how many are needed before the gap is covered. Taking the largest gains first is safe because every redial costs the same and a redial may overshoot.

Pythonentry point: fewest_redials

def fewest_redials(nums1, nums2):
    a = sum(nums1)
    b = sum(nums2)
    if len(nums1) > 6 * len(nums2) or len(nums2) > 6 * len(nums1):
        return -1
    if a == b:
        return 0
    if a > b:
        nums1, nums2 = nums2, nums1
        a, b = b, a
    gap = b - a
    # gains of size g come from low-tray entries equal to 6 - g and high-tray
    # entries equal to g + 1
    gains = [0] * 6
    for v in nums1:
        if 6 - v > 0:
            gains[6 - v] += 1
    for v in nums2:
        if v - 1 > 0:
            gains[v - 1] += 1
    used = 0
    for g in range(5, 0, -1):
        if gap <= 0:
            break
        take = gains[g]
        need = (gap + g - 1) // g
        if need <= take:
            used += need
            gap = 0
            break
        used += take
        gap -= take * g
    return used if gap <= 0 else -1

The obvious version

Collect every gain a single redial could deliver into a plain list, sort it, and take gains off the end one at a time until the gap is covered. Materialises every gain rather than tallying them by size.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_fewest_redials(nums1, nums2):
    a = sum(nums1)
    b = sum(nums2)
    if a == b:
        return 0
    if a > b:
        nums1, nums2 = nums2, nums1
        a, b = b, a
    gap = b - a
    gains = []
    for v in nums1:
        gains.append(6 - v)
    for v in nums2:
        gains.append(v - 1)
    gains.sort()
    used = 0
    while gap > 0 and gains:
        gap -= gains.pop()
        used += 1
    return used if gap <= 0 else -1

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in