BRUTE METHOD(Recursion)
Intuition:
- We look for all possibilities for every individual length and send the remaining value in recursion.
- Once the base case is hit, i.e n becomes 0, we return 0;
- And this continues till all the lengths x,y,z are looked whether they will contribute to it or not.
Implementation:
// C++ Code to find maximum number of cut segments
#include <bits/stdc++.h>
#include <limits.h>
#include <iostream>
using namespace std;
int maximizeCuts(int n, int x, int y, int z)
{
// Your code here
if (n == 0)
return 0;
if (n < 0)
return INT_MIN;
int a = maximizeCuts(n - x, x, y, z) + 1;
int b = maximizeCuts(n - y, x, y, z) + 1;
int c = maximizeCuts(n - z, x, y, z) + 1;
int d = max(a, max(b, c));
return d;
}
int main()
{
int l = 11, p = 2, q = 3, r = 5;
cout << maximizeCuts(l, p, q, r) << endl;
return 0;
}
// This code is contributed by Raunak Singh
// Java Code to find maximum number of cut segments
import java.io.*;
class GFG {
public static int maximizeCuts(int n, int x, int y, int z)
{
// Your code here
if (n == 0)
return 0;
if (n < 0)
return Integer.MIN_VALUE;
int a = maximizeCuts(n - x, x, y, z) + 1;
int b = maximizeCuts(n - y, x, y, z) + 1;
int c = maximizeCuts(n - z, x, y, z) + 1;
int d = Math.max(a, Math.max(b, c));
return d;
}
public static void main(String[] args)
{
int l = 11, p = 2, q = 3, r = 5;
System.out.println(maximizeCuts(l, p, q, r));
}
}
// This code is contributed by Raunak Singh
# function to find the maximum number of cuts
def maximize_cuts(n, x, y, z):
# if the rod length is 0, no more cuts can be made
if n == 0:
return 0
# if the rod length becomes negative, return negative infinity
if n < 0:
return float('-inf')
# Calculate the number of cuts using each possible cut length (x, y, z)
a = maximize_cuts(n - x, x, y, z) + 1
b = maximize_cuts(n - y, x, y, z) + 1
c = maximize_cuts(n - z, x, y, z) + 1
# Find the maximum number of cuts among the three possibilities
d = max(a, max(b, c))
return d
if __name__ == "__main__":
l = 11
p = 2
q = 3
r = 5
# Call the maximize_cuts function and print the result
print(maximize_cuts(l, p, q, r))
using System;
class Program {
// Function to find the maximum number of cut segments
static int MaximizeCuts(int n, int x, int y, int z)
{
// Base cases
if (n == 0)
return 0;
if (n < 0)
return int.MinValue;
// Recursively calculate the maximum cuts for each
// option
int a = MaximizeCuts(n - x, x, y, z) + 1;
int b = MaximizeCuts(n - y, x, y, z) + 1;
int c = MaximizeCuts(n - z, x, y, z) + 1;
// Return the maximum of the three options
return Math.Max(a, Math.Max(b, c));
}
static void Main()
{
// Given lengths and cuts
int length = 11, cut1 = 2, cut2 = 3, cut3 = 5;
// Print the maximum number of cut segments
Console.WriteLine(
MaximizeCuts(length, cut1, cut2, cut3));
}
}
// JavaScript code to find maximum number of cut segments
// Function to find maximum cuts
function maximizeCuts(n, x, y, z) {
// Base cases
if (n === 0)
return 0;
if (n < 0)
return Number.MIN_SAFE_INTEGER; // Represents negative infinity in JavaScript
// Recursively find the maximum cuts for each possibility
let a = maximizeCuts(n - x, x, y, z) + 1;
let b = maximizeCuts(n - y, x, y, z) + 1;
let c = maximizeCuts(n - z, x, y, z) + 1;
// Find the maximum of the three possibilities
let d = Math.max(a, Math.max(b, c));
return d;
}
// Main function
function main() {
let l = 11, p = 2, q = 3, r = 5; // Length of rod and lengths of cuts
console.log(maximizeCuts(l, p, q, r)); // Output the maximum cuts
}
// Call the main function to execute the code
main();
Output
5
Time Complexity: O(3^n)
Space Complexity: O(1)
Maximize the number of segments of length p, q and r
Given a rod of length L, the task is to cut the rod in such a way that the total number of segments of length p, q, and r is maximized. The segments can only be of length p, q, and r.
Examples:
Input: l = 11, p = 2, q = 3, r = 5
Output: 5
Explanation: Segments of 2, 2, 2, 2 and 3Input: l = 7, p = 2, q = 5, r = 5
Output: 2
Explanation: Segments of 2 and 5