Particiones mínimas de String tales que cada parte sea como máximo K

Dada una string S de tamaño N que consta de dígitos numéricos del 1 al 9 y un número entero positivo K , la tarea es minimizar las particiones de la string de manera que cada parte sea st más K . Si es imposible particionar la string, imprima -1.

Ejemplos:

Entrada: S = “3456”, K = 45
Salida: 2
Explicación: Una forma posible es particionar como 3, 45, 6. 
Otra posibilidad es 3, 4, 5, 6, que usa 3 particiones. 
Ninguna configuración necesita menos de 2 particiones. Por lo tanto, la respuesta es 2.

Entrada: S = “7891634”, K = 21
Salida: 5
Explicación: El número mínimo de particiones es 
7, 8, 9, 16, 3, 4, que utiliza 5 particiones.

Entrada: S = “67142849”, K = 39
Salida: 5

 

Enfoque: El enfoque de este problema se basa en la siguiente idea:

Haga que cada partición tenga un valor lo más grande posible con un límite superior de K .
Un caso límite es si es imposible dividir la string. Sucederá si el dígito máximo en la string es mayor que K ..

Siga los pasos a continuación para resolver este problema:

  • Iterar sobre los caracteres de la string de i = 0 a N-1 :
    • Si el número formado hasta ahora es como máximo K, continúa con esta partición. De lo contrario, aumente el número de particiones.
    • De lo contrario, si el dígito actual es mayor que K , devuelve -1 .
  • Es posible que el último número no se haya tenido en cuenta después de iterar la string, así que compruebe si la última partición es mayor que 0. En caso afirmativo, aumente el número de particiones (por ejemplo, ans ) en 1 .
  • Finalmente, devuelva ans – 1 , ya que necesitamos encontrar el número mínimo de particiones, que es uno menos que los números formados.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for above implementation
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the minimum number
// of partitions
int minimumCommas(string& s, int k)
{
    // Length of the string 's'.
    int n = s.size();
 
    // Store the current number formed.
    long long cur = 0;
 
    // 'ans' stores the final answer.
    int ans = 0;
 
    // Iterate over the string.
    for (int i = 0; i < n; ++i) {
 
        // If we can include this digit in the
        // current number
        if (cur * 10 + (s[i] - '0') <= k) {
 
            // Include this digit in
            // the current number.
            cur = cur * 10 + (s[i] - '0');
        }
        else {
 
            // If 'cur' is '0',
            // it's impossible to partition
            if (cur == 0) {
 
                // Return the integer '-1'
                return -1;
            }
            else {
 
                // Increment the answer 'ans'
                ans++;
 
                // Set cur to the current digit
                cur = s[i] - '0';
            }
        }
    }
 
    // If cur > 0, means the last number is cur
    if (cur > 0) {
 
        // Increment the 'ans'
        ans++;
    }
 
    // Return the number of partitions
    return ans - 1;
}
 
// Driver code
int main()
{
    // Input
    string S = "7891634";
    int K = 21;
 
    // Function call
    cout << minimumCommas(S, K);
    return 0;
}

Java

// JAVA program for above implementation
import java.util.*;
class GFG {
 
    // Function to count the minimum number
    // of partitions
    public static int minimumCommas(String s, int k)
    {
       
        // Length of the string 's'.
        int n = s.length();
 
        // Store the current number formed.
        long cur = 0;
 
        // 'ans' stores the final answer.
        int ans = 0;
 
        // Iterate over the string.
        for (int i = 0; i < n; ++i) {
            // If we can include this digit in the
            // current number
            if (cur * 10
                    + Character.getNumericValue(s.charAt(i))
                <= k) {
 
                // Include this digit in
                // the current number.
                cur = cur * 10
                      + Character.getNumericValue(
                          s.charAt(i));
            }
            else {
 
                // If 'cur' is '0',
                // it's impossible to partition
                if (cur == 0) {
 
                    // Return the integer '-1'
                    return -1;
                }
                else {
 
                    // Increment the answer 'ans'
                    ans++;
 
                    // Set cur to the current digit
                    cur = Character.getNumericValue(
                        s.charAt(i));
                }
            }
        }
 
        // If cur > 0, means the last number is cur
        if (cur > 0) {
 
            // Increment the 'ans'
            ans++;
        }
 
        // Return the number of partitions
        return ans - 1;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Input
        String S = "7891634";
        int K = 21;
 
        // Function call
        System.out.print(minimumCommas(S, K));
    }
}
 
// This code is contributed by Taranpreet

Python3

# Python code for the above approach
 
# Function to count the minimum number
# of partitions
def minimumCommas(s, k) :
     
    # Length of the string 's'.
    n = len(s)
 
    # Store the current number formed.
    cur = 0
 
    # 'ans' stores the final answer.
    ans = 0
 
    # Iterate over the string.
    for i in range(n) :
 
        # If we can include this digit in the
        # current number
        if (cur * 10 + (ord(s[i]) - ord('0')) <= k) :
 
            # Include this digit in
            # the current number.
            cur = cur * 10 + (ord(s[i]) - ord('0'))
         
        else :
 
            # If 'cur' is '0',
            # it's impossible to partition
            if (cur == 0) :
 
                # Return the integer '-1'
                return -1
             
            else :
 
                # Increment the answer 'ans'
                ans += 1
 
                # Set cur to the current digit
                cur = (ord(s[i]) - ord('0'))
             
         
     
 
    # If cur > 0, means the last number is cur
    if (cur > 0) :
 
        # Increment the 'ans'
        ans += 1
     
 
    # Return the number of partitions
    return ans - 1
 
# Driver code
if __name__ == "__main__":
     
    # Input
    S = "7891634"
    K = 21
 
    # Function call
    print(minimumCommas(S, K))
     
    # This code is contributed by code_hunt.

C#

// C# program for above implementation
using System;
class GFG {
 
  // Function to count the minimum number
  // of partitions
  static int minimumCommas(string s, int k)
  {
 
    // Length of the string 's'.
    int n = s.Length;
 
    // Store the current number formed.
    long cur = 0;
 
    // 'ans' stores the final answer.
    int ans = 0;
 
    // Iterate over the string.
    for (int i = 0; i < n; ++i) {
      // If we can include this digit in the
      // current number
      if (cur * 10 + (s[i] - '0') <= k) {
 
        // Include this digit in
        // the current number.
        cur = cur * 10 + (s[i] - '0');
      }
      else {
 
        // If 'cur' is '0',
        // it's impossible to partition
        if (cur == 0) {
 
          // Return the integer '-1'
          return -1;
        }
        else {
 
          // Increment the answer 'ans'
          ans++;
 
          // Set cur to the current digit
          cur = s[i] - '0';
        }
      }
    }
 
    // If cur > 0, means the last number is cur
    if (cur > 0) {
 
      // Increment the 'ans'
      ans++;
    }
 
    // Return the number of partitions
    return ans - 1;
  }
 
  // Driver code
  public static void Main()
  {
    // Input
    string S = "7891634";
    int K = 21;
 
    // Function call
    Console.WriteLine(minimumCommas(S, K));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
 
// JavaScript program for above implementation
 
// Function to count the minimum number
// of partitions
function minimumCommas(s, k)
{
 
    // Length of the string 's'.
    let n = s.length;
 
    // Store the current number formed.
    let cur = 0;
 
    // 'ans' stores the final answer.
    let ans = 0;
 
    // Iterate over the string.
    for (let i = 0; i < n; ++i) {
 
        // If we can include this digit in the
        // current number
        if (cur * 10 + (s.charCodeAt(i) - '0'.charCodeAt(0)) <= k) {
 
            // Include this digit in
            // the current number.
            cur = cur * 10 + (s.charCodeAt(i) - '0'.charCodeAt(0));
        }
        else {
 
            // If 'cur' is '0',
            // it's impossible to partition
            if (cur == 0) {
 
                // Return the integer '-1'
                return -1;
            }
            else {
 
                // Increment the answer 'ans'
                ans++;
 
                // Set cur to the current digit
                cur = s.charCodeAt(i) - '0'.charCodeAt(0);
            }
        }
    }
 
    // If cur > 0, means the last number is cur
    if (cur > 0) {
 
        // Increment the 'ans'
        ans++;
    }
 
    // Return the number of partitions
    return ans - 1;
}
 
// Driver code
 
// Input
let S = "7891634";
let K = 21;
 
// Function call
document.write(minimumCommas(S, K));
 
// This code is contributed
// by shinjanpatra
 
</script>
Producción

5

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por rohit768 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *