Split a Number into Non-Decreasing Groups
Updated
Problem statement
You have n identical items and want to split all of them into exactly k groups. Every group must get at least one item, and the groups are listed so that their sizes never decrease: size[0] <= size[1] <= ... <= size[k-1].
Since the items are identical, a split is fully described by its list of group sizes. For example, with n = 5 and k = 2 the splits are [1,4] and [2,3]; [4,1] is not allowed because the sizes go down.
Return the number of different splits. The number can be very large, so return it modulo 10^9 + 7.
Function
countPartitions(n: int, k: int) → intExamples
Example 1
n = 7k = 3return = 4The ways to write 7 as 3 group sizes that never decrease are [1,1,5], [1,2,4], [1,3,3] and [2,2,3]. Orders such as [5,1,1] are not counted again, because the sizes must not go down. The answer is 4.
Example 2
n = 9k = 4return = 6The 6 ways are [1,1,1,6], [1,1,2,5], [1,1,3,4], [1,2,2,4], [1,2,3,3] and [2,2,2,3].
Example 3
n = 300k = 25return = 185796306The exact count is 125,144,186,672,314, which is larger than 10^9 + 7, so the answer is that count modulo 10^9 + 7: 185796306.
Constraints
1 <= n <= 10001 <= k <= n
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Dice-Walk Winning ProbabilityGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Integer BreakAmazon · ONSITE INTERVIEW
- Knight Probability in ChessboardGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Frog Paths Without Long RunsSusquehanna International Group (SIG) · OASusquehanna International Group (SIG) interview questions
- Count Lucky TicketsThe D.E. Shaw Group · OAThe D.E. Shaw Group interview questions
- Count Staircases with Strictly Increasing StepseBay · ONSITE INTERVIEWeBay interview questions
- Maximum Score with Prime JumpsMicrosoft · OAMicrosoft interview questions
- Count Divisible Power SumsGoodScore · ONSITE INTERVIEW
- Jump Game with Prime-Step RuleUber · OAUber interview questions
- Count Shipment SchedulesMorgan Stanley · OAMorgan Stanley interview questions
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)