14.28 Minimum Plans to Reach Target Bandwidth

14.28.1 Problem Metadata

Platform: HackerRank
Problem ID: minimum-plans-to-reach-target-bandwidth
Difficulty: Medium
URL: https://www.hackerrank.com/contests/software-engineer-prep-kit/challenges/minimum-plans-to-reach-target-bandwidth
Tags:
Techniques: Unbounded Knapsack, Dynamic Programming, Array

14.28.2 Description

Given an array of positive integers planSizes representing available data plan sizes (in Mbps) and an integer targetBandwidth, return the minimum number of plans needed to sum exactly to the target bandwidth. If it’s impossible to reach the exact target, return -1.

Key Requirements: - Each plan can be reused unlimited times (unbounded) - Find the minimum count of plans needed - Return -1 if no valid combination exists

Relationship to Similar Problems: This is a variant of Coin Change (LeetCode 322). Both problems use unbounded knapsack DP to find the minimum number of items (coins/plans) needed to reach a target sum. The core algorithm is identical, with different variable names (planSizes vs coins, targetBandwidth vs amount).

14.28.3 Examples

Example 1:

Input: planSizes = [1, 2, 5], targetBandwidth = 11
Output: 3
Explanation:
- Optimal choice: 5 + 5 + 1 = 11 (two 5 Mbps plans + one 1 Mbps plan)
- Uses 3 plans total
- No combination uses fewer than 3 plans

Example 2:

Input: planSizes = [1, 3, 4, 7], targetBandwidth = 10
Output: 2
Explanation:
- Optimal choice: 7 + 3 = 10 (one 7 Mbps plan + one 3 Mbps plan)
- Uses 2 plans
- No single plan equals 10, and other combinations require 3+ plans

Example 3:

Input: planSizes = [100, 500, 200, 1000, 50], targetBandwidth = 750
Output: 2
Explanation:
- Optimal choice: 500 + 200 + 50 = 750 uses 3 plans
- Or: 250 + 250 + 250 if 250 exists (not available)
- Best possible: depends on available combinations

Example 4:

Input: planSizes = [5], targetBandwidth = 5
Output: 1
Explanation: Single plan of 5 Mbps matches target exactly

Example 5:

Input: planSizes = [2], targetBandwidth = 3
Output: -1
Explanation: Cannot reach 3 using only plans of size 2

14.28.4 Input Format

First line: integer planSizes_count (number of available plans)
Next planSizes_count lines: each contains a single integer representing a plan size
Final line: integer targetBandwidth

Example:

This represents planSizes = [100, 500, 200, 1000, 50] and targetBandwidth = 750.

14.28.5 Output Format

Return a single integer: the minimum number of plans needed to reach exactly targetBandwidth. If no combination exists, return -1.

14.28.6 Constraints

\(1 \le\) planSizes.length \(\le 1000\)
\(1 \le\) planSizes[i] \(\le 10000\) for all \(0 \le i <\) planSizes.length
\(0 \le\) targetBandwidth \(\le 100000\)
All values are integers

14.28.7 Solution - Dynamic Programming (Unbounded Knapsack)

14.28.7.1 Walkthrough

This problem is a classic unbounded knapsack optimization problem, identical in structure to Coin Change (LeetCode 322). The key insight is that we’re not finding all combinations (which would require backtracking), but rather finding the minimum count of plans needed, which is perfect for dynamic programming.

Why Dynamic Programming?

The problem exhibits two key properties that make DP optimal:

Optimal Substructure: The minimum plans needed for bandwidth \(i\) can be built from the minimum plans needed for smaller bandwidths
- If we use a plan of size \(p\) to contribute to bandwidth \(i\), we need the minimum plans for bandwidth \((i - p)\) plus 1
- dp[i] = dp[i - planSize] + 1
Overlapping Subproblems: Computing dp[11] requires dp[10], dp[9], dp[6]. Computing dp[10] also requires dp[9], dp[8], dp[5], etc.
- Without DP, backtracking would recalculate these subproblems exponentially many times
- DP solves each subproblem exactly once and reuses the result

Algorithm Strategy:

The solution uses bottom-up dynamic programming with a 1D array:

State Definition:
- dp[i] = minimum number of plans needed to reach exactly bandwidth i
- dp[0] = 0 (base case: 0 plans for 0 bandwidth)
- Initialize all other values to Integer.MAX_VALUE (represents “impossible”)
Transition Relation:
```
For each bandwidth i from 1 to targetBandwidth:
  For each planSize in planSizes:
    If planSize <= i and dp[i - planSize] is reachable:
      dp[i] = min(dp[i], dp[i - planSize] + 1)
```
Why dp[i - planSize] + 1?
- dp[i - planSize] is the minimum plans needed to reach bandwidth \((i - \text{planSize})\)
- Adding one more plan of size planSize reaches bandwidth \(i\)
- We take the minimum across all possible plan choices
Result Extraction:
- If dp[targetBandwidth] == Integer.MAX_VALUE, no combination exists → return -1
- Otherwise, return dp[targetBandwidth]

Visual Example: planSizes = [1, 2, 5], targetBandwidth = 11

dp array construction:

dp[0] = 0  (base case)

dp[1]: Try plans [1,2,5]
  - Use plan 1: dp[1-1] + 1 = dp[0] + 1 = 0 + 1 = 1 ✓
  - Plan 2 too large, plan 5 too large
  → dp[1] = 1

dp[2]: Try plans [1,2,5]
  - Use plan 1: dp[2-1] + 1 = dp[1] + 1 = 1 + 1 = 2
  - Use plan 2: dp[2-2] + 1 = dp[0] + 1 = 0 + 1 = 1 ✓ (better!)
  - Plan 5 too large
  → dp[2] = 1

