Given a 2d array, arr[][] and a piece of the chocolate bar of dimension N × M, the task is to find the minimum possible sum of the area of invalid pieces by dividing the chocolate bar into one or more pieces where a chocolate piece is called invalid if the dimension of that piece doesn’t match any given pair.
Note: A chocolate piece can be cut vertically or horizontally (perpendicular to its sides), such that it is divided into two pieces and the dimension in the given vector is not ordered i.e. for a pair (x, y) in the given vector both dimensions (x, y) and (y, x) are considered valid.
Examples:
Input: N = 10, M =10, arr[][] = {{1, 2}}
Output: 0
Explanation:
Divide the given chocolate bar of dimension (10, 10) into 50 pieces of dimension (1, 2) or (2, 1), not leaving any left over pieces, hence output is zero.Input: N = 10, M =10, arr[][] = {{3, 5}}
Output: 10
Naive Approach: The naive idea is to use recursion to divide the chocolate in every possible dimension by making every possible vertical or horizontal cut. Follow the below steps to solve this problem:
- Divide the chocolate bar into all possible ways, i.e. make every possible vertical & horizontal cut one by one and for each case find a solution for the resulting pieces recursively.
- For the base case, simply check if the current division is valid or not:
- If it is valid then return zero.
- Otherwise, try to divide it into valid pieces using the above approach, if it cannot be divided further into valid pieces return the area of the piece.
Time Complexity: O(N + M)(N + M)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach the idea is to use dynamic programming as the above approach has overlapping subproblems that need to be calculated more than once and to reduce that calculation use tabulation or memoization. The total number of different chocolate pieces that can be made is N × M only, so the above algorithm has N × M states.
Follow the steps below to solve the problem:
- Initialize an array dp[][] to store the minInvalidAreaUtil(l, b) at dp[l][b], ok[][] to store the valid dimension chocolates (i, j) in ok[i][j] = 1 and ok[j][i] = 1.
- For every state whether the current piece (l, b) is valid or not in constant time from lookup table ok[][]
- If the current piece (l, b) is valid, i.e ok[l][b] == 1. Therefore, return dp[l][b] = 0
- Otherwise, compute it by making every possible vertical & horizontal cut one by one and for each case find a solution for the resulting pieces. Hence, update dp[l][b].
- Print the final answer as minInvalidAreaUtil(l, b).
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;const int sz = 1001;// Store valid dimensionsbool ok[sz][sz] = {};// Stores memoizationint dp[sz][sz];// Utility function to calculate minimum invalid area for// Chocolate piece having dimension (l, r)int minInvalidAreaUtil(int l, int b){ if (dp[l][b] == -1) { // Check whether current piece is valid or not // If it is, then return zero // for current dimension if (ok[l][b]) { return dp[l][b] = 0; } int ans = l * b; // Making all possible horizontal cuts, one by // one and calculating the sum of minimum invalid // area for both the resulting pieces for (int i = 1; i < b; i++) { ans = min(ans, minInvalidAreaUtil(l, i) + minInvalidAreaUtil(l, b - i)); } // Making all possible vertical cuts, one by one // and calculating the sum of minimum invalid area // for both the resulting pieces for (int i = 1; i < l; i++) { ans = min(ans, minInvalidAreaUtil(i, b) + minInvalidAreaUtil(l - i, b)); } // Store the computed result dp[l][b] = ans; } return dp[l][b];}// Function to calculate minimum invalid area for// Chocolate piece having dimension (l, r)void minInvalidArea(int N, int M, vector<pair<int, int> >& dimensions){ // Total number of valid dimensions int K = dimensions.size(); // Storing valid dimensions as for every (x, y) // both (x, y) and (y, x) are valid for (int i = 0; i < K; i++) { ok[dimensions[i].first][dimensions[i].second] = 1; ok[dimensions[i].second][dimensions[i].first] = 1; } // Fill dp[][] table with -1, indicating that // results are not computed yet for (int i = 0; i < sz; i++) { for (int j = 0; j < sz; j++) { dp[i][j] = -1; } } // Stores minimum area int minArea = minInvalidAreaUtil(N, M); // Print minArea as the output cout << minArea << endl;}// Driver Codeint main(){ // Given N & M int N = 10, M = 10; // Given valid dimensions vector<pair<int, int> > dimensions = { { 3, 5 } }; // Function Call minInvalidArea(N, M, dimensions); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{ static final int sz = 1001;// Store valid dimensionsstatic boolean ok[][] = new boolean[sz][sz];// Stores memoizationstatic int dp[][] = new int[sz][sz]; static class pair{ int first, second; public pair(int first, int second) { this.first = first; this.second = second; } }// Utility function to calculate minimum invalid// area for Chocolate piece having dimension (l, r)static int minInvalidAreaUtil(int l, int b){ if (dp[l][b] == -1) { // Check whether current piece is valid // or not. If it is, then return zero // for current dimension if (ok[l][b]) { return dp[l][b] = 0; } int ans = l * b; // Making all possible horizontal cuts, one by // one and calculating the sum of minimum invalid // area for both the resulting pieces for(int i = 1; i < b; i++) { ans = Math.min(ans, minInvalidAreaUtil(l, i) + minInvalidAreaUtil(l, b - i)); } // Making all possible vertical cuts, one by one // and calculating the sum of minimum invalid area // for both the resulting pieces for(int i = 1; i < l; i++) { ans = Math.min(ans, minInvalidAreaUtil(i, b) + minInvalidAreaUtil(l - i, b)); } // Store the computed result dp[l][b] = ans; } return dp[l][b];}// Function to calculate minimum invalid area for// Chocolate piece having dimension (l, r)static void minInvalidArea(int N, int M, Vector<pair> dimensions){ // Total number of valid dimensions int K = dimensions.size(); // Storing valid dimensions as for every (x, y) // both (x, y) and (y, x) are valid for(int i = 0; i < K; i++) { ok[dimensions.elementAt(i).first][dimensions.elementAt(i).second] = true; ok[dimensions.elementAt(i).second][dimensions.elementAt(i).first] = true; } // Fill dp[][] table with -1, indicating that // results are not computed yet for(int i = 0; i < sz; i++) { for(int j = 0; j < sz; j++) { dp[i][j] = -1; } } // Stores minimum area int minArea = minInvalidAreaUtil(N, M); // Print minArea as the output System.out.println(minArea);}// Driver Codepublic static void main(String[] args){ // Given N & M int N = 10, M = 10; // Given valid dimensions Vector<pair > dimensions = new Vector<>(); dimensions.add(new pair(3, 5)); // Function Call minInvalidArea(N, M, dimensions);}}// This code is contributed by Dharanendra L V. |
Python3
# Python3 program for the above approachsz = 1001# Store valid dimensionsok = [[0 for i in range(sz)] for i in range(sz)]# Stores memoizationdp = [[0 for i in range(sz)] for i in range(sz)]# Utility function to calculate minimum # invalid area for Chocolate piece having# dimension (l, r)def minInvalidAreaUtil(l, b): global dp, ok if (dp[l][b] == -1): # Check whether current piece is valid # or not If it is, then return zero # for current dimension if (ok[l][b]): dp[l][b] = 0 return dp[l][b] ans = l * b # Making all possible horizontal cuts, one by # one and calculating the sum of minimum invalid # area for both the resulting pieces for i in range(1, b): ans = min(ans, minInvalidAreaUtil(l, i) + minInvalidAreaUtil(l, b - i)) # Making all possible vertical cuts, one by one # and calculating the sum of minimum invalid area # for both the resulting pieces for i in range(1, l): ans = min(ans, minInvalidAreaUtil(i, b) + minInvalidAreaUtil(l - i, b)) # Store the computed result dp[l][b] = ans return dp[l][b]# Function to calculate minimum invalid area for# Chocolate piece having dimension (l, r)def minInvalidArea(N, M, dimensions): global dp, ok # Total number of valid dimensions K = len(dimensions) # Storing valid dimensions as for every (x, y) # both (x, y) and (y, x) are valid for i in range(K): ok[dimensions[i][0]][dimensions[i][1]] = 1 ok[dimensions[i][1]][dimensions[i][0]] = 1 # Fill dp[][] table with -1, indicating that # results are not computed yet for i in range(sz): for j in range(sz): dp[i][j] = -1 # Stores minimum area minArea = minInvalidAreaUtil(N, M) # PrminArea as the output print(minArea)#Driver Codeif __name__ == '__main__': # Given N & M N, M = 10, 10 # Given valid dimensions dimensions = [ [ 3, 5 ] ] # Function Call minInvalidArea(N, M, dimensions)# This code is contributed by mohit kumar 29 |
C#
// C# program to implement above approachusing System;using System.Collections.Generic;class GFG{ static int sz = 1001; // Store valid dimensions static bool[][] ok = new bool[sz][]; // Stores memoization static int[][] dp = new int[sz][]; // Utility function to calculate minimum invalid // area for Chocolate piece having dimension (l, r) static int minInvalidAreaUtil(int l, int b) { if (dp[l][b] == -1) { // Check whether current piece is valid // or not. If it is, then return zero // for current dimension if (ok[l][b]) { return dp[l][b] = 0; } int ans = l * b; // Making all possible horizontal cuts, one by // one and calculating the sum of minimum invalid // area for both the resulting pieces for(int i = 1 ; i < b ; i++) { ans = Math.Min(ans, minInvalidAreaUtil(l, i) + minInvalidAreaUtil(l, b - i)); } // Making all possible vertical cuts, one by one // and calculating the sum of minimum invalid area // for both the resulting pieces for(int i = 1 ; i < l ; i++) { ans = Math.Min(ans, minInvalidAreaUtil(i, b) + minInvalidAreaUtil(l - i, b)); } // Store the computed result dp[l][b] = ans; } return dp[l][b]; } // Function to calculate minimum invalid area for // Chocolate piece having dimension (l, r) static void minInvalidArea(int N, int M, List<pair> dimensions) { // Total number of valid dimensions int K = dimensions.Count; // Storing valid dimensions as for every (x, y) // both (x, y) and (y, x) are valid for(int i = 0; i < K; i++) { ok[dimensions[i].first][dimensions[i].second] = true; ok[dimensions[i].second][dimensions[i].first] = true; } // Fill dp[][] table with -1, indicating that // results are not computed yet for(int i = 0; i < sz ; i++) { for(int j = 0; j < sz ; j++) { dp[i][j] = -1; } } // Stores minimum area int minArea = minInvalidAreaUtil(N, M); // Print minArea as the output Console.Write(minArea); } // Driver Code public static void Main(string[] args){ int N = 10, M = 10; for(int i = 0 ; i < sz ; i++){ ok[i] = new bool[sz]; dp[i] = new int[sz]; } // Given valid dimensions List<pair> dimensions = new List<pair>(); dimensions.Add(new pair(3, 5)); // Function Call minInvalidArea(N, M, dimensions); }}class pair{ public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } }// This code is contributed by subhamgoyal2014. |
Javascript
<script>// JavaScript program for the above approachlet sz = 1001// Store valid dimensionslet ok = new Array(sz).fill(0).map(()=>new Array(sz).fill(0))// Stores memoizationlet dp = new Array(sz).fill(0).map(()=>new Array(sz).fill(0))// Utility function to calculate minimum // invalid area for Chocolate piece having// dimension (l, r)function minInvalidAreaUtil(l, b){ if (dp[l][b] == -1){ // Check whether current piece is valid // or not If it is, then return zero // for current dimension if (ok[l][b]){ dp[l][b] = 0 return dp[l][b] } let ans = l * b // Making all possible horizontal cuts, one by // one and calculating the sum of minimum invalid // area for both the resulting pieces for(let i=1;i<b;i++) ans = Math.min(ans, minInvalidAreaUtil(l, i) + minInvalidAreaUtil(l, b - i)) // Making all possible vertical cuts, one by one // and calculating the sum of minimum invalid area // for both the resulting pieces for(let i=1;i<l;i++) ans = Math.min(ans, minInvalidAreaUtil(i, b) + minInvalidAreaUtil(l - i, b)) // Store the computed result dp[l][b] = ans } return dp[l][b]}// Function to calculate minimum invalid area for// Chocolate piece having dimension (l, r)function minInvalidArea(N, M, dimensions){ // Total number of valid dimensions let K = dimensions.length // Storing valid dimensions as for every (x, y) // both (x, y) and (y, x) are valid for(let i=0;i<K;i++){ ok[dimensions[i][0]][dimensions[i][1]] = 1 ok[dimensions[i][1]][dimensions[i][0]] = 1 } // Fill dp[][] table with -1, indicating that // results are not computed yet for(let i=0;i<sz;i++) for(let j=0;j<sz;j++) dp[i][j] = -1 // Stores minimum area let minArea = minInvalidAreaUtil(N, M) // PrminArea as the output document.write(minArea,"</br>")}// Driver Code // Given N & Mlet N = 10,M = 10// Given valid dimensionslet dimensions = [ [ 3, 5 ] ]// Function CallminInvalidArea(N, M, dimensions)// This code is contributed by shinjanpatra</script> |
Output
10
Time Complexity: O(N * M * (N + M))
Auxiliary Space: O(N * M)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a DP to store the solution of the subproblems and initialize it with -1.
- Initialize the DP with base cases.
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP
- Return the final solution stored in dp[N][M].
Implementation :
C++
// C++ code for above approach#include <bits/stdc++.h>using namespace std;const int sz = 1001;// Store valid dimensionsbool ok[sz][sz] = {};// Stores memoizationint dp[sz][sz];// Utility function to calculate minimum invalid area for// Chocolate piece having dimension (l, r)int minInvalidAreaUtil(int N, int M, vector<pair<int, int> >& dimensions) { // Total number of valid dimensions int K = dimensions.size(); // Storing valid dimensions as for every (x, y) // both (x, y) and (y, x) are valid for (int i = 0; i < K; i++) { ok[dimensions[i].first][dimensions[i].second] = 1; ok[dimensions[i].second][dimensions[i].first] = 1; } // Fill dp[][] table with -1, indicating that // results are not computed yet memset(dp, -1, sizeof(dp)); for (int l = 1; l <= N; l++) { for (int b = 1; b <= M; b++) { // Check whether current piece is valid or not // If it is, then return zero for current dimension if (ok[l][b]) { dp[l][b] = 0; continue; } int ans = l * b; // Making all possible horizontal cuts, one by // one and calculating the sum of minimum invalid // area for both the resulting pieces for (int i = 1; i < b; i++) { ans = min(ans, dp[l][i] + dp[l][b - i]); } // Making all possible vertical cuts, one by one // and calculating the sum of minimum invalid area // for both the resulting pieces for (int i = 1; i < l; i++) { ans = min(ans, dp[i][b] + dp[l - i][b]); } // Store the computed result dp[l][b] = ans; } } // Stores minimum area int minArea = dp[N][M]; // Print minArea as the output cout << minArea << endl; return minArea;}// Driver Codeint main() { // Given N & M int N = 10, M = 10; // Given valid dimensions vector<pair<int, int> > dimensions = {{3, 5}}; // Function Call minInvalidAreaUtil(N, M, dimensions); return 0;}// --- by bhardwajji |
Java
//GFG//Java Code for this approachimport java.util.*;public class Main { static boolean[][] ok = new boolean[1001][1001]; static int[][] dp = new int[1001][1001]; // Utility function to calculate minimum invalid area for // Chocolate piece having dimension (l, r) static int minInvalidAreaUtil(int N, int M, ArrayList<int[]> dimensions) { // Total number of valid dimensions int K = dimensions.size(); // Storing valid dimensions as for every (x, y) // both (x, y) and (y, x) are valid for (int i = 0; i < K; i++) { int[] dim = dimensions.get(i); int x = dim[0], y = dim[1]; ok[x][y] = true; ok[y][x] = true; } // Fill dp[][] table with -1, indicating that // results are not computed yet for (int i = 0; i <= N; i++) { Arrays.fill(dp[i], -1); } for (int l = 1; l <= N; l++) { for (int b = 1; b <= M; b++) { // Check whether current piece is valid or not // If it is, then return zero for current dimension if (ok[l][b]) { dp[l][b] = 0; continue; } int ans = l * b; // Making all possible horizontal cuts, one by // one and calculating the sum of minimum invalid // area for both the resulting pieces for (int i = 1; i < b; i++) { ans = Math.min(ans, dp[l][i] + dp[l][b - i]); } // Making all possible vertical cuts, one by one // and calculating the sum of minimum invalid area // for both the resulting pieces for (int i = 1; i < l; i++) { ans = Math.min(ans, dp[i][b] + dp[l - i][b]); } // Store the computed result dp[l][b] = ans; } } // Stores minimum area int minArea = dp[N][M]; // Print minArea as the output System.out.println(minArea); return minArea; } // Driver Code public static void main(String[] args) { // Given N & M int N = 10, M = 10; // Given valid dimensions ArrayList<int[]> dimensions = new ArrayList<>(); dimensions.add(new int[]{3, 5}); // Function Call minInvalidAreaUtil(N, M, dimensions); }}// This code is contributed by Sundaram |
Python
import sys# Store valid dimensionsok = [[False]*1001 for _ in range(1001)]# Stores memoizationdp = [[-1]*1001 for _ in range(1001)]# Utility function to calculate minimum invalid area for# Chocolate piece having dimension (l, r)def minInvalidAreaUtil(N, M, dimensions): # Total number of valid dimensions K = len(dimensions) # Storing valid dimensions as for every (x, y) # both (x, y) and (y, x) are valid for i in range(K): x, y = dimensions[i] ok[x][y] = True ok[y][x] = True # Fill dp[][] table with -1, indicating that # results are not computed yet for i in range(N+1): for j in range(M+1): dp[i][j] = -1 for l in range(1, N+1): for b in range(1, M+1): # Check whether current piece is valid or not # If it is, then return zero for current dimension if ok[l][b]: dp[l][b] = 0 continue ans = l * b # Making all possible horizontal cuts, one by # one and calculating the sum of minimum invalid # area for both the resulting pieces for i in range(1, b): ans = min(ans, dp[l][i] + dp[l][b - i]) # Making all possible vertical cuts, one by one # and calculating the sum of minimum invalid area # for both the resulting pieces for i in range(1, l): ans = min(ans, dp[i][b] + dp[l - i][b]) # Store the computed result dp[l][b] = ans # Stores minimum area minArea = dp[N][M] # Print minArea as the output print(minArea) return minArea# Driver Codeif __name__ == '__main__': # Given N & M N, M = 10, 10 # Given valid dimensions dimensions = [(3, 5)] # Function Call minInvalidAreaUtil(N, M, dimensions) |
C#
using System;using System.Collections.Generic;class Program{ const int sz = 1001; // Store valid dimensions static bool[,] ok = new bool[sz, sz]; // Stores memoization static int[,] dp = new int[sz, sz]; // Utility function to calculate minimum invalid area for // Chocolate piece having dimension (l, r) static int MinInvalidAreaUtil(int N, int M, List<Tuple<int, int>> dimensions) { // Total number of valid dimensions int K = dimensions.Count; // Storing valid dimensions as for every (x, y) // both (x, y) and (y, x) are valid for (int i = 0; i < K; i++) { ok[dimensions[i].Item1, dimensions[i].Item2] = true; ok[dimensions[i].Item2, dimensions[i].Item1] = true; } // Fill dp[,] table with -1, indicating that // results are not computed yet for (int i = 0; i <= N; i++) { for (int j = 0; j <= M; j++) { dp[i, j] = -1; } } for (int l = 1; l <= N; l++) { for (int b = 1; b <= M; b++) { // Check whether current piece is valid or not // If it is, then return zero for current dimension if (ok[l, b]) { dp[l, b] = 0; continue; } int ans = l * b; // Making all possible horizontal cuts, one by // one and calculating the sum of minimum invalid // area for both the resulting pieces for (int i = 1; i < b; i++) { ans = Math.Min(ans, dp[l, i] + dp[l, b - i]); } // Making all possible vertical cuts, one by one // and calculating the sum of minimum invalid area // for both the resulting pieces for (int i = 1; i < l; i++) { ans = Math.Min(ans, dp[i, b] + dp[l - i, b]); } // Store the computed result dp[l, b] = ans; } } // Stores minimum area int minArea = dp[N, M]; // Print minArea as the output Console.WriteLine(minArea); return minArea; } // Driver Code static void Main() { // Given N & M int N = 10, M = 10; // Given valid dimensions List<Tuple<int, int>> dimensions = new List<Tuple<int, int>> { Tuple.Create(3, 5) }; // Function Call MinInvalidAreaUtil(N, M, dimensions); }} |
Output
10
Time Complexity: O(N * M * (N + M))
Auxiliary Space: O(N * M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
