Encuentra el número más pequeño con los dígitos dados y la suma de los dígitos

Posted on by Rudeus Greyrat

Dados dos números enteros positivos P y Q , encuentre el número entero mínimo que contenga solo los dígitos P y Q tal que la suma de los dígitos del número entero sea N .

Ejemplo:

Entrada: N = 11, P = 4, Q = 7 
Salida: 47
Explicación: Hay dos números enteros posibles que se pueden formar a partir de 4 y 7 de modo que su suma sea 11, es decir, 47 y 74. Ya que necesitamos encontrar el mínimo posible valor, 47 es la respuesta requerida.

Entrada: N = 11, P = 9, Q = 7
Salida: No posible 
Explicación: No es posible crear un número entero usando los dígitos 7 y 9 tal que su suma sea 11.   

 

Enfoque eficiente: Consideremos que P es mayor o igual que Q , count_P denota el número de ocurrencias de P y count_Q denota el número de ocurrencias de Q en el entero resultante. Entonces, la pregunta se puede representar en forma de una ecuación ( P * count_P) + (Q * count_Q) = N , y para minimizar el conteo de dígitos en el número entero resultante  , count_P + count_Q debe ser lo más mínimo posible. Se puede observar que dado que P >= Q , el valor máximo posible de count_Pque satisfaga ( P * count_P) + (Q * count_Q) = N será la opción más óptima. A continuación se muestran los pasos para el enfoque anterior:

  1. Inicialice count_P y count_Q como 0.
  2. Si N es divisible por P , count_P = N/P y N=0 .
  3. Si N no es divisible por P , reste Q de N e incremente count_Q en 1.
  4. Repita los pasos 2 y 3 hasta que N sea mayor que 0.
  5. Si N != 0 , no es posible generar el entero que satisfaga las condiciones requeridas. De lo contrario, el entero resultante será count_Q multiplicado por Q seguido de count_P multiplicado por P.

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

C++

// C++ Program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the minimum
// integer having only digits P and
// Q and the sum of digits as N
void printMinInteger(int P, int Q, int N)
{
    // If Q is greater that P then
    // swap the values of P and Q
    if (Q > P) {
        swap(P, Q);
    }
 
    // If P and Q are both zero or
    // if Q is zero and N is not
    // divisible by P then there
    // is no possible integer which
    // satisfies the given conditions
    if (Q == 0 && (P == 0 || N % P != 0)) {
        cout << "Not Possible";
        return;
    }
 
    int count_P = 0, count_Q = 0;
 
    // Loop to find the maximum value
    // of count_P that also satisfy
    // P*count_P + Q*count_Q = N
    while (N > 0) {
        if (N % P == 0) {
            count_P += N / P;
            N = 0;
        }
        else {
            N = N - Q;
            count_Q++;
        }
    }
 
    // If N is 0, their is a valid
    // integer possible that satisfies
    // all the requires conditions
    if (N == 0) {
 
        // Print Answer
        for (int i = 0; i < count_Q; i++)
            cout << Q;
        for (int i = 0; i < count_P; i++)
            cout << P;
    }
    else {
        cout << "Not Possible";
    }
}
 
