How should I practice Remove the Fewest Magic Beans?

Start by reading the full statement, solve the visible examples, then compare the pattern against related The D.E. Shaw Group phone screen problems in FastPrep.

Is Remove the Fewest Magic Beans associated with The D.E. Shaw Group?

FastPrep tags this as a The D.E. Shaw Group phone screen coding practice problem when the problem catalog has that company and stage context.

Remove the Fewest Magic Beans

The D.E. Shaw Group● MediumFULLTIMEPHONE SCREEN

Problem statement

You are given an array beans. Each entry is the number of beans in one bag. You may remove beans from any bag, including all the beans in that bag. Removed beans cannot be put back or moved to another bag.

After the removals, every nonempty bag must contain the same positive number of beans. Empty bags do not need to match that number.

Return the minimum total number of beans that must be removed.

Function

minimumRemoval(beans: int[]) → long

Examples

Example 1

beans = [4,1,6,5]return = 4

Empty the bag with 1 bean, remove 2 beans from the bag with 6, and remove 1 from the bag with 5. The nonempty bags then each contain 4 beans. These removals total 4.

Example 2

beans = [2,10,3,2]return = 7

Keep the bag with 10 beans and empty the other three bags. Removing 2 + 3 + 2 = 7 beans is optimal.

Constraints

1 <= beans.length <= 10^5.
1 <= beans[i] <= 10^5.

More The D.E. Shaw Group problems

See The D.E. Shaw Group hiring insights