Número más pequeño mayor que Y con suma de dígitos igual a X

Dados dos enteros X e Y , encuentre el número mínimo con la suma de los dígitos X, que es estrictamente mayor que Y.

Ejemplos: 

Entrada: X = 18, Y = 99 
Salida: 189 
Explicación: 
189 es el número más pequeño mayor que 99 que tiene una suma de dígitos = 18.

Entrada: X = 12, Y = 72 
Salida: 75 
Explicación: 
75 es el número más pequeño mayor que 72 que tiene suma de dígitos = 12. 

Enfoque ingenuo: el enfoque ingenuo es iterar desde Y + 1 y verificar si hay algún número cuya suma de dígitos sea X o no. Si encontramos algún número así, imprima ese número.

Complejidad de tiempo: O((R – Y)*log 10 N), donde R es el número máximo hasta donde iteramos y N es el número en el rango [Y, R]  
Espacio auxiliar: O(1)

Enfoque eficiente: la idea es iterar a través de los dígitos de Y de derecha a izquierda e intentar aumentar el dígito actual y cambiar los dígitos a la derecha para que la suma de los dígitos sea igual a X. A continuación se muestran los pasos: 

  • Si estamos considerando el (k + 1) dígito de la derecha y lo estamos aumentando, entonces es posible hacer que la suma de k dígitos menos significativos sea cualquier número en el rango [0, 9k] .
  • Cuando se encuentre tal posición, detenga el proceso e imprima el número en esa iteración.
  • Si k dígitos menos significativos tienen suma M (donde 0 ≤ M ≤ 9k), entonces obtenga la respuesta con avidez
    • Recorra de derecha a izquierda e inserte 9 y reste 9 de la suma de dígitos.
    • Una vez que la suma sea menor que 9, coloque la suma restante.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum string
// of length d having the sum of digits s
string helper(int d, int s)
{
 
    // Return a string of length d
    string ans(d, '0');
 
    for (int i = d - 1; i >= 0; i--) {
 
        // Greedily put 9's in the end
        if (s >= 9) {
            ans[i] = '9';
            s -= 9;
        }
 
        // Put remaining sum
        else {
            char c = (char)s + '0';
            ans[i] = c;
            s = 0;
        }
    }
 
    return ans;
}
 
// Function to find the smallest
// number greater than Y
// whose sum of digits is X
string findMin(int x, int Y)
{
 
    // Convert number y to string
    string y = to_string(Y);
 
    int n = y.size();
    vector<int> p(n);
 
    // Maintain prefix sum of digits
    for (int i = 0; i < n; i++) {
        p[i] = y[i] - '0';
        if (i > 0)
            p[i] += p[i - 1];
    }
 
    // Iterate over Y from the back where
    // k is current length of suffix
    for (int i = n - 1, k = 0;; i--, k++) {
 
        // Stores current digit
        int d = 0;
 
        if (i >= 0)
            d = y[i] - '0';
 
        // Increase current digit
        for (int j = d + 1; j <= 9; j++) {
 
            // Sum upto current prefix
            int r = (i > 0) * p[i - 1] + j;
 
            // Return answer if remaining
            // sum can be obtained in suffix
            if (x - r >= 0 and x - r <= 9 * k) {
 
                // Find suffix of length k
                // having sum of digits x-r
                string suf = helper(k, x - r);
 
                string pre = "";
                if (i > 0)
                    pre = y.substr(0, i);
 
                // Append current character
                char cur = (char)j + '0';
                pre += cur;
 
                // Return the result
                return pre + suf;
            }
        }
    }
}
 