// Driver Code
int main()
{
    int N = 32;
    int P = 7;
    int Q = 4;
 
    // Function Call
    printMinInteger(P, Q, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
 
class GFG {
 
// Function to print the minimum
// integer having only digits P and
// Q and the sum of digits as N
static void printMinInteger(int P, int Q, int N)
{
   
    // If Q is greater that P then
    // swap the values of P and Q
    if (Q > P) {
        int temp;
        temp = P;
        P = Q;
        Q = temp;
    }
 
    // If P and Q are both zero or
    // if Q is zero and N is not
    // divisible by P then there
    // is no possible integer which
    // satisfies the given conditions
    if (Q == 0 && (P == 0 || N % P != 0)) {
        System.out.println("Not Possible");
        return;
    }
 
    int count_P = 0, count_Q = 0;
 
    // Loop to find the maximum value
    // of count_P that also satisfy
    // P*count_P + Q*count_Q = N
    while (N > 0) {
        if (N % P == 0) {
            count_P += N / P;
            N = 0;
        }
        else {
            N = N - Q;
            count_Q++;
        }
    }
 
    // If N is 0, their is a valid
    // integer possible that satisfies
    // all the requires conditions
    if (N == 0) {
 
        // Print Answer
        for (int i = 0; i < count_Q; i++)
            System.out.print(Q);
        for (int i = 0; i < count_P; i++)
            System.out.print(P);
    }
    else {
        System.out.println("Not Possible");
    }
}
 
// Driver code
public static void main(String[] args)
{
    int N = 32;
    int P = 7;
    int Q = 4;
 
    // Function Call
    printMinInteger(P, Q, N);
}
}
 
// This code is contributed by code_hunt.

Python3

# Python3 program for the above approach
 
# Function to print minimum
# integer having only digits P and
# Q and the sum of digits as N
def printMinInteger(P, Q, N):
     
    # If Q is greater that P then
    # swap the values of P and Q
    if (Q > P):
        t = P
        P = Q
        Q = t
 
    # If P and Q are both zero or
    # if Q is zero and N is not
    # divisible by P then there
    # is no possible integer which
    # satisfies the given conditions
    if (Q == 0 and (P == 0 or N % P != 0)):
        print("Not Possible")
        return
     
    count_P = 0
    count_Q = 0
 
    # Loop to find the maximum value
    # of count_P that also satisfy
    # P*count_P + Q*count_Q = N
    while (N > 0):
        if (N % P == 0):
            count_P += N / P
            N = 0
        else:
            N = N - Q
            count_Q += 1
         
    # If N is 0, their is a valid
    # integer possible that satisfies
    # all the requires conditions
    if (N == 0):
         
        # Print Answer
        for i in range(count_Q):
            print(Q, end = "")
        for i in range(int(count_P)):
            print(P, end = "")
    else:
        print("Not Possible")
     
# Driver Code
N = 32
P = 7
Q = 4
 
# Function Call
printMinInteger(P, Q, N)
 
# This code is contributed by code_hunt

C#

// C# program for the above approach
using System;
 
public class GFG {
 
// Function to print the minimum
// integer having only digits P and
// Q and the sum of digits as N
static void printMinint(int P, int Q, int N)
{
   
    // If Q is greater that P then
    // swap the values of P and Q
    if (Q > P) {
        int temp;
        temp = P;
        P = Q;
        Q = temp;
    }
 
    // If P and Q are both zero or
    // if Q is zero and N is not
    // divisible by P then there
    // is no possible integer which
    // satisfies the given conditions
    if (Q == 0 && (P == 0 || N % P != 0)) {
        Console.WriteLine("Not Possible");
        return;
    }
 
    int count_P = 0, count_Q = 0;
 
    // Loop to find the maximum value
    // of count_P that also satisfy
    // P*count_P + Q*count_Q = N
    while (N > 0) {
        if (N % P == 0) {
            count_P += N / P;
            N = 0;
        }
        else {
            N = N - Q;
            count_Q++;
        }
    }
 
    // If N is 0, their is a valid
    // integer possible that satisfies
    // all the requires conditions
    if (N == 0) {
 
        // Print Answer
        for (int i = 0; i < count_Q; i++)
            Console.Write(Q);
        for (int i = 0; i < count_P; i++)
            Console.Write(P);
    }
    else {
        Console.WriteLine("Not Possible");
    }
}
 
// Driver code
public static void Main(String[] args)
{
    int N = 32;
    int P = 7;
    int Q = 4;
 
    // Function Call
    printMinint(P, Q, N);
}
}
 
// This code contributed by shikhasingrajput

Javascript

<script>
// Javascript Program of the above approach
 
// Function to print the minimum
// integer having only digits P and
// Q and the sum of digits as N
function printMinInteger(P, Q, N) {
  // If Q is greater that P then
  // swap the values of P and Q
  if (Q > P) {
    swap(P, Q);
  }
 
  // If P and Q are both zero or
  // if Q is zero and N is not
  // divisible by P then there
  // is no possible integer which
  // satisfies the given conditions
  if (Q == 0 && (P == 0 || N % P != 0)) {
    document.write("Not Possible");
    return;
  }
 
  let count_P = 0,
    count_Q = 0;
 
  // Loop to find the maximum value
  // of count_P that also satisfy
  // P*count_P + Q*count_Q = N
  while (N > 0) {
    if (N % P == 0) {
      count_P += Math.floor(N / P);
      N = 0;
    } else {
      N = N - Q;
      count_Q++;
    }
  }
 
  // If N is 0, their is a valid
  // integer possible that satisfies
  // all the requires conditions
  if (N == 0) {
    // Print Answer
    for (let i = 0; i < count_Q; i++) document.write(Q);
    for (let i = 0; i < count_P; i++) document.write(P);
  } else {
    document.write("Not Possible");
  }
}
 
// Driver Code
let N = 32;
let P = 7;
let Q = 4;
 
// Function Call
printMinInteger(P, Q, N);
 
// This code is contributed by gfgking.
</script>
Producción

47777

Complejidad de tiempo: O(N)
Complejidad de espacio: O(1)

Publicación traducida automáticamente

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