Ctrl K

Picks Without a Fixed Gap

Medium
You are given an array of positive integers values and a number gap. You pick some of the elements (at least one). A pick is valid if no two chosen numbers differ by exactly gap in absolute value. Return the number of valid picks. Picks are told apart by their sets of indices: if the array holds two equal numbers, taking one or the other counts as two different picks.
Example 1
values=[1, 4, 4, 7], gap=3 → 6

The valid picks are [1], [7], [1, 7], [4, 4] and [4], the last one in two ways since there are two 4s. That makes 6.

Example 2
values=[2, 3, 9], gap=10 → 7

No two numbers differ by 10, so all 7 non-empty picks are valid.

Example 3
values=[10], gap=5 → 1
Constraints
  • 1 ≤ len(values) ≤ 18
  • 1 ≤ values[i] ≤ 1000
  • 1 ≤ gap ≤ 1000
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsFewest Lines Through the Dots MediumSets Without a Fixed Gap MediumExtremes of Small Groups MediumSquare-Sum Chains HardA Fair Split of Colored Beads Hard
loading Python…
Input
values=[1, 4, 4, 7], gap=3
Expected
6

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