Número más pequeño cuyo producto con N tiene suma de dígitos igual a la de N

Dado un número entero N , la tarea es encontrar el número entero positivo más pequeño, que cuando se multiplica por N , tenga una suma de dígitos igual a la suma de dígitos de N.

Ejemplos:

Entrada: N = 4
Salida: 28
Explicación: 

• Suma de dígitos de N = 4
• 4 * 28 = 112
• Suma de dígitos = 1 + 1 + 2 = 4, que es igual a la suma de dígitos de N.

Entrada: N = 3029
Salida: 37
Explicación: 

• Suma de dígitos de N = 3 + 0 + 2 + 9 = 14
• 3029 * 37 = 112073
• Suma de dígitos = 1 + 1 + 2 + 0 + 7 + 3 = 14, que es igual a la suma de dígitos de N.

Enfoque: Siga los pasos para resolver el problema:

1. Dado que N puede ser grande, tome la entrada de N como una string. Calcula la suma de los dígitos de N y guárdala en una variable, digamos S .
2. Dado que la respuesta debe exceder 10, a partir del número 11, multiplíquelo con N y guárdelo en una variable, digamos res .
3. Calcula la suma de dígitos de res y comprueba si la suma de dígitos de res es igual a la S o no. Si se encuentra que es cierto, imprima el número entero.

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

// C++ program for the above approach
#include <iostream>
using namespace std;
 
// Function to find the minimum
// integer having sum of digits
// of a number multiplied by n
// equal to sum of digits of n
void find_num(string n)
{
   
    // Initialize answer
    int ans = 0;
    int sumOfDigitsN = 0;
   
    // Find sum of digits of N
    for(int c = 0; c < n.length(); c++)
    {
        sumOfDigitsN += n - '0';
         
    }
    int x=11;
       
    while(true)
    {
        // Multiply N with x
        int newNum = x * stoi(n);
        int tempSumDigits = 0;
        string temp = to_string(newNum);
       
        // Sum of digits of the new number
        for(int c = 0; c < temp.length(); c++)
        {
            tempSumDigits += temp - '0';
        }
       
        // If condition satisfies
        if (tempSumDigits == sumOfDigitsN)
        {
            ans = x;
            break;
        }
        //increase x
          x++;
    }
   
    // Print answer
    cout << ans << endl;
}
 
// Driver Code
int main()
{
    string N = "3029";
   
    // Function call
    find_num(N);
    return 0;
}
 
// This code is contributed by Sunil Sakariya

// Java program for the above approach
 
class GFG {
 
    // Function to find the minimum
    // integer having sum of digits
    // of a number multiplied by n
    // equal to sum of digits of n
    static void find_num(String n)
    {
        // Initialize answer
        int ans = 0;
 
        // Convert string to
        // character array
        char[] digitsOfN
            = n.toCharArray();
 
        int sumOfDigitsN = 0;
 
        // Find sum of digits of N
        for (char c : digitsOfN) {
 
            sumOfDigitsN
                += Integer.parseInt(
                    Character.toString(c));
        }
 
        for (int x = 11; x > 0; x++) {
 
            // Multiply N with x
            int newNum
                = x * Integer.parseInt(n);
 
            int tempSumDigits = 0;
 
            char[] temp
                = Integer.toString(
                             newNum)
                      .toCharArray();
 
            // Sum of digits of the new number
            for (char c : temp) {
                tempSumDigits
                    += Integer.parseInt(
                        Character.toString(c));
            }
 
            // If condition satisfies
            if (tempSumDigits == sumOfDigitsN) {
                ans = x;
                break;
            }
        }
 
        // Print answer
        System.out.println(ans);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String N = "3029";
 
        // Function call
        find_num(N);
    }
}

# Python3 program for the above approach
 
# Function to find the minimum
# integer having sum of digits
# of a number multiplied by n
# equal to sum of digits of n
def find_num(n):
     
    # Initialize answer
    ans = 0
 
    # Convert string to
    # character array
    digitsOfN = str(n)
 
    sumOfDigitsN = 0
 
    # Find sum of digits of N
    for c in digitsOfN:
        sumOfDigitsN += int(c)
 
    for x in range(11, 50):
         
        # Multiply N with x
        newNum = x * int(n)
 
        tempSumDigits = 0
 
        temp = str(newNum)
 
        # Sum of digits of the new number
        for c in temp:
            tempSumDigits += int(c)
        #print(tempSumDigits,newNum)
 
        # If condition satisfies
        if (tempSumDigits == sumOfDigitsN):
            ans = x
            break
 
    # Print answer
    print(ans)
 
# Driver Code
if __name__ == '__main__':
     
    N = "3029"
 
    # Function call
    find_num(N)
 
# This code is contributed by mohit kumar 29

// C# program for the above approach 
using System;
using System.Globalization;
 
class GFG{
  
// Function to find the minimum
// integer having sum of digits
// of a number multiplied by n
// equal to sum of digits of n
static void find_num(string n)
{
     
    // Initialize answer
    int ans = 0;
 
    // Convert string to
    // character array
    char[] digitsOfN = n.ToCharArray();
 
    int sumOfDigitsN = 0;
 
    // Find sum of digits of N
    foreach(char c in digitsOfN)
    {
        sumOfDigitsN += Int32.Parse(
                Char.ToString(c));
    }
 
    for(int x = 11; x > 0; x++)
    {
         
        // Multiply N with x
        int newNum = x * Int32.Parse(n);
 
        int tempSumDigits = 0;
         
        string str = newNum.ToString();
        char[] temp = str.ToCharArray();
 
        // Sum of digits of the new number
        foreach(char c in temp)
        {
            tempSumDigits += Int32.Parse(
                    Char.ToString(c));
        }
 
        // If condition satisfies
        if (tempSumDigits == sumOfDigitsN)
        {
            ans = x;
            break;
        }
    }
 
    // Print answer
    Console.WriteLine(ans);
}
 
// Driver Code
public static void Main()
{
    string N = "3029";
     
    // Function call
    find_num(N);
}
}
 
// This code is contributed by susmitakundugoaldanga

<script>
 
// Javascript program for the above approach
 
// Function to find the minimum
// integer having sum of digits
// of a number multiplied by n
// equal to sum of digits of n
function find_num(n)
{
   
    // Initialize answer
    var ans = 0;
    var sumOfDigitsN = 0;
   
    // Find sum of digits of N
    for(var c = 0; c < n.length; c++)
    {
        sumOfDigitsN += n - '0';
         
    }
    var x=11;
       
    while(true)
    {
        // Multiply N with x
        var newNum = x * parseInt(n);
        var tempSumDigits = 0;
        var temp = (newNum.toString());
       
        // Sum of digits of the new number
        for(var c = 0; c < temp.length; c++)
        {
            tempSumDigits += temp - '0';
        }
       
        // If condition satisfies
        if (tempSumDigits == sumOfDigitsN)
        {
            ans = x;
            break;
        }
        //increase x
          x++;
    }
   
    // Print answer
    document.write( ans );
}
 
// Driver Code
var N = "3029";
 
// Function call
find_num(N);
 
</script>

37

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