Sets Without a Fixed Gap

Medium

You are given an array values of distinct positive integers and an integer gap. Call a selection of elements *calm* if no two numbers in it differ by exactly gap. The empty selection is calm too. Return the number of calm selections (subsets of values).

Example 1

values=[3, 6, 9], gap=3 → 5

There are 8 sets in total. The ones containing 3 and 6 or 6 and 9 are banned: {3, 6}, {6, 9}, {3, 6, 9}. That leaves 5: {}, {3}, {6}, {9}, {3, 9}.

Example 2

values=[1, 10, 4], gap=2 → 8

No two values differ by 2, so all 2³ = 8 sets qualify.

Example 3

values=[7, 2, 5, 12, 4], gap=5 → 20

Constraints

1 ≤ len(values) ≤ 50
1 ≤ values[i] ≤ 1000
All values[i] are distinct
1 ≤ gap ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Math Dynamic Programming Combinatorics Sorting

Similar problems

Picks Without a Fixed Gap Medium Extremes of Small Groups Medium Chain of Multiples Medium Subsets With an Odd Total Medium Biggest Number Divisible by Three Hard

Input

values=[3, 6, 9], gap=3

Expected

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