Determine the minimum step for a subsequence with at most 1 based on the given conditions

The purpose of this article is to implement a program to find the minimum steps to determine a subsequence of maximum 1 second based on a given condition.

As we all know, a one-dimensional array containing null-terminated characters can be used to define a string.

Given a string Str of length K, where K is always an even number and contains the characters "0", "1" and "?" Divide the string into two separate strings, we call them For Str1 and Str2, each string will contain characters at even values ​​of Str and odd values ​​of Str. The goal is to determine the minimum number of steps required to predict the highest number of 1's in two strings (Str1 or Str2). Selects a character for Str1 or Str2 in one step. Selects "0" if the character is zero, "1" if the character is one, and "?" if it is a 1 or 0 character.

Problem Statement

Implement a program to find the minimum steps to determine the maximum 1 second subsequence based on given conditions

Example 1

Input: Str = “?10?0?”

Output: 4

illustrate

• Step 1 - Here Str[0] is "?"

So select "0" as the character for Str1.
Which implies Str1=”0″, Str2=”″.

• Step 2 - Here Str[1] is "1"

Select "1" as the character for Str2.
Which implies Str1=”0″, Str2=”1″.

• Step 3 - Here Str[2] is "0"

Select "0" as the character for Str1.
Which implies Str1=”00″, Str2=”1″.

• Step 4 - Here Str[3] is "?"

Select "1" as the character for Str2.
Which implies Str1=”00″, Str2=”11″.

No matter what number the remaining index chooses, Str2 will have more 1's after step 4.

Example 2

Input: Str = “1?0??0110”

Output: 4

illustrate

• Step 1 - Here Str[0] is "1"

So select "1" as the character for Str1.
Which implies Str1=”1″, Str2=”″.

• Step 2 - Here Str[1] is "?"

Select "1" as the character for Str2.
Which implies Str1=”1″, Str2=”1″.

• Step 3 - Here Str[2] is "0"

Select "0" as the character for Str1.
Which implies Str1=”10″, Str2=”1″.

• Step 4 - Here Str[3] is "?"

Select "1" as the character for Str2.
Which implies Str1=”10″, Str2=”11″.

• Step 5 - Here Str[4] is "?"

Select "0" as the character for Str1.
Which implies Str1=”100″, Str2=”11″.

• Step 6 - Here Str[5] is "0"

Select "0" as the character for Str2.
Which implies Str1=”100″, Str2=”111″.

• Step 7 - Here Str[6] is "1"

Select "1" as the character for Str1.
Which implies Str1=”1001″, Str2=”111″.

No matter what number the remaining index chooses, Str2 will have more 1's after step 7.

solution

To find the minimum steps to determine the maximum 1 second subsequence based on the given conditions, we use the following approach.

Given below is a method to solve this problem and find the minimum steps to determine a subsequence with a maximum of 1 second based on the given conditions.

The goal is to solve the problem recursively and arrive at a solution after considering each alternative.

The term "recursion" is nothing more than the process of a function calling itself, whether directly (i.e. without intermediaries) or indirectly. This equivalent function is said to be a recursive function. Additionally, recursive algorithms can be used to solve various problems with relative ease.

algorithm

Algorithm to find the minimum step that determines the maximum 1 second subsequence based on the given conditions given below

• Step 1 - Get Started

• Step 2 - Define the recursive function.

• Step 3 - Define the string Str, the integer i, the integers count1 and count2, which are used to store the number up to i in Str1 and Str2 respectively.

• Step 4 - Define integers n1 and n2 to store the available positions in Str1 and Str2

• Step 5 - If i equals m, then both Str1 and Str2 are fully filled and the answer can now be expected with certainty. So please reply 0.

• Step 6 - If count1 exceeds the product of n2 and count2, return 0 because Str1 will now have more than Str2 even after selecting all values ​​in Str2 value.

For the above reasons, if count2 exceeds the product of n1 and count1, 0 ​​is returned.

• Step 7 - Verify that i is equal to even or odd number after testing the base instance. If i is even, Str1 will select this index; if not, Str2.

Since the number of accessible positions in the string will be reduced by one position after padding, it is reduced by n1 or n2 depending on the currently padded string.

• Step 8 - Assume that the current character is '?', that is, s[i] = '? ' Then perform two recursive calls to select "1" and "0", and 1 is combined into the two and returns the minimum of the two.

Otherwise, make a phone call and then add a phone number to get the answer.

The response to this query will be provided by the final recursive call.

• Step 8 - Stop

Example: C program

This is a C program implementation of the algorithm written above to find the minimum steps to determine a maximum subsequence of 1 second based on a given condition

// the C++ program of the above written algorithm
#include <bits/stdc++.h>
using namespace std;

// the function in order find the minimum number of the steps recursively  needed by combining both the 2 strings
int minimumSteps(string& Str, int cnt1, int cnt2,int n1, int n2, int m,int i){

   // check whetherthe current pointer reach //the end
   if (i == m) {
      return 0;
   }
    
   // the Condition which indicates here that one string does more ones than the other regardless of which number is opted  for theindexes which is remaining
   if (cnt1 > (n2 + cnt2)
         || cnt2 > (n1 + cnt1)) {
      return 0;
   }
   int ch1 = 0;
   int ch2 = 0;
    
   // on condition that i is found to be even, then choose the character for Str
   if (i % 2 == 0) {
      if (Str[i] == '?') {
         return min( 1 + minimumSteps(Str, i + 1,  cnt1 + 1, cnt2, n1 - 1, n2, m), 1 + minimumSteps( Str, i + 1, cnt1, cnt2, n1 - 1, n2, m));
      } else if (Str[i] == '1') {
         ch1 = 1 + minimumSteps(Str, i + 1, cnt1 + 1, cnt2, n1 - 1, n2, m);
         return ch1;
      } else {
         ch2 = 1 + minimumSteps(Str, i + 1, cnt1, cnt2, n1 - 1, n2, m);
         return ch2;
      }
   }
   else {
      if (Str[i] == '?') {
         return min(1 + minimumSteps(Str, i + 1, cnt1, cnt2 + 1, n1, n2 - 1, m),1 + minimumSteps(Str, i + 1,cnt1, cnt2, n1, n2 - 1, m));
      } else if (Str[i] == '1') {
         ch1 = 1+ minimumSteps(Str, i + 1, cnt1, cnt2 + 1, n1, n2 - 1, m);
         return ch1;
      } else {
         ch2 = 1+ minimumSteps( Str, i + 1, cnt1, cnt2, n1, n2 - 1, m);
         return ch2;
      }
   }
}
int main(){
   string str = "?10?0?01";
   int M = str.size();
   cout << minimumSteps(str, 0, 0, 0, M / 2, M / 2, M);
   return 0;
}

Output

1

in conclusion

Similarly, we can find the minimum number of steps to determine the subsequence with a maximum of 1s based on the given conditions

This paper addresses the challenge of obtaining the minimum number of steps to determine the maximum 1 second subsequence given a condition.

C programming code is provided here along with an algorithm to find the minimum step that determines the maximum 1 second subsequence given the conditions.

The above is the detailed content of Determine the minimum step for a subsequence with at most 1 based on the given conditions. For more information, please follow other related articles on the PHP Chinese website!