Maximum number of segments of lengths a, b and c

The problem “Maximum number of segments of lengths a, b and c” states that you are given a positive integer N, and you need to find the maximum number of segments of lengths a,b, and c that can be formed using N.

Example

N = 7
a = 5, b = 2, c = 3

3

Explanation

Here if we go with the greedy approach, trying to cut all the segments with the smallest segment(=2). We will not be able to create the last segment of size 1. Thus we divide the length 4 with two 2 length segments and one 4 length segment.

Approach

The problem provides us with a positive integer N, and some other integers a, b, c. Here we want to divide the number in lengths of a, b, and c. We need to divide N such that the number of segments is maximum. So to solve the problem, let’s first try a greedy approach. A greedy approach to solve the problem is choosing the smallest of a, b, and c. Now we divide N into segments with the minimum length. But there is a catch to it, what if the smallest segment does not divide N? Then we will be left with a remainder segment which is not possible to make. So, this confirms that we cannot find the answer using a greedy approach in some cases.

So, instead of doing this using a greedy approach. We solve the problem using recursion. We make a function that gives us the answer for N, then this function calls itself with values N-a, N-b, and N-c. Thus the original problem has been divided into smaller subproblems. We can also reduce the exponential time complexity of this recursive function using dynamic programming. The program with DP will run in linear time. Because we will create a DP array that will store the answer for smaller subproblems. And whenever their result is required we simply use them instead of recomputing them as we did in recursive solution.

Code

C++ code to find the maximum number of segments of lengths a, b and c

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int n = 7, a = 5, b = 2, c = 3;
  int dp[n + 1];
  memset(dp, -1, sizeof(dp));
  // base case
  dp[0] = 0;
  for (int i = 0; i < n; i++)
  {
    if (dp[i] != -1) {
            if(i + a <= n )dp[i + a] = max(dp[i] + 1, dp[i + a]);
            if(i + b <= n )dp[i + b] = max(dp[i] + 1, dp[i + b]);
            if(i + c <= n )dp[i + c] = max(dp[i] + 1, dp[i + c]);
    }
  }
    cout<<dp[n];
}

3

Java code to find the maximum number of segments of lengths a, b and c

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    int n = 7, a = 5, b = 2, c = 3;
    int dp[] = new int[n+1];
    for(int i=0;i<=n;i++)dp[i] = -1;
    // base case
    dp[0] = 0;
    for (int i = 0; i < n; i++)
    {
      if (dp[i] != -1) {
              if(i + a <= n )dp[i + a] = Math.max(dp[i] + 1, dp[i + a]);
              if(i + b <= n )dp[i + b] = Math.max(dp[i] + 1, dp[i + b]);
              if(i + c <= n )dp[i + c] = Math.max(dp[i] + 1, dp[i + c]);
      }
    }
    System.out.println(dp[n]);
  }
}

3

Complexity Analysis

Time Complexity

O(N), because we simply ran a loop until the given integer. Thus the time complexity is linear.

Space Complexity

O(N), because we had to create a 1D DP array for storing the intermediate results to avoid recomputation. Thus the space complexity is also linear.