Número más pequeño mayor o igual a N usando solo los dígitos 1 a K

Posted on by Rudeus Greyrat

Dado un número N y un entero K , la tarea es encontrar el número más pequeño mayor o igual a N , formado usando solo los primeros K dígitos distintos de cero (1, 2, …, K-1, K).
Ejemplos: 

Entrada: N = 124, K = 3 
Salida: 131 
Explicación: 
El número más pequeño mayor o igual a 124, que solo está formado por los dígitos 1, 2, 3 es 131.

Entrada: N = 325242, K = 4 
Salida: 331111 
 

Enfoque ingenuo: 
la solución más simple es comenzar un ciclo for desde N + 1 y encontrar el primer número formado por los primeros K dígitos.

Solución eficiente: 

  • Para obtener una solución eficiente, debemos comprender el hecho de que se pueden formar un máximo de números de 9 dígitos hasta 10 10 . Entonces, iteramos sobre los dígitos del número al revés y verificamos: 
    1. Si el dígito actual >= K entonces, haga que ese dígito sea = 1 .
    2. Si el dígito actual < K y no hay ningún dígito mayor que K después de este, incremente el dígito en 1 y copie todos los dígitos restantes tal como están.
  • Una vez que hemos iterado sobre todos los dígitos y aún no hemos encontrado ningún dígito que sea menor que K, debemos agregar un dígito (1) a la respuesta. 

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

C++

// C++ Program to find the smallest
// number greater than or equal
// to N which is made up of
// first K digits
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the
// digits greater than K
int CountGreater(int n, int k)
{
    int a = 0;
    while (n) {
        if ((n % 10) > k) {
            a++;
        }
        n = n / 10;
    }
    return a;
}
 
// Function to print the list
int PrintList(list<int> ans)
{
    for (auto it = ans.begin();
         it != ans.end(); it++)
        cout << *it;
}
 
// Function to find the number
// greater than or equal to n,
// which is only made of first
// k digits
void getNumber(int n, int k)
{
    int count = CountGreater(n, k);
 
    // If the number itself
    // satisfy the conditions
    if (count == 0) {
        cout << n;
        return;
    }
 
    list<int> ans;
    bool changed = false;
 
    // Check digit from back
    while (n > 0) {
        int digit = n % 10;
        if (changed == true) {
            ans.push_front(digit);
        }
        else {
            // If digit > K is
            // present previously and
            // current digit is less
            // than K
            if (count == 0 && digit < k) {
                ans.push_front(digit + 1);
                changed = true;
            }
            else {
                ans.push_front(1);
                // If current digit is
                // greater than K
                if (digit > k) {
                    count--;
                }
            }
        }
        n = n / 10;
    }
 
    // If an extra digit needs
    // to be added
    if (changed == false) {
        ans.push_front(1);
    }
 
    // Print the number
    PrintList(ans);
 
    return;
}
 
// Driver Code
int main()
{
    int N = 51234;
    int K = 4;
    getNumber(N, K);
    return 0;
}

Java

// Java program to find the smallest
// number greater than or equal
// to N which is made up of
// first K digits
import java.util.*;
 
