Número siguiente mayor que N con la misma cantidad de dígitos A y B

Posted on by Rudeus Greyrat

Dado un número  norte y dos dígitos  A y  B . La tarea es encontrar el menor número no menor que N que contenga el mismo número de dígitos A y B.
Nota : N <= 10 7
Ejemplos: 
 

Entrada : N = 4500, A = 4, B = 7 
Salida : 4747 
El número mayor que 4500 que tiene la misma cantidad de número ‘4’ y número ‘7’ es 4747.
Entrada : N = 99999999, A = 6, B = 7 
Salida : 6666677777 
 

A continuación se muestra el algoritmo paso a paso para resolver este problema: 
 

  1. Si la longitud de ‘N’ es impar, el número resultante será de longitud ‘N+1’ ya que tanto ‘a’ como ‘b’ tienen que estar en la misma cantidad.
  2. Si la longitud de ‘N’ es par, el número resultante será de longitud ‘N’ o ‘N+2’.
  3. Generaremos el número recursivamente agregando A y B uno por uno y tomaremos el mínimo de los dos para la siguiente llamada recursiva.
  4. Por último, devuelva el número más pequeño mayor o igual a ‘N’.

A continuación se muestra la implementación de la idea anterior: 
 

C++

// C++ program to find next greater Number
// than N with the same quantity of
// digits A and B
 
#include <bits/stdc++.h>
using namespace std;
 
// Recursive function to find the required number
long findNumUtil(long res, int a, int aCount, int b, int bCount, int n)
{
    if (res > 1e11)
        return 1e11;
 
    // If the resulting number is >= n and
    // count of a = count of b, return the number
    if (aCount == bCount && res >= n)
        return res;
 
    // select minimum of two and call the function again
    return min(findNumUtil(res * 10 + a, a, aCount + 1, b, bCount, n),
               findNumUtil(res * 10 + b, a, aCount, b, bCount + 1, n));
}
 
// Function to find the number next greater Number
// than N with the same quantity of
// digits A and B
int findNum(int n, int a, int b)
{
    int result = 0;
    int aCount = 0;
    int bCount = 0;
 
    return findNumUtil(result, a, aCount, b, bCount, n);
}
 
// Driver code
int main()
{
    int N = 4500;
    int A = 4;
    int B = 7;
 
    cout << findNum(N, A, B);
 
    return 0;
}

Java

// Java program to find next greater Number
// than N with the same quantity of
// digits A and B
 
public class GFG {
     
    // Recursive function to find the required number
    static long findNumUtil(long res, int a, int aCount, int b, int bCount, int n)
    {
        if (res > 1e11)
            return (long) 1e11;
 
        // If the resulting number is >= n and
        // count of a = count of b, return the number
        if (aCount == bCount && res >= n)
            return res;
 
        // select minimum of two and call the function again
        return Math.min(findNumUtil(res * 10 + a, a, aCount + 1, b, bCount, n),
                   findNumUtil(res * 10 + b, a, aCount, b, bCount + 1, n));
    }
 
    // Function to find the number next greater Number
    // than N with the same quantity of
    // digits A and B
    static int findNum(int n, int a, int b)
    {
        int result = 0;
        int aCount = 0;
        int bCount = 0;
 
        return (int) findNumUtil(result, a, aCount, b, bCount, n);
    }
 
     
    // Driver code
    public static void main(String args[])
    {
           int N = 4500;
            int A = 4;
            int B = 7;
 
            System.out.println(findNum(N, A, B));
 
 
    }
    // This Code is contributed by ANKITRAI1
}

Python3

# Python 3 program to find next greater
# Number than N with the same quantity of
# digits A and B
 
# Recursive function to find the
# required number
def findNumUtil(res, a, aCount, b, bCount, n):
    if (res > 1e11):
        return 1e11
 
    # If the resulting number is >= n
    # and count of a = count of b,
    # return the number
    if (aCount == bCount and res >= n):
        return res
 
    # select minimum of two and call
    # the function again
    return min(findNumUtil(res * 10 + a,
                           a, aCount + 1, b, bCount, n),
               findNumUtil(res * 10 + b, a,
                           aCount, b, bCount + 1, n))
 
 
