Maximizing Stick Utilization for Square and Rectangle Construction
Given two arrays A[] and B[] of the same length N. There are N types of sticks of lengths specified. Each stick of length A[i] is present in B[i] units (i=1 to N). You have to construct the squares and rectangles using these sticks. Each unit of a stick can be used as the length or breadth of a rectangle or as a side of a square. A single unit of a stick can be used only once. Let S be the sum of the lengths of all sticks that are used in constructing squares and rectangles. The task is to calculate the maximum possible value of S.
Note: The element in array A[] is always unique.
Examples:
Input: N = 4, A[] = {3, 4, 6, 5}, B[] = {2, 3, 1, 6}
Output: 38
Explanation: There are 2 sticks of length 3.
There are 3 sticks of length 4.
There is a 1 stick of length 6.
There are 6 sticks of length 5. One square can be made using 4 sticks of 4th kind (5*4=20) A rectangle can be made using 2 sticks of 4th kind and 2 sticks of 2nd kind (5*2+4*2=18) S = 20 + 18 = 38Input: N = 1, A[] = {3}, B[] = {2}
Output: 0
Explanation: There are only 2 sticks of length 3 which are not enough to make the square or rectangle.
Approach: To solve the problem follow the below idea:
The idea is to use the same formula(Perimeter = 2*(L+B) ) for squares and rectangles to calculate the length of sticks, as in the case of square L==B then this formula becomes 4*L, Advantage of using this formula is no need to check for squares, only take care of rectangles then the calculation is very simple 2*L+2*B, we can generalize it as L+L+B+B that means we just have to add all sticks which are in pairs and at the end number of sticks added should be multiple of 4.
Note: Only an even number of sticks of the ith kind will be used in constructing the square or rectangle.
Step-by-step approach:
- Keep the answer variable to store the answer and the total variable to keep track of how many sticks we have added to the answer.
- Now run a loop over sticks.
- Check if the number of sticks is odd then decrease the number of sticks by one to convert it into an even number.
- Now add the total stick length(number of sticks * one stick length) into the answer.
- Add the number of sticks into the total variable to keep track of the total sticks used so far.
- Check if the total stick used is not in multiple of 4 which means one rectangle is not formed then decrease one pair of sticks which is a minimum one.
- Return the answer.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <iostream> #include <vector> using namespace std; // Function to calculate the // maximum possible value long long maxPossibleValue( int N, vector< int > A, vector< int > B) { long long x, y, mn = 1e10, ans = 0, tot = 0; for ( int i = 0; i < N; i++) { // Getting the values of x and y // from the given vectors x = A[i]; y = B[i]; // If y is odd, decrement it by 1 if (y % 2) y--; // If y is greater than or equal to 2, // store the minimum value of x in mn if (y >= 2) { mn = min(mn, x); } // Calculate the product of x and y and // add it to ans ans += y * x; // Add y to tot tot += y; } // If tot is not divisible by 4, subtract // 2 times the minimum value from ans if (tot % 4 != 0) { ans -= 2 * mn; } // Return the final answer return ans; } // Drivers code int main() { int N = 4; vector< int > A = { 3, 4, 6, 5 }; vector< int > B = { 2, 3, 1, 6 }; long long result = maxPossibleValue(N, A, B); // Function Call cout << "The maximum possible value is: " << result << endl; return 0; } |
Java
import java.util.ArrayList; public class MaxPossibleValue { // Function to calculate the maximum possible value static long maxPossibleValue( int N, ArrayList<Integer> A, ArrayList<Integer> B) { long x, y, mn = Long.MAX_VALUE, ans = 0 , tot = 0 ; for ( int i = 0 ; i < N; i++) { // Getting the values of x and y from the given // arrays x = A.get(i); y = B.get(i); // If y is odd, decrement it by 1 if (y % 2 != 0 ) y--; // If y is greater than or equal to 2, // store the minimum value of x in mn if (y >= 2 ) { mn = Math.min(mn, x); } // Calculate the product of x and y and // add it to ans ans += y * x; // Add y to tot tot += y; } // If tot is not divisible by 4, subtract // 2 times the minimum value from ans if (tot % 4 != 0 ) { ans -= 2 * mn; } // Return the final answer return ans; } // Driver code public static void main(String[] args) { int N = 4 ; ArrayList<Integer> A = new ArrayList<>(N); A.add( 3 ); A.add( 4 ); A.add( 6 ); A.add( 5 ); ArrayList<Integer> B = new ArrayList<>(N); B.add( 2 ); B.add( 3 ); B.add( 1 ); B.add( 6 ); long result = maxPossibleValue(N, A, B); // Function Call System.out.println( "The maximum possible value is: " + result); } } |
Python3
def max_possible_value(N, A, B): x, y, mn = 0 , 0 , float ( 'inf' ) ans, tot = 0 , 0 for i in range (N): # Getting the values of x and y from the given lists x = A[i] y = B[i] # If y is odd, decrement it by 1 if y % 2 : y - = 1 # If y is greater than or equal to 2, store the minimum value of x in mn if y > = 2 : mn = min (mn, x) # Calculate the product of x and y and add it to ans ans + = y * x # Add y to tot tot + = y # If tot is not divisible by 4, subtract 2 times the minimum value from ans if tot % 4 ! = 0 : ans - = 2 * mn # Return the final answer return ans # Drivers code def main(): N = 4 A = [ 3 , 4 , 6 , 5 ] B = [ 2 , 3 , 1 , 6 ] result = max_possible_value(N, A, B) # Function Call print ( "The maximum possible value is:" , result) if __name__ = = "__main__" : main() |
C#
using System; using System.Collections.Generic; public class MaxPossibleValue { // Function to calculate the maximum possible value static long CalculateMaxPossibleValue( int N, List< int > A, List< int > B) { long x, y, mn = long .MaxValue, ans = 0, tot = 0; for ( int i = 0; i < N; i++) { // Getting the values of x and y from the given // lists x = A[i]; y = B[i]; // If y is odd, decrement it by 1 if (y % 2 != 0) y--; // If y is greater than or equal to 2, // store the minimum value of x in mn if (y >= 2) { mn = Math.Min(mn, x); } // Calculate the product of x and y and // add it to ans ans += y * x; // Add y to tot tot += y; } // If tot is not divisible by 4, subtract // 2 times the minimum value from ans if (tot % 4 != 0) { ans -= 2 * mn; } // Return the final answer return ans; } // Driver code public static void Main( string [] args) { int N = 4; List< int > A = new List< int >{ 3, 4, 6, 5 }; List< int > B = new List< int >{ 2, 3, 1, 6 }; long result = CalculateMaxPossibleValue(N, A, B); // Function Call Console.WriteLine( "The maximum possible value is: " + result); } } |
Javascript
function GFG(N, A, B) { let x, y, mn = 1e10, ans = 0, tot = 0; for (let i = 0; i < N; i++) { // Getting the values of x and y from given arrays x = A[i]; y = B[i]; // If y is odd and decrement it by 1 if (y % 2) y--; // If y is greater than or equal to 2 // store the minimum value of x in mn if (y >= 2) { mn = Math.min(mn, x); } // Calculate the product of x and y ans += y * x; // Add y to tot tot += y; } if (tot % 4 !== 0) { ans -= 2 * mn; } // Return the final answer return ans; } // Driver code const N = 4; const A = [3, 4, 6, 5]; const B = [2, 3, 1, 6]; const result = GFG(N, A, B); // Print the result console.log( "The maximum possible value is:" , result); |
The maximum possible value is: 38
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Contact Us