Total Strength of All Squads

Hard

Each fighter has a skill level skills[i]. A squad is any non-empty subset of the fighters. The strength of a squad is the square of its highest skill multiplied by its lowest skill. Return the sum of strengths over all possible squads. Fighters with equal skill are still different people. The answer can be huge, so return it modulo 10⁹ + 7.

Example 1

skills=[3, 1, 2] → 76

Squads: [3] → 27, [1] → 1, [2] → 8, [3,1] → 9, [3,2] → 18, [1,2] → 4, [3,1,2] → 9. The sum is 76.

Example 2

skills=[2, 2] → 24

Three squads, each with strength 2² · 2 = 8, for a total of 24.

Example 3

skills=[5] → 125

Constraints

1 ≤ len(skills) ≤ 10⁵
1 ≤ skills[i] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Math Dynamic Programming Prefix Sum Sorting

Similar problems

Biggest Number Divisible by Three Hard Parcel Lockers Along a Road Hard Merge the Front Tiles Hard Split Into a Climb and a Descent Hard Split Into a Climb and a Descent: Large Values Hard

Input

skills=[3, 1, 2]

Expected

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