Given an array arr[] of size N and an integer K, the task is to find the size of the largest subset possible having a sum at most K when only one element can be halved (the halved value will be rounded to the closest greater integer).
Examples:
Input: arr[] = {4, 4, 5}, K = 15
Output: 3
Explanation: 4+4+5 = 13 which is less than 15. So subset can have all elements.Input: arr[3] = {2, 3, 5}, K = 9
Output: 3
Explanation: 2 + 3 = 5 which is less than 9
2 + 3 + 5 = 10 which is greater than 9, So cannot be part of subset.
After halving i.e. ceil [5/2] = 3, sum = 2+3+3 = 8 which is less than 9.
So all 3 elements can be part of subset.Input: arr[8] = {1, 2, 3, 4, 5, 6, 7, 8}, K = 20
Output: 6
Explanation: 1+2+3+4+5 = 15 which is less than 20
15 + 6 = 21 which is greater than 20.
After halving the value i.e. ceil [6/2] = 3
15 + 3 = 18 which is less than 20. So it can be part of subset.
Approach: The given problem can be solved using Sorting method based on the following idea:
In a sorted array keep on performing sum from i = 0 to N-1. If at any moment sum is greater than K, that element can only be included if after halving that value the sum is at most K
Follow the steps mentioned below to solve the problem:
- Sort the array in ascending order.
- Declare a variable (say Sum) to maintain the sum.
- Traverse the array from i = 0 to N-1:
- Add arr[i] to Sum.
- If Sum is greater than K, then make arr[i] = ceil(arr[i]/2) and check if that sum is less than K or not.
- If Sum is less than K then continue iteration.
- Increment the size of the subset.
- Return the size of the subset.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find total number of elementint findcount(int arr[], int n, int m){ int ans = n, sum = 0, count = 0; // Sort the array sort(arr, arr + n); for (int i = 0; i < n; i++) { // Round up to the ceil value if (sum + (arr[i] + 1) / 2 > m) { ans = i; break; } // Sum of the array elements sum += arr[i]; // Size of the subset count++; } return count;}// Driver codeint main(){ int N = 8, K = 20; int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; // Function call cout << findcount(arr, N, K); return 0;} |
Java
// JAVA program for the above approachimport java.util.*;class GFG { // Function to find total number of element public static int findcount(int arr[], int n, int m) { int ans = n, sum = 0, count = 0; // Sort the array Arrays.sort(arr); for (int i = 0; i < n; i++) { // Round up to the ceil value if (sum + (arr[i] + 1) / 2 > m) { ans = i; break; } // Sum of the array elements sum += arr[i]; // Size of the subset count++; } return count; } // Driver code public static void main(String[] args) { int N = 8, K = 20; int arr[] = new int[] { 1, 2, 3, 4, 5, 6, 7, 8 }; // Function call System.out.print(findcount(arr, N, K)); }}// This code is contributed by Taranpreet |
Python3
# Python solution based on above approach# Function to find total number of elementdef findcount(n, k, arr): # Sort the array arr.sort() sum = 0 count = 0 for i in range(n): # Round up to the ceil value if (sum + (arr[i] + 1) / 2 > k): ans = i break # Sum of the array elements sum += arr[i] # Size of the subset count = count + 1 return(count) # driver coden = 8k = 20arr = [1, 2, 3, 5, 4, 6, 7, 8]result = findcount(n,k,arr)print(result) # This code is contributed by greeshmapslp. |
C#
// C# program for the above approachusing System;class GFG { // Function to find total number of element static int findcount(int[] arr, int n, int m) { int ans = n, sum = 0, count = 0; // Sort the array Array.Sort(arr); for (int i = 0; i < n; i++) { // Round up to the ceil value if (sum + (arr[i] + 1) / 2 > m) { ans = i; break; } // Sum of the array elements sum += arr[i]; // Size of the subset count++; } return count; } // Driver code public static void Main() { int N = 8, K = 20; int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8 }; // Function call Console.Write(findcount(arr, N, K)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// JavaScript program for the above approach// Function to find total number of elementfunction findcount(arr, n, m){ var ans = n; var sum = 0; var count = 0; // Sort the array arr.sort(); for (var i = 0; i < n; i++) { // Round up to the ceil value if (sum + Math.floor((arr[i] + 1) / 2) > m) { ans = i; break; } // Sum of the array elements sum += arr[i]; // Size of the subset count++; } return count;}// Driver codevar N = 8;var K = 20;var arr = [ 1, 2, 3, 4, 5, 6, 7, 8 ];// Function calldocument.write(findcount(arr, N, K));// This code is contributed by phasing17</script> |
6
Time Complexity: O(N * logN)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