dp[5]: Try plans [1,2,5]
  - Use plan 1: dp[5-1] + 1 = dp[4] + 1 = 2 + 1 = 3
  - Use plan 2: dp[5-2] + 1 = dp[3] + 1 = 2 + 1 = 3
  - Use plan 5: dp[5-5] + 1 = dp[0] + 1 = 0 + 1 = 1 ✓ (best!)
  → dp[5] = 1

...continuing this process...

dp[10]: min(dp[9]+1, dp[8]+1, dp[5]+1) = min(3, 3, 2) = 2
dp[11]: min(dp[10]+1, dp[9]+1, dp[6]+1) = min(3, 3, 3) = 3

Final dp array:
Index:  0  1  2  3  4  5  6  7  8  9  10  11
Value:  0  1  1  2  2  1  2  2  3  3  2   3

Answer: dp[11] = 3  (optimal: 5 + 5 + 1)

Key Implementation Details:

Sentinel Value: Use Integer.MAX_VALUE to mark unreachable bandwidths
- Must check dp[i - planSize] != Integer.MAX_VALUE before adding 1 to avoid integer overflow
Order of Iteration:
- Outer loop iterates through bandwidths (1 to target)
- Inner loop tries all plan sizes
- This order ensures we build up solutions from smaller bandwidths to larger ones
Unbounded Usage:
- We can reuse the same plan multiple times
- When computing dp[i], we can use dp[i - planSize] which may already include this same planSize
- Example: dp[4] with planSize=2 uses dp[2], which may have already used a plan of size 2

14.28.7.2 Analysis

Time Complexity: \(O(n \times T)\) where \(n\) is the number of distinct plan sizes and \(T\) is the target bandwidth.

Breaking down the operations: 1. Initialization: \(O(T)\) - filling the dp array with Integer.MAX_VALUE 2. DP table construction: \(O(n \times T)\) - Outer loop runs \(T\) times (for each bandwidth from 1 to targetBandwidth) - Inner loop runs \(n\) times (for each plan size) - Each iteration does \(O(1)\) work (comparison and update) - Total: \(T \times n \times O(1) = O(n \times T)\) 3. Result extraction: \(O(1)\) - checking final value

Total: \(O(T) + O(n \times T) + O(1) = O(n \times T)\)

Example: For n = 5 plan sizes and T = 750 target bandwidth: \(5 \times 750 = 3,750\) operations (very efficient).

Space Complexity: \(O(T)\) for auxiliary storage.

DP array: \(O(T)\) - stores minimum plans for bandwidths 0 to targetBandwidth
Input storage: Not counted (provided by problem)
Other variables: \(O(1)\) - loop counters, temporary values

Total auxiliary space: \(O(T)\)

Space Optimization Note: This is already optimal for 1D DP. Unlike 2D knapsack problems, we cannot reduce space further because we need access to all previous bandwidth values.

14.28.7.3 Implementation Steps

Step 1: Initialize DP Array

int[] dp = new int[targetBandwidth + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;  // Base case: 0 plans needed for 0 bandwidth

Create array of size targetBandwidth + 1 to include index 0
Fill with Integer.MAX_VALUE to represent “impossible to reach”
Set dp[0] = 0 as the base case (no plans needed for zero bandwidth)

Step 2: Build DP Table Bottom-Up

for (int i = 1; i <= targetBandwidth; i++) {
    for (int planSize : planSizes) {
        if (planSize <= i && dp[i - planSize] != Integer.MAX_VALUE) {
            dp[i] = Math.min(dp[i], dp[i - planSize] + 1);
        }
    }
}

Iterate through each bandwidth value from 1 to targetBandwidth
For each bandwidth i, try all available plan sizes
Eligibility checks:
- planSize <= i: Plan size doesn’t exceed current bandwidth target
- dp[i - planSize] != Integer.MAX_VALUE: The remaining bandwidth \((i - \text{planSize})\) is reachable
Update rule: dp[i] = min(dp[i], dp[i - planSize] + 1)
- If using this plan gives fewer total plans, update dp[i]
- The +1 accounts for adding the current plan

Step 3: Extract Result

return dp[targetBandwidth] == Integer.MAX_VALUE ? -1 : dp[targetBandwidth];

Check if dp[targetBandwidth] is still Integer.MAX_VALUE
- If yes: No combination of plans can reach the target → return -1
- If no: Return the minimum number of plans found

Step 4: Handle Edge Cases The algorithm naturally handles: - Empty input: If planSizes is empty, all dp[i > 0] remain Integer.MAX_VALUE → returns -1 - Target = 0: dp[0] = 0 is already set → returns 0 - Impossible targets: If no combination sums to target, dp[target] stays Integer.MAX_VALUE → returns -1 - Single plan matches target: If planSize == targetBandwidth, then dp[target] = dp[0] + 1 = 1

14.28.7.4 Code - Java

class Result {

    /*
     * Complete the 'findMinimumPlansForBandwidth' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER_ARRAY planSizes
     *  2. INTEGER targetBandwidth
     */

    public static int findMinimumPlansForBandwidth(List<Integer> planSizes, int targetBandwidth) {
        // Initialize dp array - minimum number of plans needed to reach bandwidth i
        int[] dp = new int[targetBandwidth + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;  // Base case: 0 plans needed for 0 bandwidth

        // Fill dp table
        for (int i = 1; i <= targetBandwidth; i++) {
            for (int planSize : planSizes) {
                // planSize <= i: eligible plan to reach bandwidth
                // dp[i - planSize] != Integer.MAX_VALUE: dp[i - planSize] must be reachable
                if (planSize <= i && dp[i - planSize] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - planSize] + 1);
                }
            }
        }

        return dp[targetBandwidth] == Integer.MAX_VALUE ? -1 : dp[targetBandwidth];
    }

}