class GFG{
 
// Function to count the
// digits greater than K
static int CountGreater(int n, int k)
{
    int a = 0;
     
    while (n > 0)
    {
        if ((n % 10) > k)
        {
            a++;
        }
        n = n / 10;
    }
    return a;
}
 
// Function to print the list
static void PrintList(List<Integer> ans)
{
    for(int it : ans)
        System.out.print(it);
}
 
// Function to find the number
// greater than or equal to n,
// which is only made of first
// k digits
static void getNumber(int n, int k)
{
    int count = CountGreater(n, k);
 
    // If the number itself
    // satisfy the conditions
    if (count == 0)
    {
        System.out.print(n);
        return;
    }
 
    List<Integer> ans = new LinkedList<>();
    boolean changed = false;
 
    // Check digit from back
    while (n > 0)
    {
        int digit = n % 10;
         
        if (changed == true)
        {
            ans.add(0, digit);
        }
        else
        {
             
            // If digit > K is
            // present previously and
            // current digit is less
            // than K
            if (count == 0 && digit < k)
            {
                ans.add(0, digit + 1);
                changed = true;
            }
            else
            {
                ans.add(0, 1);
                 
                // If current digit is
                // greater than K
                if (digit > k)
                {
                    count--;
                }
            }
        }
        n = n / 10;
    }
 
    // If an extra digit needs
    // to be added
    if (changed == false)
    {
        ans.add(0, 1);
    }
 
    // Print the number
    PrintList(ans);
 
    return;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 51234;
    int K = 4;
     
    getNumber(N, K);
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program to find the smallest
# number greater than or equal
# to N which is made up of
# first K digits
 
# Function to count the
# digits greater than K
def CountGreater(n, k):
 
    a = 0
    while (n > 0):
        if ((n % 10) > k):
            a += 1
             
        n = n // 10
 
    return a
 
# Function to print the list
def PrintList (ans):
 
    for i in ans:
        print(i, end = '')
 
# Function to find the number
# greater than or equal to n,
# which is only made of first
# k digits
def getNumber(n, k):
 
    count = CountGreater(n, k)
     
    # If the number itself
    # satisfy the conditions
    if (count == 0):
        print(n)
        return
 
    ans = []
    changed = False
 
    # Check digit from back
    while (n > 0):
        digit = n % 10
        if (changed == True):
            ans.insert(0, digit)
 
        else:
             
            # If digit > K is
            # present previously and
            # current digit is less
            # than K
            if (count == 0 and digit < k):
                ans.insert(0, digit + 1)
                changed = True
 
            else:
                ans.insert(0, 1)
                 
                # If current digit is
                # greater than K
                if (digit > k):
                    count -= 1
 
        n = n // 10
 
    # If an extra digit needs
    # to be added
    if (changed == False):
        ans.insert(0, 1)
 
    # Print the number
    PrintList(ans)
    return
 
# Driver Code
N = 51234
K = 4
 
getNumber(N, K)
 
# This code is contributed by himanshu77

C#

// C# program to find the smallest
// number greater than or equal
// to N which is made up of
// first K digits
using System;
using System.Collections.Generic;
class GFG{
 
// Function to count the
// digits greater than K
static int CountGreater(int n, int k)
{
  int a = 0;
 
  while (n > 0)
  {
    if ((n % 10) > k)
    {
      a++;
    }
    n = n / 10;
  }
  return a;
}
 
// Function to print the list
static void PrintList(List<int> ans)
{
  foreach(int it in ans)
    Console.Write(it);
}
 
// Function to find the number
// greater than or equal to n,
// which is only made of first
// k digits
static void getNumber(int n, int k)
{
  int count = CountGreater(n, k);
 
  // If the number itself
  // satisfy the conditions
  if (count == 0)
  {
    Console.Write(n);
    return;
  }
 
  List<int> ans = new List<int>();
  bool changed = false;
 
  // Check digit from back
  while (n > 0)
  {
    int digit = n % 10;
 
    if (changed == true)
    {
      ans.Insert(0, digit);
    }
    else
    {
      // If digit > K is
      // present previously and
      // current digit is less
      // than K
      if (count == 0 && digit < k)
      {
        ans.Insert(0, digit + 1);
        changed = true;
      }
      else
      {
        ans.Insert(0, 1);
 
        // If current digit is
        // greater than K
        if (digit > k)
        {
          count--;
        }
      }
    }
    n = n / 10;
  }
 
  // If an extra digit needs
  // to be added
  if (changed == false)
  {
    ans.Insert(0, 1);
  }
 
  // Print the number
  PrintList(ans);
 
  return;
}
 
// Driver Code
public static void Main(String[] args)
{
  int N = 51234;
  int K = 4;
  getNumber(N, K);
}
}
 
// This code is contributed by Princi Singh
Producción: 

111111

 

Publicación traducida automáticamente

Artículo escrito por SHIVAM BHALLA 1 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 *