Given an array arr[] consisting of N integers, and an integer K, the task is to construct a binary string of length K satisfying the following conditions:
- The character at ith index is ‘1′ if a subset with sum i can be formed from the array.
- Otherwise, the character at ith index is ‘0’.
Examples:
Input: arr[] = {1, 4}, K = 5
Output: 10011
Explanation:
Character at 1st index can be made by ‘1’ considering the subset {1}.
Character at 4th index can be made by ‘1’ considering the subset {4}.
Character at 5th index can be made by ‘1’ considering the subset {1, 4}.Input: arr[] = {1, 6, 1}, K = 8
Output: 11000111
Approach: The idea is to use a greedy approach to solve this problem. Below are the steps:
- Initialize a bitset, say bit[], of size 105 + 5 and set bit[0] = 1.
- Traverse through the array and for each array element arr[i], update bit as bit |= bit << arr[i] to have bit p if p can be obtained as a subset sum.
- At ith iteration, bit[i] stores the initial sum and after performing bit << arr[i], all bits are shifted by arr[i]. Therefore, bit p becomes p + arr[i].
- Finally, bit | (bit << arr[i]) merges these two cases, whether to consider the ith position or not.
- Iterate from 1 to K and print every value bit[i] as the required binary string.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// To construct the// required binary stringbitset<100003> bit;// Function to construct binary string// according to the given conditionsvoid constructBinaryString(int arr[], int N, int K){ // Initialize with 1 bit[0] = 1; // Traverse the array for (int i = 0; i < N; i++) { // To check if the i-th integer // needs to be considered or not bit |= bit << arr[i]; } // Print the binary string for (int i = 1; i <= K; i++) { cout << bit[i]; }}// Driver Codeint main(){ // Given array int arr[] = { 1, 6, 1 }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); // Given K int K = 8; constructBinaryString(arr, N, K);} |
Java
// Java code to implement the approachimport java.util.Arrays;class BinaryString { public static void main(String[] args) { // Given array int[] arr = {1, 6, 1}; // Size of the array int N = arr.length; // Given K int K = 8; constructBinaryString(arr, N, K); } // Function to construct binary string // according to the given conditions static void constructBinaryString(int[] arr, int N, int K) { // Initialize with 1 int bit = 1; // Traverse the array for (int i = 0; i < N; i++) { // To check if the i-th integer // needs to be considered or not bit |= (bit << arr[i]); } // Print the binary string String binaryString = Integer.toBinaryString(bit); System.out.println(binaryString.substring(1, K)); }}// This code is contributed by phasing17 |
Python3
# Python program for the above approach# To construct the# required binary string#bit = [0]*100003# Function to construct binary string# according to the given conditionsdef constructBinaryString(arr,N, K): # Initialize with 1 bit = 1 # Traverse the array for i in range(0, N): # To check if the i-th eger # needs to be considered or not bit |= bit << arr[i] # Print the binary string #for i in range(1,K): # print(bit[i]) bit = bin(bit).replace("0b", "") print(bit[1:K + 1]) # Driver Code# Given arrayarr = [1, 6, 1]# Size of the arrayN = len(arr)# Given KK = 8constructBinaryString(arr, N, K)# This code is contributed by shubhamsingh10 |
C#
using System;using System.Linq;namespace BinaryString { class Program { static void Main(string[] args) { // Given array int[] arr = { 1, 6, 1 }; // Size of the array int N = arr.Length; // Given K int K = 8; ConstructBinaryString(arr, N, K); } // Function to construct binary string // according to the given conditions static void ConstructBinaryString(int[] arr, int N, int K) { // Initialize with 1 int bit = 1; // Traverse the array for (int i = 0; i < N; i++) { // To check if the i-th integer // needs to be considered or not bit |= (bit << arr[i]); } // Print the binary string string binaryString = Convert.ToString(bit, 2); Console.WriteLine(binaryString.Substring(1, K)); } }}// This code is contributed by phasing17. |
Javascript
// JavaScript program for the above approach// To construct the// required binary string//bit = [0]*100003// Function to construct binary string// according to the given conditionsfunction constructBinaryString(arr,N, K){ // Initialize with 1 let bit = 1 // Traverse the array for (var i = 0; i < N; i++) // To check if the i-th eger // needs to be considered or not bit |= (bit << arr[i]) // Print the binary string //for i in range(1,K): // print(bit[i]) bit = bit.toString(2) console.log(bit.substring(1, K + 1))} // Driver Code// Given arraylet arr = [1, 6, 1]// Size of the arraylet N = arr.length// Given Klet K = 8constructBinaryString(arr, N, K)// This code is contributed by phasing17 |
Output:
11000111
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
