Here we understand the problem of finding the maximum volume of cube for every person when edges of N cubes are given, then we will write a C++ program to implement the same.
Given:
- An array a[] of N integers which denotes the edges of N cubical structures respectively.
- M integers which denotes the number of peoples.
Problem: To find the maximum amount of volume of a cube that can be given to every person.
Note: Cubes can be cut of any shape from any of the N cubes.
Examples:
Input: a[] = {1, 1, 1, 2, 2}, m = 3 Output: 4 All three person get a slice of volume 4 each Person 1 gets a slice of volume 4 from the last cube. Person 2 gets a slice of volume 4 from the last cube. Person 3 gets a slice of volume 4 from the second last cube. Input: a[] = {2, 2, 2, 2, 2}, m = 4 Output: 8
Common Approach: A common approach is:
- First calculate the volume of all of the cubes
- Linearly check for every volume that it can be distributed among all M people or not
- Find the maximum volume among all such volumes.
Time Complexity: O(N2)
Efficient Approach: An efficient approach is to use the binary search to find the answer. Since the edge lengths are given in the array, convert them to the volume of the respective cubes.
Find the maximum volume among volumes of all of the cubes. Say, the maximum volume is maxVolume. Now, perform binary search on the range [0, maxVolume].
- Calculate the middle value of the range, say mid.
- Now, calculate the total number of cubes that can be cut of all of the cubes of volume mid.
- If the total cubes that can be cut exceed the number of persons, then that amount of volume of cubes can be cut for every person, hence we check for a larger value in the range [mid+1, maxVolume].
- If the total cubes do not exceed the number of persons, then we check for an answer in the range [low, mid-1].
C++ program to find the Maximum volume of cube for every person when edge of N cubes are given:
#include <bits/stdc++.h> using namespace std; int getMaximumVloume(int a[], int n, int m) { int maxVolume = 0; for (int i = 0; i < n; i++) { a[i] = a[i] * a[i] * a[i]; maxVolume = max(a[i], maxVolume); } int low = 0, high = maxVolume; int maxVol = 0; while (low <= high) { int mid = (low + high) >> 1; int cnt = 0; for (int i = 0; i < n; i++) { cnt += a[i] / mid; } if (cnt >= m) { low = mid + 1; maxVol = max(maxVol, mid); } else high = mid - 1; } return maxVol; } int main() { int a[] = { 1, 1, 1, 2, 2 }; int n = sizeof(a) / sizeof(a[0]); int m = 3; cout << getMaximumVloume(a, n, m); return 0; }
Time Complexity: O(N * log (maxVolume))
Comment below to discuss the above problem or to provide a more efficient solution for the same.