Número mínimo con dígitos como 4 y 7 solamente y suma dada

Los números de la suerte son los enteros positivos cuyas representaciones decimales contienen solo los dígitos de la suerte 4 y 7. 
¿Qué número de la suerte mínimo tiene la suma de dígitos igual a n? 

Ejemplos: 

Input : sum = 11
Output : 47
Sum of digits in 47 is 11 and 47
is the smallest number with given sum.

Input :  sum = 10
Output : -1    

El enfoque se basa en los siguientes hechos:  

1. Dado que los dígitos son solo 4 y 7, la suma de dígitos dada se puede escribir como a*4 + b*7 = suma donde a y b son números enteros positivos (mayores o iguales a 0) que representan el número de 4 y 7 respectivamente.
2. Dado que necesitamos encontrar el número mínimo, el resultado siempre será de la forma que tiene primero todos los 4 y luego todos los 7, es decir, 44…477…7.

Básicamente necesitamos encontrar valores de ‘a’ y ‘b’. Encontramos estos valores usando los siguientes hechos:  

1. Si la suma es múltiplo de 4, entonces el resultado tiene todos los 4.
2. Si la suma es múltiplo de 7, entonces el resultado tiene todos los 7.
3. Si la suma no es múltiplo de 4 o 7, entonces podemos restar uno de ellos hasta que la suma se convierta en múltiplo de otro.

// C++ program to find smallest number
// with given sum of digits.
#include <bits/stdc++.h>
using namespace std;
 
// Prints minimum number with given digit
// sum and only allowed digits as 4 and 7.
void findMin(int sum)
{
    int a = 0, b = 0;
    while (sum > 0)
    {
        // Cases where all remaining digits
        // are 4 or 7 (Remaining sum of digits
        // should be multiple of 4 or 7)
        if (sum % 7 == 0)
        {
            b++;
            sum -= 7;
        }
        else if (sum % 4 == 0)
        {
            a++;
            sum -= 4;
        }
 
        // If both 4s and 7s are there
        // in digit sum, we subtract a 4.
        else
        {
            a++;
            sum -= 4;
        }
    }
 
    if (sum < 0)
    {
        printf("-1n");
        return;
    }
 
    for (int i=0; i<a; i++)
        printf("4");
 
    for (int i=0; i<b; i++)
        printf("7");
 
    printf("n");
}
 
// Driver code
int main()
{
    findMin(15);
    return 0;
}

// Java program to find smallest number
// with given sum of digits.
import java.io.*;
 
class GFG {
     
    // Prints minimum number with given digit
    // sum and only allowed digits as 4 and 7.
    static void findMin(int sum)
    {
        int a = 0, b = 0;
        while (sum > 0)
        {
            // Cases where all remaining digits
            // are 4 or 7 (Remaining sum of digits
            // should be multiple of 4 or 7)
            if (sum % 7 == 0)
            {
                b++;
                sum -= 7;
            }
            else if (sum % 4 == 0)
            {
                a++;
                sum -= 4;
            }
     
            // If both 4s and 7s are there
            // in digit sum, we subtract a 4.
            else
            {
                a++;
                sum -= 4;
            }
        }
     
        if (sum < 0)
        {
            System.out.print("-1n");
            return;
        }
     
        for (int i = 0; i < a; i++)
            System.out.print("4");
             
        for (int i = 0; i < b; i++)
            System.out.print("7");
             
        System.out.println();
    }
     
    // Driver code
    public static void main(String args[])
                            throws IOException
    {
        findMin(15);
    }
}
 
/* This code is contributed by Nikita tiwari.*/

# Python program to find smallest number
# with given sum of digits.
 
