Based on the greedy strategy, the target number is constructed by the sum of digital strings containing only 0 and 1

This article details an algorithm for generating a target number by superimposing strings containing only the digits 0 and 1. The core strategy is the greedy method, that is, in each iteration, build the largest 0/1 number string possible, decide to place 1 or 0 by checking whether each bit of the target number is greater than 0, and reduce the number of digits of the target number accordingly. Finally, the number of iterations is the minimum number of 0/1 number strings required.

Goal and problem description

Given a string S representing a number, our goal is to find the minimum number of number strings consisting only of '0' and '1', such that their sum is exactly equal to S. For example, to generate the number 3401, we can break it down into 1101 1100 1100 0100. In this case, we need 4 such number strings.

Core algorithm idea: greedy strategy

The key to solving this problem is to adopt a greedy strategy. In order to minimize the number of required number strings, we should "consume" as many digits of the target number as possible in each iteration, that is, build the largest number string that only contains '0' and '1'.

The specific steps are as follows:

1. Initialization: Convert each bit of the target number S into an integer and store it in an array for bit operations. At the same time, the integer form of S is retained for sum checking.
2. Iterative build: When the integer form of the target number is still greater than 0, repeat the following process:
   • Create an empty StringBuilder to build the current 0/1 number string.
   • Iterate over the array storing the target number of digits. For each number in the array (i.e. each digit of the target number):
     • If the number in the current bit is greater than 0, it means we can "use" this bit. Append '1' to StringBuilder.
     • If the number in the current bit is equal to 0, it means that there is no available value for this bit. Append '0' to StringBuilder.
   • After completing the traversal, we got a 0/1 number string in the form of "1101" or "0100".
   • Convert this 0/1 number string to an integer.
   • Subtract this newly generated integer from the integer form of the target number.
   • At the same time, for those bits in the array to which we appended a '1', the value is decremented by 1 (because we "consumed" one unit of this bit).
   • Record the number of iterations (that is, the number of 0/1 number strings generated).
3. Termination condition: The iteration ends when the integer form of the target number becomes 0. At this time, the number of iterations recorded is the minimum number of 0/1 number strings required.

Example Demo: Build 3401

Let us take S = "3401" as an example to demonstrate the algorithm process step by step:

1. initialization:

   • arr = [3, 4, 0, 1]
   • num = 3401
   • count = 0 (used to record the number of generated digital strings)

2. First iteration:

   • Based on arr = [3, 4, 0, 1], construct a 0/1 number string.
   • The temp string is "1101".
   • var = 1101.
   • num = 3401 - 1101 = 2300.
   • Update arr (decrease 1 according to the position of '1' in temp): arr becomes [2, 3, 0, 0].
   • count = 1.

3. Second iteration:

   • Based on arr = [2, 3, 0, 0], construct a 0/1 number string.
   • The temp string is "1100".
   • var = 1100.
   • num = 2300 - 1100 = 1200.
   • Update arr: arr becomes [1, 2, 0, 0].
   • count = 2.

4. Third iteration:

   • Based on arr = [1, 2, 0, 0], construct a 0/1 number string.
   • The temp string is "1100".
   • var = 1100.
   • num = 1200 - 1100 = 100.
   • Update arr: arr becomes [0, 1, 0, 0].
   • count = 3.

5. Fourth iteration:

   • Based on arr = [0, 1, 0, 0], construct a 0/1 number string.
   • The temp string is "0100".
   • var = 100.
   • num = 100 - 100 = 0.
   • Update arr: arr becomes [0, 0, 0, 0].
   • count = 4.

6. Termination: num becomes 0 and the loop ends. The final result is count = 4.

Java code implementation

The following is a Java implementation based on the above greedy strategy:

import java.util.Scanner;

public class ZeroOneStringSum {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Please enter the target numeric string S: ");
        String s = sc.next();
        int len ​​= s.length();

        // Store each digit of the target number into an array for easy operation int[] arr = new int[len];
        for (int i = 0; i  0) {
            StringBuilder currentZeroOneNumStr = new StringBuilder();

            // Traverse each bit, construct the current 0/1 number string, and update the arr array synchronously for (int i = 0; i  0) {
                    currentZeroOneNumStr.append(1); // If the current bit is greater than 0, use 1
                    arr[i]--; // Only when this bit is used to generate '1', decrement this bit of the original number by 1
                } else {
                    currentZeroOneNumStr.append(0); // Otherwise use 0
                }
            }

            String generatedStr = currentZeroOneNumStr.toString();

The above is the detailed content of Based on the greedy strategy, the target number is constructed by the sum of digital strings containing only 0 and 1. For more information, please follow other related articles on the PHP Chinese website!