Citadel Online Assessment | Ways to Sum | Citadel OA 2022

An automated packaging system is responsible for packing boxes. A box is certified to hold a certain weight. Given an integer total, calculate the number of possible ways to achieve the total as a sum of weights of items weighing integers from 1 to k, inclusive.

Relevant Citadel OA Problems:

• Triplets
• Ways to Sum
• Consecutive Sum
• Disk Space Analysis
• Do They Belong?
• Global Maximum
• Initial Public Offering
• Inversions
• Portfolio Balances
• Prime Factor Visitation
• Profit Targets
• Sprint Training
• Throttling Gateway
• Birthday Card Collection

Parameter

• total: the value to sum to
• k: the maximum of the range of integers to consider when summing to total

Result

• the number of ways to sum to the total; the number might be very large, so return the integer modulo 1000000007(10^9+7)

Example

Input: total = 8, k = 2

To reach a weight of 8, there are 5 different ways that items with weights between 1 and 2 can be combined:

• [1,1,1,1,1,1,1,1]
• [1,1,1,1,1,1,2]
• [1,1,1,1,2,2]
• [1,1,2,2,2]
• [2,2,2,2]

Output: 5

Constraints

• 1 <= total <= 1000
• 1 <= k <= 100

Try it yourself

Solution