Encuentre un triplete (A, B, C) tal que 3*A + 5*B + 7*C sea igual a N

Dado un entero N , la tarea es encontrar tres enteros positivos A , B y C tales que el valor de la expresión (3*A + 5*B + 7*C) sea igual a N . Si no existe tal triplete, imprima «-1» .

Ejemplos:

Entrada: N = 19
Salida:
A = 3
B = 2
C = 0
Explicación: Igualando A, B y C a 0, 1 y 2 respectivamente, el valor evaluado de la expresión = 3 * A + 5 * B + 7 * C = 3 * 3 + 5 * 2 + 7 * 0 = 19, que es lo mismo que N (= 19).

Entrada: N = 4
Salida: -1

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los tripletes posibles con números enteros hasta N y verificar si existe algún triplete (A, B, C), tal que el valor de (3*A + 5*B + 7 * C) es igual a N. Si se encuentra que es cierto, imprima ese triplete. De lo contrario, imprima «-1» . 
Complejidad de Tiempo: O(N ³ )
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar en función de la siguiente observación de que el valor de A se encuentra en el rango [0, N / 3] , el valor de B se encuentra en el rango [0, N / 5] y el valor de C se encuentra en el rango [0, N / 7] . Siga los pasos a continuación para resolver el problema:

• Iterar sobre el rango [0, N/7] y realizar las siguientes operaciones:
  • Iterar sobre el rango [0, N/5] y encontrar el valor de A como (N – 5*j – 7*i) .
  • En el paso anterior, si el valor de A es al menos 0 y A es divisible por 3 , entonces existe un triplete como (A/3, i, j) . Imprime este triplete y sal del bucle .
• Después de completar los pasos anteriores, si no existe tal triplete, imprima «-1» .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find a triplet (A, B, C)
// such that 3 * A + 5 * B + 7 * C is N
void CalculateValues(int N){
 
  int A = 0, B = 0, C = 0;
 
  // Iterate over the range [0, N//7]
  for (C = 0; C < N/7; C++)
  {
 
    // Iterate over the range [0, N//5]
    for ( B = 0; B < N/5; B++)
    {
 
      // Find the value of A
      int A = N - 7 * C - 5 * B;
 
      // If A is greater than or equal
      // to 0 and divisible by 3
      if (A >= 0 && A % 3 == 0)
      {
        cout << "A = " << A / 3 << ", B = " << B << ", C = "<< C << endl;
 
        return;
      }
    }
  }
 
  // Otherwise, print -1
  cout << -1 << endl;
 
}
 
// Driver Code
int main()
{
  int N = 19;
  CalculateValues(19);
 
  return 0;
}
 
// This code is contributed by susmitakundugoaldanga.

// Java program to implement
// the above approach
import java.util.*;
 
class GFG
{
 
  // Function to find a triplet (A, B, C)
  // such that 3 * A + 5 * B + 7 * C is N
  static void CalculateValues(int N)
  {
    int A = 0, B = 0, C = 0;
 
    // Iterate over the range [0, N//7]
    for (C = 0; C < N/7; C++)
    {
 
      // Iterate over the range [0, N//5]
      for ( B = 0; B < N/5; B++)
      {
 
        // Find the value of A
        A = N - 7 * C - 5 * B;
 
        // If A is greater than or equal
        // to 0 and divisible by 3
        if (A >= 0 && A % 3 == 0)
        {
          System.out.print("A = " + A / 3 + ", B = " + B + ", C = "+ C);
 
          return;
        }
      }
    }
 
    // Otherwise, print -1
    System.out.println(-1);
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int N = 19;
    CalculateValues(19);
  }
}
 
// This code is contributed by souravghosh0416.

# Python program for the above approach
 
# Function to find a triplet (A, B, C)
# such that 3 * A + 5 * B + 7 * C is N
def CalculateValues(N):
   
    # Iterate over the range [0, N//7]
    for C in range(0, N//7 + 1):
         
        # Iterate over the range [0, N//5]
        for B in range(0, N//5 + 1):
 
            # Find the value of A
            A = N - 7 * C - 5 * B
 
            # If A is greater than or equal
            # to 0 and divisible by 3
            if (A >= 0 and A % 3 == 0):
                print("A =", A / 3, ", B =", B, ", \
                       C =", C, sep =" ")
                return
     
    # Otherwise, print -1
    print(-1)
    return
 
 
# Driver Code
if __name__ == '__main__':
   
    N = 19
    CalculateValues(19)

// C# program for the above approach
using System;
 
class GFG{
 
  // Function to find a triplet (A, B, C)
  // such that 3 * A + 5 * B + 7 * C is N
  static void CalculateValues(int N)
  {
    int A = 0, B = 0, C = 0;
 
    // Iterate over the range [0, N//7]
    for (C = 0; C < N/7; C++)
    {
 
      // Iterate over the range [0, N//5]
      for ( B = 0; B < N/5; B++)
      {
 
        // Find the value of A
        A = N - 7 * C - 5 * B;
 
        // If A is greater than or equal
        // to 0 and divisible by 3
        if (A >= 0 && A % 3 == 0)
        {
          Console.Write("A = " + A / 3 + ", B = " + B + ", C = "+ C);
 
          return;
        }
      }
    }
 
    // Otherwise, print -1
    Console.WriteLine(-1);
  }
 
  // Driver Code
  static public void Main()
  {
    int N = 19;
    CalculateValues(19);
  }
}
 
// This code is contributed by splevel62.

<script>
 
// Javascript program for the above approach
 
// Function to find a triplet (A, B, C)
// such that 3 * A + 5 * B + 7 * C is N
function CalculateValues(N){
 
var A = 0, B = 0, C = 0;
 
// Iterate over the range [0, N//7]
for (C = 0; C < N/7; C++)
{
 
    // Iterate over the range [0, N//5]
    for ( B = 0; B < N/5; B++)
    {
 
    // Find the value of A
    var A = N - 7 * C - 5 * B;
 
    // If A is greater than or equal
    // to 0 and divisible by 3
    if (A >= 0 && A % 3 == 0)
    {
        document.write( "A = " + A / 3 + ", B = " + B + ", C = "+ C );
 
        return;
    }
    }
}
 
// Otherwise, print -1
document.write( -1 );
 
}
 
// Driver Code
 
var N = 19;
CalculateValues(19);
 
 
</script>

A = 3, B = 2, C = 0

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)