Given an array, arr[] and integer K, the task is to find the maximum number of non-overlapping subsets such that the sum of the subsets is strictly greater than K when you may also change the value of each element to the maximum value of the particular subset.
Examples:
Input: arr[]= {90, 80, 70, 60, 50, 100}, K = 180
Output: 2Input: arr[] = {3, 2, 1}, K = 8
Output: 1
Approach: To solve the problem follow the below idea:
In order to form a maximum number of subsets we need to form a sequence with a minimum number of elements as well as the sum of values of elements should be greater than K. We start forming subsequences with elements having maximum value and changing the rest of the element value to the maximum value in the same subsequence.
Follow the steps mentioned below to implement the idea:
- Sort the array arr[] in non-increasing order
- Take a pointer i initially at 0.
- Iterate over the array and form subset with arr[i] with minimum possible elements.
- Check if the elements already used + the elements required (d/arr[i] +1) for forming the current subset is less than or equal to the total number of elements then increase the subset formed and move pointer i to the next index.
- Else, a return number of subsequences is formed as there are not enough elements available to form more subsets.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function for finding out maximum// subsequences formedint maximumSequence(vector<int>& arr, int K, int n){ // Sorting array in non-increasing order sort(arr.begin(), arr.end(), greater<int>()); int i = 0; int sequence_formed = 0; int elements_required = 0; while (elements_required + (K / arr[i]) + 1 <= n) { // Increasing Sequence formed sequence_formed += 1; // After forming of a new sequence, // increasing elements used who have // assigned to any of the subsequence elements_required += ((K / arr[i]) + 1); i++; } return sequence_formed;}// Driver codeint main(){ vector<int> power = { 90, 80, 70, 60, 50, 100 }; int n = power.size(); int k = 180; // Function call cout << maximumSequence(power, k, n);} |
Python3
def maximum_sequence(arr, K, n): # Sorting array in non-increasing order arr.sort(reverse=True) i = 0 sequence_formed = 0 elements_required = 0 while elements_required + (K // arr[i]) + 1 <= n: # Increasing Sequence formed sequence_formed += 1 # After forming of a new sequence, # increasing elements used who have # assigned to any of the subsequence elements_required += ((K // arr[i]) + 1) i += 1 return sequence_formed# Driver codeif __name__ == "__main__": power = [90, 80, 70, 60, 50, 100] n = len(power) k = 180 # Function call print(maximum_sequence(power, k, n))#This code is contributed by sanjanasikarwar24 |
Java
import java.util.Arrays;import java.util.Collections;import java.util.List;public class Main { // Function for finding out maximum // subsequences formed public static int maximumSequence(List<Integer> arr, int K, int n) { // Sorting array in non-increasing order Collections.sort(arr, Collections.reverseOrder()); int i = 0; int sequence_formed = 0; int elements_required = 0; while (elements_required + (K / arr.get(i)) + 1 <= n) { // Increasing Sequence formed sequence_formed += 1; // After forming of a new sequence, // increasing elements used who have // assigned to any of the subsequence elements_required += ((K / arr.get(i)) + 1); i++; } return sequence_formed; } public static void main(String[] args) { List<Integer> power = Arrays.asList(90, 80, 70, 60, 50, 100); int n = power.size(); int k = 180; // Function call System.out.println(maximumSequence(power, k, n)); }}//This code is contributed by sanjanasikarwar24 |
C#
using System;using System.Collections.Generic;using System.Linq;namespace ConsoleApp{ class Program { // Function for finding out maximum // subsequences formed public static int MaximumSequence(List<int> arr, int K, int n) { // Sorting array in non-increasing order arr.Sort((a, b) => b.CompareTo(a)); int i = 0; int sequence_formed = 0; int elements_required = 0; while (elements_required + (K / arr[i]) + 1 <= n) { // Increasing Sequence formed sequence_formed += 1; // After forming of a new sequence, // increasing elements used who have // assigned to any of the subsequence elements_required += ((K / arr[i]) + 1); i++; } return sequence_formed; } static void Main(string[] args) { List<int> power = new List<int> { 90, 80, 70, 60, 50, 100 }; int n = power.Count; int k = 180; // Function call Console.WriteLine(MaximumSequence(power, k, n)); } }}//This code is contributed by sanjanasikarwar24 |
Javascript
using System;using System.Collections.Generic;using System.Linq;namespace ConsoleApp{ class Program { // Function for finding out maximum // subsequences formed public static int MaximumSequence(List<int> arr, int K, int n) { // Sorting array in non-increasing order arr.Sort((a, b) => b.CompareTo(a)); int i = 0; int sequence_formed = 0; int elements_required = 0; while (elements_required + (K / arr[i]) + 1 <= n) { // Increasing Sequence formed sequence_formed += 1; // After forming of a new sequence, // increasing elements used who have // assigned to any of the subsequence elements_required += ((K / arr[i]) + 1); i++; } return sequence_formed; } static void Main(string[] args) { List<int> power = new List<int> { 90, 80, 70, 60, 50, 100 }; int n = power.Count; int k = 180; // Function call Console.WriteLine(MaximumSequence(power, k, n)); } }}//This code is contributed by sanjanasikarwar24 |
Output
2
Time Complexity: O(N * logN)
Auxiliary Space: O(1)
Related Articles:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
