5 hours ago

ANIRUDH • 0

Kota

Problem-2: Maximizing Subset Elements for a Target Sum

Given an array of integers and a target sum, the goal is to find a subset of the array elements that sums exactly to the target. Among all such valid subsets, we must find the one with the maximum number of elements (cardinality) and return that count. If no subset sums to the target, the answer is 0.

Solution 1: Greedy Approach

This solution attempts to solve the problem with a simple greedy strategy. The core idea is to sort the array and preferentially pick smaller elements, hoping to fit more of them into the target sum. This approach is fundamentally flawed because a locally optimal choice (picking the smallest available number) does not guarantee a globally optimal solution (a valid subset that sums to the target).

The logic is as follows:

1. Sort: Sort the input array in ascending order.

2. Iterate and Add: Iterate through the sorted array, adding elements to a running sum as long as the sum does not exceed the target. Count the number of elements added.

3. Check Final Sum: After iterating, if the final sum equals the target, return the count. Otherwise, this strategy fails. It often fails to find a valid subset even when one exists (e.g., for array {3, 4, 9} and target 9, greedy picks 3 and 4, fails to reach 9, and misses the correct solution {9}).

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int greedy_max_elements_for_sum(vector<int>& arr, int target) {
    sort(arr.begin(), arr.end());
    
    int current_sum = 0;
    int element_count = 0;
    
    for (int num : arr) {
        if (current_sum + num <= target) {
            current_sum += num;
            element_count++;
        }
    }
    
    if (current_sum == target) {
        return element_count;
    }
    
    return 0;
}

Complexity Analysis

Let N be the number of elements in the array.

• Time Complexity: O(NlogN). The complexity is dominated by the initial sorting step.

• Space Complexity: O(1) or O(N) depending on the sort implementation.

Solution 2: Dynamic Programming (Optimal)

This problem is a variation of the classic Subset Sum problem and exhibits optimal substructure and overlapping subproblems, making it a perfect candidate for dynamic programming. This approach systematically builds a solution by considering every element and every possible sum up to the target.

The logic is as follows:

1. Define DP State: Create a 2D DP table, dp[i][j], which will store the maximum number of elements from the first i items of the input array that sum up to exactly j. Initialize the table with a sentinel value (e.g., -1) to represent unreachable states.

2. Base Case: A sum of 0 can always be achieved with 0 elements (the empty set). So, dp[i] = 0 for all i.

3. Recurrence Relation: For each element arr[i-1] and each sum j, we have two choices:

   • Exclude arr[i-1]: The result is the same as for the first i-1 elements, i.e., dp[i-1][j].

   • Include arr[i-1]: This is possible only if j >= arr[i-1] and a solution for the subproblem dp[i-1][j - arr[i-1]] exists. The new cardinality would be dp[i-1][j - arr[i-1]] + 1. The value of dp[i][j] is the maximum of these two choices.

4. Final Answer: The solution is the value in dp[n][target]. If it's the sentinel value, no solution exists, and we return 0.

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int max_elements_for_sum_cpp(const vector<int>& arr, int target) {
    int n = arr.size();
    
    vector<vector<int>> dp(n + 1, vector<int>(target + 1, -1));

    for (int i = 0; i <= n; ++i) {
        dp[i] = 0;
    }

    for (int i = 1; i <= n; ++i) {
        int num = arr[i - 1];
        for (int j = 1; j <= target; ++j) {
            int exclude_val = dp[i - 1][j];

            int include_val = -1;
            if (j >= num && dp[i - 1][j - num] != -1) {
                include_val = dp[i - 1][j - num] + 1;
            }
            
            dp[i][j] = max(exclude_val, include_val);
        }
    }

    int result = dp[n][target];
    return (result != -1) ? result : 0;
}

int main() {
    vector<int> arr = {2, 3, 5, 5};
    int target = 10;
    cout << "Maximum elements: " << max_elements_for_sum_cpp(arr, target) << endl;
    return 0;
}

Complexity Analysis

Let N be the number of elements and T be the target sum.

• Time Complexity: O(NtimesT). The algorithm fills an NtimesT table, with constant time work for each cell. This is a pseudo-polynomial time complexity.