// Driver Code
int main()
{
    // Given Number and Sum
    int x = 18;
    int y = 99;
 
    // Function Call
    cout << findMin(x, y) << endl;
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
@SuppressWarnings("unchecked")
class GFG{
  
// Function to return the minimum String
// of length d having the sum of digits s
static String helper(int d, int s)
{
     
    // Return a String of length d
    StringBuilder ans = new StringBuilder();
      
    for(int i = 0; i < d; i++)
    {
        ans.append("0");
    }
      
    for(int i = d - 1; i >= 0; i--)
    {
         
        // Greedily put 9's in the end
        if (s >= 9)
        {
            ans.setCharAt(i,'9');
            s -= 9;
        }
          
        // Put remaining sum
        else
        {
            char c = (char)(s + (int)'0');
            ans.setCharAt(i,  c);
            s = 0;
        }
    }
    return ans.toString();
}
  
// Function to find the smallest
// number greater than Y
// whose sum of digits is X
static String findMin(int x, int Y)
{
     
    // Convert number y to String
    String y = Integer.toString(Y);
      
    int n = y.length();
      
    ArrayList p = new ArrayList();
      
    for(int i = 0; i < n; i++)
    {
        p.add(0);
    }
      
    // Maintain prefix sum of digits
    for(int i = 0; i < n; i++)
    {
        p.add(i, (int)((int) y.charAt(i) - (int)'0'));
          
        if (i > 0)
        {
            p.add(i, (int)p.get(i) +
                     (int)p.get(i - 1));
        }
    }
      
    // Iterate over Y from the back where
    // k is current length of suffix
    for(int i = n - 1, k = 0;; i--, k++)
    {
          
        // Stores current digit
        int d = 0;
          
        if (i >= 0)
        {
            d = (int) y.charAt(i) - (int)'0';
        }
          
        // Increase current digit
        for(int j = d + 1; j <= 9; j++)
        {
            int r = j;
              
            // Sum upto current prefix
            if (i > 0)
            {
                r += (int) p.get(i - 1);
            }
              
            // Return answer if remaining
            // sum can be obtained in suffix
            if (x - r >= 0 && x - r <= 9 * k)
            {
                  
                // Find suffix of length k
                // having sum of digits x-r
                String suf = helper(k, x - r);
                  
                String pre = "";
                  
                if (i > 0)
                    pre = y.substring(0, i);
                  
                // Append current character
                char cur = (char)(j + (int)'0');
                pre += cur;
                  
                // Return the result
                return pre + suf;
            }
        }
    }
}
  
// Driver code
public static void main(String[] arg)
{
     
    // Given number and sum
    int x = 18;
    int y = 99;
      
    // Function call
    System.out.print(findMin(x, y));
}
}
 
// This code is contributed by pratham76

Python3

# Python3 program for the
# above approach
 
# Function to return the
# minimum string of length
# d having the sum of digits s
def helper(d, s):
 
    # Return a string of
    # length d
    ans = ['0'] * d
 
    for i in range(d - 1,
                   -1, -1):
 
        # Greedily put 9's
        # in the end
        if (s >= 9):
            ans[i] = '9'
            s -= 9
 
        # Put remaining sum
        else:
            c = chr(s +
                    ord('0'))
            ans[i] = c;
            s = 0;
 
    return ''.join(ans);
 
# Function to find the
# smallest number greater
# than Y whose sum of
# digits is X
def findMin(x, Y):
 
    # Convert number y
    # to string
    y = str(Y);
    n = len(y)
    p = [0] * n
 
    # Maintain prefix sum
    # of digits
    for i in range(n):
        p[i] = (ord(y[i]) -
                ord('0'))
        if (i > 0):
            p[i] += p[i - 1];
 
    # Iterate over Y from the
    # back where k is current
    # length of suffix
    n - 1
    k = 0
     
    while True:
 
        # Stores current digit
        d = 0;
        if (i >= 0):
            d = (ord(y[i]) -
                 ord('0'))
 
        # Increase current
        # digit
        for j in range(d + 1,
                       10):
 
            # Sum upto current
            # prefix
            r = ((i > 0) *
                 p[i - 1] + j);
 
            # Return answer if
            # remaining sum can
            # be obtained in suffix
            if (x - r >= 0 and
                x - r <= 9 * k):
 
                # Find suffix of length
                # k having sum of digits
                # x-r
                suf = helper(k,
                             x - r);
 
                pre = "";
                if (i > 0):
                    pre = y[0 : i]
 
                # Append current
                # character
                cur = chr(j +
                          ord('0'))
                pre += cur;
 
                # Return the result
                return pre + suf;
 
        i -= 1
        k += 1     
 
# Driver Code
if __name__ == "__main__":
               
   # Given Number and Sum
    x = 18;
    y = 99;
 
    # Function Call
    print ( findMin(x, y))
 
# This code is contributed by Chitranayal

C#

// C# program for the above approach
using System;
using System.Text;
using System.Collections;
 
class GFG{
 
// Function to return the minimum string
// of length d having the sum of digits s
static string helper(int d, int s)
{
 
    // Return a string of length d
    StringBuilder ans = new StringBuilder();
     
    for(int i = 0; i < d; i++)
    {
        ans.Append("0");
    }
     
    for(int i = d - 1; i >= 0; i--)
    {
         
        // Greedily put 9's in the end
        if (s >= 9)
        {
            ans[i] = '9';
            s -= 9;
        }
         
        // Put remaining sum
        else
        {
            char c = (char)(s + (int)'0');
            ans[i] = c;
            s = 0;
        }
    }
    return ans.ToString();
}
 
// Function to find the smallest
// number greater than Y
// whose sum of digits is X
static string findMin(int x, int Y)
{
     
    // Convert number y to string
    string y = Y.ToString();
     
    int n = y.Length;
     
    ArrayList p = new ArrayList();
     
    for(int i = 0; i < n; i++)
    {
        p.Add(0);
    }
     
    // Maintain prefix sum of digits
    for(int i = 0; i < n; i++)
    {
        p[i] = (int)((int) y[i] - (int)'0');
         
        if (i > 0)
        {
            p[i] = (int)p[i] +
                   (int)p[i - 1];
        }
    }
     
    // Iterate over Y from the back where
    // k is current length of suffix
    for(int i = n - 1, k = 0;; i--, k++)
    {
         
        // Stores current digit
        int d = 0;
         
        if (i >= 0)
        {
            d = (int) y[i] - (int)'0';
        }
         
        // Increase current digit
        for(int j = d + 1; j <= 9; j++)
        {
            int r = j;
             
            // Sum upto current prefix
            if (i > 0)
            {
                r += (int) p[i - 1];
            }
             
            // Return answer if remaining
            // sum can be obtained in suffix
            if (x - r >= 0 && x - r <= 9 * k)
            {
                 
                // Find suffix of length k
                // having sum of digits x-r
                string suf = helper(k, x - r);
                 
                string pre = "";
                 
                if (i > 0)
                    pre = y.Substring(0, i);
                 
                // Append current character
                char cur = (char)(j + (int)'0');
                pre += cur;
                 
                // Return the result
                return pre + suf;
            }
        }
    }
}
 
// Driver code
public static void Main(string[] arg)
{
     
    // Given number and sum
    int x = 18;
    int y = 99;
     
    // Function call
    Console.Write(findMin(x, y));
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to return the minimum String
// of length d having the sum of digits s
function helper(d, s)
{
     
    // Return a String of length d
    let ans = [];
       
    for(let i = 0; i < d; i++)
    {
        ans.push("0");
    }
       
    for(let i = d - 1; i >= 0; i--)
    {
         
        // Greedily put 9's in the end
        if (s >= 9)
        {
            ans[i] ='9';
            s -= 9;
        }
           
        // Put remaining sum
        else
        {
            let c = String.fromCharCode(
                s + '0'.charCodeAt(0));
            ans[i] = c;
            s = 0;
        }
    }
    return ans.join("");
}
 
// Function to find the smallest
// number greater than Y
// whose sum of digits is X
function findMin(x, Y)
{
     
    // Convert number y to String
    let y = Y.toString();
    let n = y.length;
    let p = [];
       
    for(let i = 0; i < n; i++)
    {
        p.push(0);
    }
       
    // Maintain prefix sum of digits
    for(let i = 0; i < n; i++)
    {
        p[i] = y[i].charCodeAt(0) -
                '0'.charCodeAt(0);
           
        if (i > 0)
        {
            p[i] = p[i] + p[i - 1];
        }
    }
       
    // Iterate over Y from the back where
    // k is current length of suffix
    for(let i = n - 1, k = 0;; i--, k++)
    {
         
        // Stores current digit
        let d = 0;
           
        if (i >= 0)
        {
            d =  y[i].charCodeAt(0) -
                  '0'.charCodeAt(0);
        }
           
        // Increase current digit
        for(let j = d + 1; j <= 9; j++)
        {
            let r = j;
               
            // Sum upto current prefix
            if (i > 0)
            {
                r +=  p[i - 1];
            }
               
            // Return answer if remaining
            // sum can be obtained in suffix
            if (x - r >= 0 && x - r <= 9 * k)
            {
                   
                // Find suffix of length k
                // having sum of digits x-r
                let suf = helper(k, x - r);
                let pre = "";
                   
                if (i > 0)
                    pre = y.substring(0, i);
                   
                // Append current character
                let cur = String.fromCharCode(
                    j + '0'.charCodeAt(0));
                pre += cur;
                   
                // Return the result
                return pre + suf;
            }
        }
    }
}
 
// Driver code
 
// Given number and sum
let x = 18;
let y = 99;
 
// Function call
document.write(findMin(x, y));
   
// This code is contributed by avanitrachhadiya2155
 
</script>
Producción: 

189

 

Complejidad de tiempo: O(log 10 Y) 
Espacio auxiliar: O(log 10 Y)
 

Publicación traducida automáticamente

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