Maximum and Minimum apples distribution limits
Given an integer N representing a number of apples and an array weights[] consisting weight of these apples. Distribute them to K people such that they receive equal-weighing apples. Each person must receive at least one apple. Cutting an apple in half is restricted, the task is to print the maximum and minimum number of apples through equal weight distribution also if it is not possible then print -1.
Note: There is no boundation on the distribution of the number of apples received.
Examples:
Input: N = 3, K = 2, weights[] = [100, 200, 100]
Output: 1 2
Explanation: Two apples weighing 100 can be given to the first person and the remaining one weighing 200 can be given to the second person.Input: N = 1, K = 3, weight[] = [500]
Output: -1
Explanation: One apple cannot be distributed between three people.
Approach: To solve the problem follow the below idea:
Distribute a given set of apples among a certain number of children while trying to make the distribution as equal as target weight which is the average of all the weights.
This can be done using backtracking algorithm. Calculate the target sum for each group , by dividing the total sum of elements by the number of groups. If the total sum is not divisible by the number of groups, it’s not possible to distribute the elements equally. Try placing each element into one of the groups while maintaining the equal sum condition for each group.
Follow the steps below to solve the problem:
- The
canPartition
function is defined to check if it’s possible to partition the elements intok
groups such that each group has the same sum. It is implemented using a backtracking approach. The function checks all possible combinations of placing elements into the groups and returns true if a valid distribution is found. - The
distributeElements
the function is defined to distribute the elements intok
groups with equal sums. It calculates the target sum for each group by dividing the total sum of elements by the number of groups. If the total sum is not divisible by the number of groups, it returns an empty vector, indicating that it’s not possible to distribute the elements equally. - The function creates an empty vector of vectors called
groups
, which will store the final distribution of elements. - It initializes a vector
groupSum
of sizek
, which keeps track of the sum of elements in each group. - The function calls the
canPartition
function with the given elements,groups
,groupSum
, target sum, initial index 0, andk
. If a valid distribution is found, the function returns true; otherwise, it returns false. - In the
canPartition
function, the recursion stops when all elements have been placed into groups (currIdx == nums.size()
). It then checks if all groups have the same sum by iterating through thegroupSum
vector. - If a valid distribution is found, the
distributeElements
function returns thegroups
the vector containing the elements’ distribution. - Calculate the minimum and maximum number of elements used to form each group by iterating through the
groups
vector and updatingminVal
andmaxVal
.
C++14
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; bool canPartition(vector< int >& nums, vector<vector< int > >& groups, vector< int >& groupSum, int targetSum, int currIdx, int k) { if (currIdx == nums.size()) { // All elements have been placed // into groups, check if all // groups have the same sum for ( int sum : groupSum) { if (sum != targetSum) return false ; } return true ; } for ( int i = 0; i < k; ++i) { if (groupSum[i] + nums[currIdx] <= targetSum) { groups[i].push_back(nums[currIdx]); groupSum[i] += nums[currIdx]; if (canPartition(nums, groups, groupSum, targetSum, currIdx + 1, k)) return true ; groups[i].pop_back(); groupSum[i] -= nums[currIdx]; } } return false ; } vector<vector< int > > distributeElements( int n, int k, vector< int >& elements) { int totalSum = accumulate(elements.begin(), elements.end(), 0); int targetSum = totalSum / k; // Not possible to distribute equally if (totalSum % k != 0) return {}; vector<vector< int > > groups(k); vector< int > groupSum(k, 0); bool possible = canPartition(elements, groups, groupSum, targetSum, 0, k); // Not possible to distribute equally if (!possible) return {}; return groups; } // Drivers code int main() { int n = 5; int k = 2; vector< int > elements = { 7, 5, 8, 5, 5 }; int minVal = n, maxVal = 0; vector<vector< int > > groups = distributeElements(n, k, elements); if (groups.empty()) { cout << "-1" ; } else { for ( const vector< int >& group : groups) { minVal = min(minVal, ( int )group.size()); maxVal = max(maxVal, ( int )group.size()); } cout << minVal << " " << maxVal; } return 0; } |
Java
// Java code for the above approach import java.util.*; public class GFG { static boolean canPartition(List<Integer> nums, List<List<Integer> > groups, List<Integer> groupSum, int targetSum, int currIdx, int k) { if (currIdx == nums.size()) { // All elements have been placed // into groups, check if all // groups have the same sum for ( int sum : groupSum) { if (sum != targetSum) return false ; } return true ; } for ( int i = 0 ; i < k; ++i) { if (groupSum.get(i) + nums.get(currIdx) <= targetSum) { groups.get(i).add(nums.get(currIdx)); groupSum.set(i, groupSum.get(i) + nums.get(currIdx)); if (canPartition(nums, groups, groupSum, targetSum, currIdx + 1 , k)) return true ; groups.get(i).remove(groups.get(i).size() - 1 ); groupSum.set(i, groupSum.get(i) - nums.get(currIdx)); } } return false ; } static List<List<Integer> > distributeElements( int n, int k, List<Integer> elements) { int totalSum = elements.stream() .mapToInt(Integer::intValue) .sum(); int targetSum = totalSum / k; // Not possible to distribute equally if (totalSum % k != 0 ) return new ArrayList<>(); List<List<Integer> > groups = new ArrayList<>(); for ( int i = 0 ; i < k; i++) { groups.add( new ArrayList<>()); } List<Integer> groupSum = new ArrayList<>(Collections.nCopies(k, 0 )); boolean possible = canPartition( elements, groups, groupSum, targetSum, 0 , k); // Not possible to distribute equally if (!possible) return new ArrayList<>(); return groups; } public static void main(String[] args) { int n = 5 ; int k = 2 ; List<Integer> elements = Arrays.asList( 7 , 5 , 8 , 5 , 5 ); int minVal = n, maxVal = 0 ; List<List<Integer> > groups = distributeElements(n, k, elements); if (groups.isEmpty()) { System.out.println( "-1" ); } else { for (List<Integer> group : groups) { minVal = Math.min(minVal, group.size()); maxVal = Math.max(maxVal, group.size()); } System.out.println(minVal + " " + maxVal); } } } // This code is contributed by Abhinav Mahajan // (abhinav_m22). |
Python3
# Python code for the above approach: def canPartition(nums, groups, groupSum, targetSum, currIdx, k): if currIdx = = len (nums): # All elements have been placed # into groups, check if all # groups have the same sum for sum in groupSum: if sum ! = targetSum: return False return True for i in range (k): if groupSum[i] + nums[currIdx] < = targetSum: groups[i].append(nums[currIdx]) groupSum[i] + = nums[currIdx] if canPartition(nums, groups, groupSum, targetSum, currIdx + 1 , k): return True groups[i].pop() groupSum[i] - = nums[currIdx] return False def distributeElements(n, k, elements): totalSum = sum (elements) targetSum = totalSum / / k # Not possible to distribute equally if totalSum % k ! = 0 : return [] groups = [[] for _ in range (k)] groupSum = [ 0 ] * k possible = canPartition(elements, groups, groupSum, targetSum, 0 , k) # Not possible to distribute equally if not possible: return [] return groups # Drivers code n = 5 k = 2 elements = [ 7 , 5 , 8 , 5 , 5 ] minVal = n maxVal = 0 groups = distributeElements(n, k, elements) if not groups: print ( "-1" ) else : for group in groups: minVal = min (minVal, len (group)) maxVal = max (maxVal, len (group)) print (minVal, maxVal) # This code is contributed by Tapesh(tapeshdua420) |
C#
using System; using System.Collections.Generic; using System.Linq; class GFG { static bool CanPartition(List< int > nums, List<List< int >> groups, List< int > groupSum, int targetSum, int currIdx, int k) { if (currIdx == nums.Count) { // All elements have been placed into groups, // check if all groups have the same sum foreach ( int sum in groupSum) { if (sum != targetSum) return false ; } return true ; } for ( int i = 0; i < k; ++i) { if (groupSum[i] + nums[currIdx] <= targetSum) { groups[i].Add(nums[currIdx]); groupSum[i] += nums[currIdx]; if (CanPartition(nums, groups, groupSum, targetSum, currIdx + 1, k)) return true ; groups[i].RemoveAt(groups[i].Count - 1); groupSum[i] -= nums[currIdx]; } } return false ; } static List<List< int >> DistributeElements( int n, int k, List< int > elements) { int totalSum = elements.Sum(); int targetSum = totalSum / k; // Not possible to distribute equally if (totalSum % k != 0) return new List<List< int >>(); List<List< int >> groups = new List<List< int >>(); for ( int i = 0; i < k; i++) { groups.Add( new List< int >()); } List< int > groupSum = Enumerable.Repeat(0, k).ToList(); bool possible = CanPartition(elements, groups, groupSum, targetSum, 0, k); // Not possible to distribute equally if (!possible) return new List<List< int >>(); return groups; } public static void Main( string [] args) { int n = 5; int k = 2; List< int > elements = new List< int > { 7, 5, 8, 5, 5 }; int minVal = n, maxVal = 0; List<List< int >> groups = DistributeElements(n, k, elements); if (groups.Count == 0) { Console.WriteLine( "-1" ); } else { foreach (List< int > group in groups) { minVal = Math.Min(minVal, group .Count); maxVal = Math.Max(maxVal, group .Count); } Console.WriteLine(minVal + " " + maxVal); } } } |
Javascript
function canPartition(nums, groups, groupSum, targetSum, currIdx, k) { if (currIdx === nums.length) { for (const sum of groupSum) { if (sum !== targetSum) return false ; } return true ; } // Try placing the current element // into each group for (let i = 0; i < k; ++i) { if (groupSum[i] + nums[currIdx] <= targetSum) { // Place the element into the // group and update the group sum groups[i].push(nums[currIdx]); groupSum[i] += nums[currIdx]; // Recursively check for the next element if (canPartition(nums, groups, groupSum, targetSum, currIdx + 1, k)) return true ; // Backtrack: remove the element from the // group and update the group sum groups[i].pop(); groupSum[i] -= nums[currIdx]; } } return false ; } // Function to distribute elements // into K groups with equal sums function distributeElements(n, k, elements) { const totalSum = elements.reduce((acc, curr) => acc + curr, 0); const targetSum = totalSum / k; // Not possible to distribute equally // if the total sum is not divisible by K if (totalSum % k !== 0) return []; const groups = new Array(k).fill().map(() => []); const groupSum = new Array(k).fill(0); const possible = canPartition(elements, groups, groupSum, targetSum, 0, k); // Not possible to distribute equally if (!possible) return []; return groups; } // Drivers code const n = 5; const k = 2; const elements = [7, 5, 8, 5, 5]; let minVal = n; let maxVal = 0; const groups = distributeElements(n, k, elements); if (groups.length === 0) { console.log( "-1" ); } else { for (const group of groups) { minVal = Math.min(minVal, group.length); maxVal = Math.max(maxVal, group.length); } console.log(minVal + " " + maxVal); } |
2 3
Complexity Analysis:
- Time complexity: O(Kn), In the worst case, the algorithm explores all possible combinations of placing elements into groups, which could be exponential in the number of elements
n
and the number of groupsk
. Therefore, the time complexity can be considered as O(Kn), wheren
is the number of elements, andk
is the number of groups. However, it is essential to note that backtracking algorithms can often be pruned or optimized based on specific cases, which may lead to better performance for some input scenarios. - Auxiliary Space: The space complexity of the
algorithm
is O(n + k), wheren
is the number of elements andk
is the number of groups. The main space-consuming factors are thegroups
vector of vectors, which holds the distribution of elements into groups, and thegroupSum
vector of sizek
, which keeps track of the sum of elements in each group. The size of these vectors depends on the number of elementsn
and the number of groupsk
. Other variables and data structures used in the function have constant space requirements.
Note: It’s important to keep in mind that backtracking algorithms, like the one used here, can be sensitive to the problem’s input characteristics. While the worst-case time complexity may be exponential, the algorithm can perform efficiently for small input sizes or specific cases where a valid distribution is quickly found. However, for larger inputs or challenging scenarios, more optimized algorithms, such as dynamic programming or advanced optimization techniques, may be required to achieve better performance.
Contact Us