Groups Without Twins

Hard

You are given a list items and a number group_count. Split all the elements into exactly group_count groups of equal size so that no group contains two equal numbers. The spread of a group is its largest element minus its smallest. Return the smallest possible total spread over all groups, or -1 if the elements cannot be split this way.

Example 1

items=[3, 1, 3, 2], group_count=2 → 3

The two 3s must end up in different groups. Groups [1, 3] and [2, 3] give 2 + 1 = 3, while [1, 2] and [3, 3] is not allowed.

Example 2

items=[2, 2, 2, 1], group_count=2 → -1

Three 2s cannot be spread over two groups with at most one 2 in each.

Example 3

items=[4, 1, 6, 2, 5, 3], group_count=3 → 3

Constraints

1 ≤ group_count ≤ len(items) ≤ 16
len(items) is divisible by group_count
1 ≤ items[i] ≤ len(items)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Array Dynamic Programming Bitmask

Similar problems

Settle Up in the Fewest Transfers Hard Two Groups With the Same Average Hard Assembling Fragments Hard Square-Sum Chains Hard Smallest Team With Every Skill Hard

Input

items=[3, 1, 3, 2], group_count=2

Expected

Run checks the first 3 tests in your browser. Submit checks all 66 tests on the server, hidden ones included.