Count Ticket Purchase Plans
A cinema sells individual tickets and ticket bundles. Every bundle contains exactly the same number of tickets.
A customer needs an exact number of tickets. Count the different ways the customer can buy them using bundles and individual tickets.
Implement the following method:
int countTicketPlans(int ticketCount, int bundleSize)
ticketCount is the exact number of tickets required.bundleSize is the number of tickets in each bundle.- The method returns the number of different purchase plans.
Rules
- The customer may purchase any number of bundles.
- Tickets not included in bundles are purchased individually.
- A A valid plan may contain zero bundles or zero individual tickets.
- Two plans are different when they use different numbers of bundles.
- The total number of purchased tickets must equal
ticketCount.
Constraints
1 ≤ ticketCount ≤ 1,000,000,0001 ≤ bundleSize ≤ 1,000,000,000- The returned value fits in a 32-bit signed integer.
Examples
Example 1
countTicketPlans(ticketCount = 17, bundleSize = 6)
Output: 3
The customer may purchase 0, 1, or 2 bundles and buy the remaining tickets individually.
Example 2
countTicketPlans(ticketCount = 20, bundleSize = 5)
Output: 5
The possible numbers of bundles are 0, 1, 2, 3, and 4.
Example 3
countTicketPlans(ticketCount = 9, bundleSize = 14)
Output: 1
A bundle contains more tickets than required, so all 9 tickets must be purchased individually.
Example 4
countTicketPlans(ticketCount = 6, bundleSize = 1)
Output: 7
The customer may purchase from 0 through 6 bundles and obtain the remaining tickets individually.