Expected Consecutive Pairs Among Chosen Numbers
Updated
Problem statement
You pick k different numbers from 1, 2, ..., n. Every set of k numbers is equally likely to be picked.
A consecutive pair is two picked numbers that differ by exactly 1. For example, the picked numbers 3, 4, 5, 9 contain two consecutive pairs: (3, 4) and (4, 5).
Return the expected number of consecutive pairs among the picked numbers.
Your answer is accepted if its absolute error or its relative error is at most 10^-9.
Function
expectedConsecutivePairs(n: int, k: int) → doubleExamples
Example 1
n = 25k = 6return = 1.2This is the interview case: six numbers from 1 to 25.
There are 24 possible consecutive pairs: (1, 2), (2, 3), ..., (24, 25). A given pair, say (7, 8), is fully picked with chance 6/25 × 5/24 = 1/20.
Adding this chance over all 24 pairs gives 24 × 1/20 = 6/5 = 1.2.
Example 2
n = 5k = 5return = 4.0All five numbers are picked, so every one of the 4 pairs (1, 2), (2, 3), (3, 4), (4, 5) is there. The answer is exactly 4.
Example 3
n = 10k = 1return = 0.0Only one number is picked, so there can never be a pair. The answer is 0.
Constraints
1 <= n <= 10^91 <= k <= n
More Susquehanna International Group (SIG) Online Assessment questions
- Catch Fish with Reusable BaitsOA · Seen Nov 2026
- Bold Play to Reach a GoalOA · Seen Nov 2026
- Cats, Truth and Who Has MoreOA · Seen Nov 2026
- Counting Cows by Their LegsOA · Seen Nov 2026
- Enough Muffins for the LineOA · Seen Nov 2026
- Four-by-Four Boundary GridOA · Seen Nov 2026
- Frog Paths Without Long RunsOA · Seen Nov 2026
- Higher Roll, or Lose the SumOA · Seen Nov 2026
- Is a Popular Story Fake?OA · Seen Nov 2026
- Knights, Knaves and Their StatementsOA · Seen Nov 2026
Similar questions at other companies
- Next Pascal Row CoefficientIntuit · OAIntuit interview questions
- Subarray SumVisa · OAVisa interview questions
- Drawing EdgeWeRide · OAWeRide interview questions
- Drawing EdgeIBM · OAIBM interview questions
- Drawing EdgeSnowflake · OASnowflake interview questions
- Process SchedulingCitadel · OACitadel interview questions
- Unique Digits in RangeAgoda · OAAgoda interview questions
- Ordered Book Displays with a Featured BookIMC Trading · OAIMC Trading interview questions
- Find Max Number of PairsRoblox · OARoblox interview questions
- Count Nondecreasing Digit-Sum ArraysMicrosoft · OAMicrosoft interview questions