• Space Complexity: O(NtimesT). The space is required for the DP table. This can be optimized to O(T) since each row only depends on the previous one.

5 hours ago

ANIRUDH • 0

Kota

Problem-3: Selling Apples by Count

Given a collection of N apples, each with a specific weight, and an integer K, we need to select a subset of apples to sell. The constraint for the selected subset is that the difference between the weight of the heaviest and lightest apple must not exceed K. The goal is to return the maximum number of apples that can be in such a valid subset.

Solution 1: Brute-Force Approach

This solution attempts to solve the problem by generating every possible subset of apples, checking if each subset is valid, and keeping track of the size of the largest valid subset found. This approach is correct but computationally infeasible for the given constraints (N up to 10,000), as the number of subsets grows exponentially.

The logic is as follows:

1. Generate Subsets: Iterate through all 2N possible subsets of the given apples.

2. Validate Each Subset: For each subset, find the minimum and maximum weight.

3. Check Constraint: If max_weight - min_weight <= K, the subset is valid.

4. Track Maximum Size: Keep a running maximum of the sizes of all valid subsets encountered.

5. Return Result: After checking all subsets, return the overall maximum size.

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int brute_force_max_apples(const vector<int>& weights, int K) {
    int n = weights.size();
    int max_size = 0;

    for (int mask = 1; mask < (1 << n); ++mask) {
        int min_w = INT_MAX;
        int max_w = INT_MIN;
        int count = 0;

        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                min_w = min(min_w, weights[i]);
                max_w = max(max_w, weights[i]);
                count++;
            }
        }

        if (max_w - min_w <= K) {
            max_size = max(max_size, count);
        }
    }

    return max_size;
}

int main() {
    vector<int> weights = {1, 5, 6, 2};
    int K = 3;
    cout << brute_force_max_apples(weights, K) << endl;
    return 0;
}

Complexity Analysis

Let N be the number of apples.

• Time Complexity: O(Ncdot2N). There are 2N subsets, and for each, finding the min/max and size takes up to O(N) time.

• Space Complexity: O(N). Space is needed to store the largest subset.

Solution 2: Sorting and Sliding Window (Optimal)

This solution leverages a key insight to transform the problem into a much simpler one. By sorting the apple weights, any optimal subset must correspond to a contiguous subarray of the sorted weights. This reduces the problem from an exponential subset search to a linear-time scan. The sliding window technique is then used to efficiently find the longest such valid subarray.

The logic is as follows:

1. Sort: Sort the array of apple weights in non-decreasing order. This is the critical step.

2. Initialize Sliding Window: Use two pointers, left and right, both starting at index 0. These define the current window (subarray).

3. Expand Window: Iterate through the array with the right pointer, expanding the window one element at a time.

4. Check Constraint and Shrink Window: After each expansion, check if the window is valid: weights[right] - weights[left] <= K. Since the array is sorted, these are the max and min elements in the window.

   • If the condition is violated, shrink the window from the left by incrementing the left pointer until the condition is met again.

5. Update Maximum Length: At each step where the window is valid, its length (right - left + 1) is a candidate for the answer. Update a max_length variable accordingly.

6. Return Result: After the right pointer has traversed the entire array, max_length will hold the answer.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int max_apples_in_range_cpp(vector<int>& weights, int K) {
    int n = weights.size();
    if (n == 0) {
        return 0;
    }

    sort(weights.begin(), weights.end());

    int left = 0;
    int max_length = 0;

    for (int right = 0; right < n; ++right) {
        while (weights[right] - weights[left] > K) {
            left++;
        }
        
        int current_length = right - left + 1;
        if (current_length > max_length) {
            max_length = current_length;
        }
    }
            
    return max_length;
}

Complexity Analysis

Let N be the number of apples.

• Time Complexity: O(NlogN). The algorithm is dominated by the initial sorting step. The subsequent sliding window pass takes only O(N) time, as each pointer traverses the array at most once.

• Space Complexity: O(1) or O(N), depending on the space complexity of the sorting algorithm used. The sliding window itself only requires constant extra space.