Given an array of integer nums[] and a positive integer K, the task is to find the maximum number of integers that can be selected from the array such that the sum of the number of 1s in their binary representation is at most K.
Examples:
Input: nums[] = [3, 9, 4, 6], K = 3
Output: 2
Explanation: The maximum number of integers that can be selected is 2 since the sum of the number of 1s in the binary representation of 3 and 4 is 3, which is equal to K.Input: nums[] = [1, 2, 3, 4, 5], K = 5
Output: 4
Explanation: The maximum number of integers that can be selected is 4 since the sum of the number of 1s in the binary representation of 1, 2, 3, and 4 is 5, which is equal to K.
Approach: This problem can be solved using dynamic programming
We can create a two-dimensional array dp, where dp[i][j] represents the maximum number of integers that can be selected from the first i elements of the array such that the sum of the number of 1s in their binary representation is at most j.
We can fill the dp array using the following recursive formula:
- dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – bit_sum] + 1)
- where bit_sum is the number of 1s in the binary representation of nums[i – 1].
Follow the steps mentioned below to solve the problem:
- Initialize a two-dimensional array dp, where dp[i][j] represents the maximum number of integers that can be selected from the first i elements of the array such that the sum of the number of 1s in their binary representation is at most j.
- Fill the dp array using the following recursive formula:
- dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – bit_sum] + 1) where bit_sum is the number of 1s in the binary representation of nums[i – 1].
- Return the value of dp[n][k], where n is the length of the nums array.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>#include <bitset>using namespace std;// Function to find the maximum number of// integers that can be selected such that// the sum of the number of 1s in their// binary representation is at most kint maximum_int_count(vector<int> nums, int k){ // Initialize the dp array with 0s vector<vector<int> > dp(nums.size() + 1, vector<int>(k + 1, 0)); // Fill the dp array using the // recursive formula for (int i = 1; i <= nums.size(); i++) { for (int j = 0; j <= k; j++) { bitset<32> bits(nums[i - 1]); int bit_sum = bits.count(); dp[i][j] = (j >= bit_sum) ? max(dp[i - 1][j], dp[i - 1][j - bit_sum] + 1) : dp[i - 1][j]; } } // Return the maximum number of integers // that can be selected return dp[nums.size()][k];}// Driver codeint main(){ vector<int> nums{ 3, 9, 4, 6 }; int k = 3; // Function Call cout << maximum_int_count(nums, k) << endl; nums = { 1, 2, 3, 4, 5 }; k = 5; // Function Call cout << maximum_int_count(nums, k) << endl; return 0;} |
Java
import java.util.*;import java.io.*;public class GFG { // Function to find the maximum number of // integers that can be selected such that // the sum of the number of 1s in their // binary representation is at most k public static int maximumIntCount(Vector<Integer> nums, int k) { // Initialize the dp array with 0s Vector<Vector<Integer>> dp = new Vector<>(nums.size() + 1); for (int i = 0; i <= nums.size(); i++) { dp.add(new Vector<Integer>()); for (int j = 0; j <= k; j++) { dp.get(i).add(0); } } // Fill the dp array using the // recursive formula for (int i = 1; i <= nums.size(); i++) { for (int j = 0; j <= k; j++) { int bitSum = Integer.bitCount(nums.get(i - 1)); dp.get(i).set(j, (j >= bitSum) ? Math.max(dp.get(i - 1).get(j), dp.get(i - 1).get(j - bitSum) + 1) : dp.get(i - 1).get(j)); } } // Return the maximum number of integers // that can be selected return dp.get(nums.size()).get(k); } public static void main(String[] args) { Vector<Integer> nums = new Vector<>(Arrays.asList(3, 9, 4, 6)); int k = 3; // Function Call System.out.println(maximumIntCount(nums, k)); nums = new Vector<>(Arrays.asList(1, 2, 3, 4, 5)); k = 5; // Function Call System.out.println(maximumIntCount(nums, k)); }} |
Python3
# Python code for the above approach:# Function to find the maximum number of# integers that can be selected such that# the sum of the number of 1s in their# binary representation is at most kdef maximum_int_count(nums, k): # Initialize the dp array with 0s dp = [[0]*(k+1) for _ in range(len(nums)+1)] # Fill the dp array using the # recursive formula for i in range(1, len(nums)+1): for j in range(0, k+1): N = nums[i-1] bits = bin(N) bit_sum = bits.count('1') if(j >= bit_sum): dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - bit_sum] + 1) else: dp[i][j] = dp[i-1][j] # Return the maximum number of integers # that can be selected return dp[len(nums)][k]# Driver codenums = [3, 9, 4, 6]k = 3# Function Callprint(maximum_int_count(nums, k))nums = [1, 2, 3, 4, 5]k = 5# Function Callprint(maximum_int_count(nums, k)) |
C#
using System;using System.Linq;using System.Collections.Generic;class Gfg{ // Function to find the maximum number of // integers that can be selected such that // the sum of the number of 1s in their // binary representation is at most k public static int maximum_int_count(List<int> nums, int k) { // Initialize the dp array with 0s int[, ] dp = new int[nums.Count + 1, k + 1]; // Fill the dp array using the // recursive formula for (int i = 1; i <= nums.Count; i++) { for (int j = 0; j <= k; j++) { int bit_sum = Convert.ToString(nums[i - 1], 2) .Count(c = > c == '1'); dp[i, j] = (j >= bit_sum) ? Math.Max( dp[i - 1, j], dp[i - 1, j - bit_sum] + 1) : dp[i - 1, j]; } } // Return the maximum number of integers // that can be selected return dp[nums.Count, k]; } public static void Main(string[] args) { List<int> nums = new List<int>{ 3, 9, 4, 6 }; int k = 3; // Function Call Console.WriteLine(maximum_int_count(nums, k)); nums = new List<int>{ 1, 2, 3, 4, 5 }; k = 5; // Function Call Console.WriteLine(maximum_int_count(nums, k)); }}// This code is contributed by divya_p123. |
Javascript
// JavaScript code for the above approach:function maximumIntCount(nums, k) { // Initialize the dp array with 0s let dp = Array.from({length: nums.length + 1}, () => Array(k + 1).fill(0) ); // Fill the dp array using the // recursive formula for (let i = 1; i <= nums.length; i++) { for (let j = 0; j <= k; j++) { let bitSum = (nums[i - 1].toString(2).match(/1/g) || []).length; dp[i][j] = j >= bitSum ? Math.max(dp[i - 1][j], dp[i - 1][j - bitSum] + 1) : dp[i - 1][j]; } } // Return the maximum number of integers // that can be selected return dp[nums.length][k];}// Driver codelet nums = [3, 9, 4, 6];let k = 3;// Function Callconsole.log(maximumIntCount(nums, k));nums = [1, 2, 3, 4, 5];k = 5;// Function Callconsole.log(maximumIntCount(nums, k));// This code is contributed by hkdass001. |
Output
2 4
Time complexity: O(n * k), where n is the length of the nums array and k is the given integer.
Auxiliary Space: O(n * k), as it uses a two-dimensional array of size n * k.
Related Articles:
- Introduction to Arrays – Data Structures and Algorithms Tutorials
- Introduction to Dynamic Programming – Data Structures and Algorithms Tutorials
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!