# Function to find the number next
# greater Number than N with the
# same quantity of digits A and B
def findNum(n, a, b):
    result = 0
    aCount = 0
    bCount = 0
 
    return findNumUtil(result, a, aCount,
                               b, bCount, n)
 
# Driver code
if __name__ == '__main__':
    N = 4500
    A = 4
    B = 7
 
    print(findNum(N, A, B))
 
# This code is contributed by
# Sanjit_Prasad

C#

// C# program to find next greater Number
// than N with the same quantity of
// digits A and B
using System;
 
class GFG
{
 
// Recursive function to find the required number
static long findNumUtil(long res, int a, int aCount,
                        int b, int bCount, int n)
{
    if (res > 1e11)
        return (long) 1e11;
 
    // If the resulting number is >= n and
    // count of a = count of b, return the number
    if (aCount == bCount && res >= n)
        return res;
 
    // select minimum of two and call
    // the function again
    return Math.Min(findNumUtil(res * 10 + a, a,
                                aCount + 1, b, bCount, n),
            findNumUtil(res * 10 + b, a, aCount,
                             b, bCount + 1, n));
}
 
// Function to find the number next
// greater Number than N with the
// same quantity of digits A and B
static int findNum(int n, int a, int b)
{
    int result = 0;
    int aCount = 0;
    int bCount = 0;
 
    return (int) findNumUtil(result, a, aCount,
                                     b, bCount, n);
}
 
// Driver code
public static void Main()
{
    int N = 4500;
    int A = 4;
    int B = 7;
 
    Console.WriteLine(findNum(N, A, B));
}
}
 
// This code is contributed by Shashank

PHP

<?php
// PHP program to find next greater Number
// than N with the same quantity of
// digits A and B
 
 
// Recursive function to find the required number
function findNumUtil($res, $a, $aCount, $b, $bCount, $n)
{
    if ($res > 100000000000)
        return 10000000000;
 
    // If the resulting number is >= n and
    // count of a = count of b, return the number
    if ($aCount == $bCount && $res >= $n)
        return $res;
 
    // select minimum of two and call the function again
    return min(findNumUtil($res * 10 + $a, $a, $aCount + 1, $b, $bCount, $n),
            findNumUtil($res * 10 + $b, $a, $aCount, $b, $bCount + 1, $n));
}
 
// Function to find the number next greater Number
// than N with the same quantity of
// digits A and B
function findNum($n, $a, $b)
{
    $result = 0;
    $aCount = 0;
    $bCount = 0;
 
    return findNumUtil($result, $a, $aCount, $b, $bCount, $n);
}
 
// Driver code
 
    $N = 4500;
    $A = 4;
    $B = 7;
 
    echo findNum($N, $A, $B);
 
// This Code is contributed by mits
?>

Javascript

<script>
    // Javascript program to find next greater Number
    // than N with the same quantity of
    // digits A and B
     
    // Recursive function to find the required number
    function findNumUtil(res, a, aCount, b, bCount, n)
    {
        if (res > 1e11)
            return 1e11;
 
        // If the resulting number is >= n and
        // count of a = count of b, return the number
        if (aCount == bCount && res >= n)
            return res;
 
        // select minimum of two and call
        // the function again
        return Math.min(findNumUtil(res * 10 + a, a,
                                    aCount + 1, b, bCount, n),
                findNumUtil(res * 10 + b, a, aCount,
                                 b, bCount + 1, n));
    }
 
    // Function to find the number next
    // greater Number than N with the
    // same quantity of digits A and B
    function findNum(n, a, b)
    {
        let result = 0;
        let aCount = 0;
        let bCount = 0;
 
        return findNumUtil(result, a, aCount,
                                         b, bCount, n);
    }
     
    let N = 4500;
    let A = 4;
    let B = 7;
   
    document.write(findNum(N, A, B));
     
    // This code is contributed by divyesh072019.
</script>
Producción: 

4747

 

Complejidad temporal: O(2 n )
Espacio auxiliar: O(1)

Publicación traducida automáticamente

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