# Prints minimum number with given digit
# sum and only allowed digits as 4 and 7.
def findMin(s):
    a, b = 0, 0
    while (s > 0):
         
        # Cases where all remaining digits
        # are 4 or 7 (Remaining sum of digits
        # should be multiple of 4 or 7)
        if (s % 7 == 0):
            b += 1
            s -= 7
        else if (s % 4 == 0):
            a += 1
            s -= 4
 
        # If both 4s and 7s are there
        # in digit sum, we subtract a 4.
        else:
            a += 1
            s -= 4
 
    string = ""
    if (s < 0):
        string = "-1"
        return string
     
     
    string += "4" * a
    string += "7" * b
     
    return string
 
# Driver code
print(findMin(15))
 
# This code is contributed by Sachin Bisht

// C# program to find smallest number
// with given sum of digits.
using System;
 
class GFG {
     
    // Prints minimum number with given digit
    // sum and only allowed digits as 4 and 7.
    static void findMin(int sum)
    {
        int a = 0, b = 0;
        while (sum > 0)
        {
             
            // Cases where all remaining digits
            // are 4 or 7 (Remaining sum of digits
            // should be multiple of 4 or 7)
            if (sum % 7 == 0)
            {
                b++;
                sum -= 7;
            }
            else if (sum % 4 == 0)
            {
                a++;
                sum -= 4;
            }
     
            // If both 4s and 7s are there
            // in digit sum, we subtract a 4.
            else
            {
                a++;
                sum -= 4;
            }
        }
     
        if (sum < 0)
        {
            Console.Write("-1n");
            return;
        }
     
        for (int i = 0; i < a; i++)
            Console.Write("4");
             
        for (int i = 0; i < b; i++)
            Console.Write("7");
             
        Console.WriteLine();
    }
     
    // Driver code
    public static void Main()
    {
        findMin(15);
    }
}
 
// This code is contributed by Nitin Mittal.

<?php
// PHP program to find smallest number
// with given sum of digits.
 
// Prints minimum number with given digit
// sum and only allowed digits as 4 and 7.
function findMin($sum)
{
    $a = 0;
    $b = 0;
    while ($sum > 0)
    {
         
        // Cases where all remaining digits
        // are 4 or 7 (Remaining sum of digits
        // should be multiple of 4 or 7)
        if ($sum % 7 == 0)
        {
            $b++;
            $sum -= 7;
        }
        else if ($sum % 4 == 0)
        {
            $a++;
            $sum -= 4;
        }
 
        // If both 4s and 7s are there
        // in digit sum, we subtract a 4.
        else
        {
            $a++;
            $sum -= 4;
        }
    }
 
    if ($sum < 0)
    {
        echo("-1n");
        return;
    }
 
    for ($i = 0; $i < $a; $i++)
        echo("4");
 
    for ($i = 0; $i < $b; $i++)
        echo("7");
 
    echo("\n");
}
 
    // Driver code
    findMin(15);
     
// This code is contributed by nitin mittal
?>

<script>
 
// Javascript program to find smallest number
// with given sum of digits.
 
// Prints minimum number with given digit
// sum and only allowed digits as 4 and 7.
function findMin(sum)
{
    var a = 0, b = 0;
     
    while (sum > 0)
    {
         
        // Cases where all remaining digits
        // are 4 or 7 (Remaining sum of digits
        // should be multiple of 4 or 7)
        if (sum % 7 == 0)
        {
            b++;
            sum -= 7;
        }
        else if (sum % 4 == 0)
        {
            a++;
            sum -= 4;
        }
 
        // If both 4s and 7s are there
        // in digit sum, we subtract a 4.
        else
        {
            a++;
            sum -= 4;
        }
    }
 
    if (sum < 0)
    {
        document.write("-1n");
        return;
    }
 
    for(i = 0; i < a; i++)
        document.write("4");
 
    for(i = 0; i < b; i++)
        document.write("7");
 
    document.write();
}
 
// Driver code
findMin(15);
 
// This code is contributed by todaysgaurav
 
</script>

Producción: 

447

Complejidad temporal: O(suma).

Este artículo es una contribución de Amit . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.