Número mínimo de conjuntos con números menores que Y

Posted on by Rudeus Greyrat

Dada una string de dígitos consecutivos y un número Y, la tarea es encontrar el número de conjuntos mínimos tal que cada conjunto siga la siguiente regla: 

  1. El conjunto debe contener números consecutivos
  2. Ningún dígito puede usarse más de una vez.
  3. El número en el conjunto no debe ser mayor que Y.

Ejemplos:  

Input: s = "1234", Y = 30  
Output: 3
Three sets of {12, 3, 4}  

Input: s = "1234", Y = 4 
Output: 4
Four sets of {1}, {2}, {3}, {4}

Enfoque: el siguiente problema se puede resolver utilizando un enfoque codicioso cuyos pasos se detallan a continuación:  

  • Iterar en la string y concatenar el número a una variable (digamos num) usando num*10 + (s[i]-‘0’)
  • Si el número no es mayor que Y, entonces marque f = 1.
  • Si el número excede Y, entonces aumente la cuenta si f = 1 y reinicie f como 0 y también inicialice num como s[i]-‘0’ o num como 0.
  • Después de iterar completamente en la string, aumente el conteo si f es 1.

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

C++

// C++ program to find the minimum number
// sets with consecutive numbers and less than Y
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum number of shets
int minimumSets(string s, int y)
{
 
    // Variable to count
    // the number of sets
    int cnt = 0;
    int num = 0;
 
    int l = s.length();
    int f = 0;
 
    // Iterate in the string
    for (int i = 0; i < l; i++) {
 
        // Add the number to string
        num = num * 10 + (s[i] - '0');
 
        // Mark that we got a number
        if (num <= y)
            f = 1;
        else // Every time it exceeds
        {
 
            // Check if previous was
            // anytime  less than Y
            if (f)
                cnt += 1;
 
            // Current number
            num = s[i] - '0';
            f = 0;
 
            // Check for current number
            if (num <= y)
                f = 1;
            else
                num = 0;
        }
    }
 
    // Check for last added number
    if (f)
        cnt += 1;
 
    return cnt;
}
 
// Driver Code
int main()
{
    string s = "1234";
    int y = 30;
    cout << minimumSets(s, y);
 
 return 0;
}

Java

// Java program to find the minimum number
// sets with consecutive numbers and less than Y
import java.util.*;
 
class solution
{
 
// Function to find the minimum number of shets
static int minimumSets(String s, int y)
{
 
    // Variable to count
    // the number of sets
    int cnt = 0;
    int num = 0;
 
    int l = s.length();
    boolean f = false;
 
    // Iterate in the string
    for (int i = 0; i < l; i++) {
 
        // Add the number to string
        num = num * 10 + (s.charAt(i) - '0');
 
        // Mark that we got a number
        if (num <= y)
            f = true;
        else // Every time it exceeds
        {
 
            // Check if previous was
            // anytime less than Y
            if (f)
                cnt += 1;
 
            // Current number
            num = s.charAt(i) - '0';
            f = false;
 
            // Check for current number
            if (num <= y)
                f = true;
            else
                num = 0;
        }
    }
 
    // Check for last added number
    if (f == true)
        cnt += 1;
 
    return cnt;
}
 
// Driver Code
public static void main(String args[])
{
    String s = "1234";
    int y = 30;
    System.out.println(minimumSets(s, y));
}
}
// This code is contributed by
// Shashank_Sharma

Python3

# Python3 program to find the minimum number
# sets with consecutive numbers and less than Y
import math as mt
 
# Function to find the minimum number of shets
def minimumSets(s, y):
     
    # Variable to count the number of sets
    cnt = 0
    num = 0
 
    l = len(s)
    f = 0
 
    # Iterate in the string
    for i in range(l):
         
        # Add the number to string
        num = num * 10 + (ord(s[i]) - ord('0'))
 
        # Mark that we got a number
        if (num <= y):
            f = 1
        else: # Every time it exceeds
 
            # Check if previous was anytime
            # less than Y
            if (f):
                cnt += 1
 
            # Current number
            num = ord(s[i]) - ord('0')
            f = 0
 
            # Check for current number
            if (num <= y):
                f = 1
            else:
                num = 0
         
    # Check for last added number
    if (f):
        cnt += 1
 
    return cnt
 
