Horje
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 into k 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 into k 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 size k, 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, and k. 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 the groupSum vector.
  • If a valid distribution is found, the distributeElements function returns the groups 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 updating minVal and maxVal.

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);
    }

Output

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 groups k. Therefore, the time complexity can be considered as O(Kn), where n is the number of elements, and k 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), where n is the number of elements and k is the number of groups. The main space-consuming factors are the groups vector of vectors, which holds the distribution of elements into groups, and the groupSum vector of size k, which keeps track of the sum of elements in each group. The size of these vectors depends on the number of elements n and the number of groups k. 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.


 


Reffered: https://www.geeksforgeeks.org

Backtracking

Related
Forming String with maximum occurrences Forming String with maximum occurrences
Find K numbers in a given range [L, R] such that their bitwise XOR is X Find K numbers in a given range [L, R] such that their bitwise XOR is X
Print ways to obtain given sum by repeated throws of a dice Print ways to obtain given sum by repeated throws of a dice
Check if it’s possible to completely fill every container with same ball Check if it’s possible to completely fill every container with same ball
Least count of words required to construct a target String Least count of words required to construct a target String

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje