Construct a binary string of length K from the array according to the given conditions

In this tutorial, we need to construct a binary string of length K. If the sum of subsets equal to I can be achieved using array elements, then its i-th index Should contain "1". We will learn two ways to solve the problem. In the first approach, we will use dynamic programming methods to check if it is possible that the sum of subsets is equal to index "I". In the second method, we will use bitset to find all possible sums through array elements.

Problem Statement - We are given an array containing N integers. Additionally, we are given an integer M representing the length of the binary string. We need to create a binary string of length M such that it obeys the following conditions.

• The character at index "I" is 1 if we can find a subset from the array whose sum equals index "I"; otherwise it is 0.

• My index starts from 1.

ExampleExample

Input –  arr = [1, 2] M = 4

Output – 1110

illustrate

• The subset whose sum equals 1 is {1}.

• The subset whose sum equals 2 is {2}.

• The subset whose sum equals 3 is {1, 2}.

• We can't find a subset that sums to 4, so we put 0 at the 4th index.

Input –  arr = [1, 3, 1] M = 9

Output – 111110000

illustrate

We can create all possible combinations so that the sum is between 1 and 5. So, the first 5 characters are 1 and the last 4 characters are 0.

Input –  arr = [2, 6, 3] M = 6

Output – 011011

illustrate

We cannot get a sum equal to 1 and 4 using array elements, so we place 0 at the first and fourth index positions.

method 1

In this method we will use dynamic programming to check if we can construct a sum equal to index 'I' using array elements. We will check it for each index and append 1 or 0 to a binary string.

algorithm

• Step 1 - Create a vector of size N and initialize it with an integer value. Also, define a "bin" variable of type string and initialize it with an empty string.

• Step 2 - Use a for loop to make the total number of iterations equal to the string length.

• Step 3 - In the for loop, call the isSubsetSum() function by passing the array N and the index value as parameters.

• Step 4 - If the isSubsetSum() function returns true, append "1" to "bin". Otherwise, append "0" to "bin".

• Step 5 - Define isSubsetSum() function to check if summing can be done using array elements.

• Step 5.1 - Define a two-dimensional vector named dpTable.

• Step 5.2 - Initialize 'dpTable[i][0]' to true since a sum of zero is always possible. Here, 'I' is the index value.

• Step 5.3 - Initialize 'dpTable[0][j]' to false since the sum of empty arrays is not possible.

• Step 5.4 - Now, use two nested loops. The first loop iterates from 1 to N and the other loop iterates from 1 to sum.

• Step 5.5 - In the for loop, if the value of the current element is greater than the sum, ignore it.

• Step 5.6 − Otherwise, include or exclude elements to get the sum.

• Step 5.7 − Return ‘dpTable[N][sum]’ containing the result.

Example

#include <iostream>
#include <vector>
using namespace std;
// Function to check if subset-sum is possible
bool isSubsetSum(vector<int> &arr, int N, int sum){
   vector<vector<bool>> dpTable(N + 1, vector<bool>(sum + 1, false));
   
   // Base cases
   for (int i = 0; i <= N; i++)
   
      // If the sum is zero, then the answer is true
      dpTable[i][0] = true;
      
   // for an empty array, the sum is not possible
   for (int j = 1; j <= sum; j++)
      dpTable[0][j] = false;
      
   // Fill the dp table
   for (int i = 1; i <= N; i++){
      for (int j = 1; j <= sum; j++){
      
         // if the current element is greater than the sum, then we can't include it
         if (arr[i - 1] > j)
            dpTable[i][j] = dpTable[i - 1][j];
            
         // else we can either include it or exclude it to get the sum
         else
            dpTable[i][j] = dpTable[i - 1][j] || dpTable[i - 1][j - arr[i - 1]];
      }
   }
   
   // The last cell of the dp table contains the result
   return dpTable[N][sum];
}
int main(){

   // Given M
   int M = 9;
   
   // Creating the vector
   vector<int> arr = {1, 3, 1};
   
   // getting the size of the vector
   int N = arr.size();
   
   // Initializing the string
   string bin = "";
   
   // Making k iteration to construct the string of length k
   for (int i = 1; i <= M; i++){
   
      // if the subset sum is possible, then add 1 to the string, else add 0
      if (isSubsetSum(arr, N, i)){
         bin += "1";
      }
      else{
         bin += "0";
      }
   }
   
   // print the result.
   cout << "The constructed binary string of length " << M << " according to the given conditions is ";
   cout << bin;
   return 0;
}

Output

The constructed binary string of length 9 according to the given conditions is 111110000

Time complexity - O(N^3), because the time complexity of isSubsetSum() is O(N^2) and we call it N times in the driver code.

Space complexity - O(N^2), because we use a two-dimensional vector in the isSubsetSum() function.

How to use Bitset

In this method we will use bitsets to find all possible sum values ​​by combining different elements of the array. Here, bitset means it creates a binary string. In the resulting bit set, each bit of it represents whether the sum is likely to be equal to a specific index, and we need to find it here.

algorithm

• Step 1 - Define the array and M. Additionally, define the createBinaryString() function.

• Step 2 - Next, define the set of bits of the desired length, which will create a binary string.

• Step 3 - Initialize bit[0] to 1, since a sum of 0 is always possible.

• Step 4 - Use a for loop to iterate over the array elements

.

• Step 5 - First, perform a "bit" left shift operation on the array elements. The resulting value is then ORed with the bit value.

• Step 6 − Print the value of the bit set from index 1 to M.

Example

#include <bits/stdc++.h>
using namespace std;
// function to construct the binary string
void createBinaryString(int array[], int N, int M){
   bitset<100003> bit;
   
   // Initialize with 1
   bit[0] = 1;
   
   // iterate over all the integers
   for (int i = 0; i < N; i++){
      // perform left shift by array[i], and OR with the previous value.
      bit = bit | bit << array[i];
   }
   
   // Print the binary string
   cout << "The constructed binary string of length " << M << " according to the given conditions is ";
   for (int i = 1; i <= M; i++){
      cout << bit[i];
   }
}
int main(){

   // array of integers
   int array[] = {1, 4, 2};
   int N = sizeof(array) / sizeof(array[0]);
   
   // value of M, size of the string
   int M = 8;
   createBinaryString(array, N, M);
}

Output

The constructed binary string of length 8 according to the given conditions is 11111110

Time complexity - O(N) since we use a single for loop.

Space complexity - O(N), because we store the value of the bit set.

in conclusion

Here, we optimized the second method, which is better than the first method in terms of space and time complexity. However, the second method may be difficult for beginners to understand if you don't have an understanding of bit sets.

The above is the detailed content of Construct a binary string of length K from the array according to the given conditions. For more information, please follow other related articles on the PHP Chinese website!