# Driver Code
s = "1234"
y = 30
print(minimumSets(s, y))
 
# This code is contributed by
# Mohit kumar 29

C#

// C# program to find the minimum number
// sets with consecutive numbers and less than Y
 
using System;
 
class solution
{
 
// Function to find the minimum number of shets
static int minimumSets(string s, int y)
{
 
    // Variable to count
    // the number of sets
    int cnt = 0;
    int num = 0;
 
    int l = s.Length ;
    bool f = false;
 
    // Iterate in the string
    for (int i = 0; i < l; i++) {
 
        // Add the number to string
        num = num * 10 + (s[i] - '0');
 
        // Mark that we got a number
        if (num <= y)
            f = true;
        else // Every time it exceeds
        {
 
            // Check if previous was
            // anytime less than Y
            if (f)
                cnt += 1;
 
            // Current number
            num = s[i] - '0';
            f = false;
 
            // Check for current number
            if (num <= y)
                f = true;
            else
                num = 0;
        }
    }
 
    // Check for last added number
    if (f == true)
        cnt += 1;
 
    return cnt;
}
 
// Driver Code
public static void Main()
{
    string s = "1234";
    int y = 30;
     
    Console.WriteLine(minimumSets(s, y));
}
// This code is contributed by Ryuga
 
}

PHP

<?php
// PHP program to find the minimum number
// sets with consecutive numbers and less than Y
 
// Function to find the minimum number of shets
function minimumSets($s, $y)
{
 
    // Variable to count
    // the number of sets
    $cnt = 0;
    $num = 0;
 
    $l = strlen($s);
    $f = 0;
 
    // Iterate in the string
    for ($i = 0; $i < $l; $i++)
    {
 
        // Add the number to string
        $num = $num * 10 + ($s[$i] - '0');
 
        // Mark that we got a number
        if ($num <= $y)
            $f = 1;
        else // Every time it exceeds
        {
 
            // Check if previous was
            // anytime less than Y
            if ($f)
                $cnt += 1;
 
            // Current number
            $num = $s[$i] - '0';
            $f = 0;
 
            // Check for current number
            if ($num <= $y)
                $f = 1;
            else
                $num = 0;
        }
    }
 
    // Check for last added number
    if ($f)
        $cnt += 1;
 
    return $cnt;
}
 
// Driver Code
$s = "1234";
$y = 30;
echo(minimumSets($s, $y));
 
//This code is contributed by Shivi_Aggarwal
?>

Javascript

<script>
 
// Javascript program to find the minimum number
// sets with consecutive numbers and less than Y
 
// Function to find the minimum number of shets
function minimumSets(s, y)
{
 
    // Variable to count
    // the number of sets
    let cnt = 0;
    let num = 0;
 
    let l = s.length;
    let f = false;
 
    // Iterate in the string
    for (let i = 0; i < l; i++) {
 
        // Add the number to string
        num = num * 10 + (s[i] - '0');
 
        // Mark that we got a number
        if (num <= y)
            f = true;
        else // Every time it exceeds
        {
 
            // Check if previous was
            // anytime less than Y
            if (f)
                cnt += 1;
 
            // Current number
            num = s[i] - '0';
            f = false;
 
            // Check for current number
            if (num <= y)
                f = true;
            else
                num = 0;
        }
    }
 
    // Check for last added number
    if (f == true)
        cnt += 1;
 
    return cnt;
}
 
// Driver code
 
    let s = "1234";
    let y = 30;
     document.write(minimumSets(s, y));
     
</script>
Producción: 

3

 

Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces. Donde N es la longitud de la string.

Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.

Publicación traducida automáticamente

Artículo escrito por Striver 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 *