Encuentre una solución integral de la ecuación no lineal 2X + 5Y = N

Dado un número entero N que representa una ecuación no lineal de la forma 2 X + 5 Y = N , la tarea es encontrar un par integral ( X , Y ) que satisfaga la ecuación dada. Si existen varias soluciones, imprima cualquiera de ellas. De lo contrario, imprima -1 .

Ejemplos:

Entrada: N = 29 
Salida: X = 2, Y = 2 
Explicación: 
Ya que, 2 2 + 5 2 = 29 
Por lo tanto, X = 2 e Y = 2 satisfacen la ecuación dada.

Entrada: N = 81 
Salida: -1 
 

Enfoque: siga los pasos a continuación para resolver el problema:

  • Inicialice una variable, diga xMax para almacenar el valor máximo posible de X .
  • Actualice xMax para registrar 2 N .
  • Inicialice una variable, diga yMax para almacenar el máximo posible de Y .
  • Actualice yMax para registrar 5 N
  • Itere sobre todos los valores posibles de X e Y y para cada valor de X e Y y para cada par, verifique si satisface la ecuación dada o no. Si se encuentra que es cierto, imprima el valor correspondiente de X e Y.

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

C++

// C++ program to implement
// the above approach
     
     
#include <bits/stdc++.h>
using namespace std;
 
 
// Function to find the value
// of power(X, N)
long long power(long long x,
                long long N)
{
     
    // Stores the value
    // of (X ^ N)
    long long res = 1;
     
     
    // Calculate the value of
    // power(x, N)
    while (N > 0) {
     
     
        // If N is odd
        if (N & 1) {
     
     
            // Update res
            res = (res * x) ;
        }
     
     
        // Update x
        x = (x * x) ;
     
     
        // Update N
        N = N >> 1;
    }
    return res;
}
 
 
 
// Function to find the value of
// X and Y that satisfy the condition
void findValX_Y(long long N)
{
     
 
    // Base Case
    if (N <= 1) {
    cout<<-1<<endl;
    return;
    }
 
 
    // Stores maximum possible
    // of X.
    int xMax;
     
     
    // Update xMax
    xMax = log2(N);
     
     
    // Stores maximum possible
    // of Y.
    int yMax;
     
         
    // Update yMax
    yMax = (log2(N) / log2(5.0));
     
     
    // Iterate over all possible
    // values of X
    for (long long i = 1;
            i <= xMax; i++) {
         
         
        // Iterate over all possible
        // values of Y
        for (long long j=1;
            j <= yMax; j++) {
             
             
            // Stores value of 2^i
            long long a
            = power(2, i);
             
             
            // Stores value of 5^j
            long long b
            = power(5, j);
                 
                 
            // If the pair (i, j)
            // satisfy the equation
            if (a + b == N) {
 
                cout<<i<<" "
                <<j<<endl;
                return;
            }
        }
    }
         
    // If no solution exists
    cout<<-1<<endl;
     
         
}
     
// Driver Code
int main()
{
    long long N = 129;
     
    findValX_Y(N);
     
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
    
// Function to find the value
// of power(X, N)
static int power(int x, int N)
{
     
    // Stores the value
    // of (X ^ N)
    int res = 1;
     
    // Calculate the value of
    // power(x, N)
    while (N > 0)
    {
         
        // If N is odd
        if ((N & 1) != 0)
        {
             
            // Update res
            res = (res * x);
        }
         
        // Update x
        x = (x * x);
         
        // Update N
        N = N >> 1;
    }
    return res;
}
 
// Function to find the value of
// X and Y that satisfy the condition
static void findValX_Y(int N)
{
     
    // Base Case
    if (N <= 1)
    {
        System.out.println(-1);
        return;
    }
 
    // Stores maximum possible
    // of X.
    int xMax;
     
    // Update xMax
    xMax = (int)Math.log(N);
     
    // Stores maximum possible
    // of Y.
    int yMax;
     
    // Update yMax
    yMax = (int)(Math.log(N) / Math.log(5.0));
     
    // Iterate over all possible
    // values of X
    for(int i = 1; i <= xMax; i++)
    {
         
        // Iterate over all possible
        // values of Y
        for(int j = 1; j <= yMax; j++)
        {
             
            // Stores value of 2^i
            int a = power(2, i);
             
            // Stores value of 5^j
            int b = power(5, j);
                 
            // If the pair (i, j)
            // satisfy the equation
            if (a + b == N)
            {
                System.out.print(i + " " + j);
                return;
            }
        }
    }
         
    // If no solution exists
    System.out.println("-1");
}
     
// Driver Code
public static void main(String args[])
{
    int N = 129;
     
    findValX_Y(N);
}
}
 
// This code is contributed by bgangwar59

Python3

# Python3 program to implement
# the above approach
from math import log2
       
# Function to find the value
# of power(X, N)
def power(x, N):
     
    # Stores the value
    # of (X ^ N)
    res = 1
  
    # Calculate the value of
    # power(x, N)
    while (N > 0):
         
        # If N is odd
        if (N & 1):
             
            # Update res
            res = (res * x)
             
        # Update x
        x = (x * x)
         
        # Update N
        N = N >> 1
         
    return res
  
# Function to find the value of
# X and Y that satisfy the condition
def findValX_Y(N):
     
    # Base Case
    if (N <= 1):
       print(-1)
       return
    
    # Stores maximum possible
    # of X
    xMax = 0
     
    # Update xMax
    xMax = int(log2(N))
     
    # Stores maximum possible
    # of Y
    yMax = 0
     
    # Update yMax
    yMax = int(log2(N) / log2(5.0))
     
    # Iterate over all possible
    # values of X
    for i in range(1, xMax + 1):
         
        # Iterate over all possible
        # values of Y
        for j in range(1, yMax + 1):
             
            # Stores value of 2^i
            a = power(2, i)
             
            # Stores value of 5^j
            b = power(5, j)
             
            # If the pair (i, j)
            # satisfy the equation
            if (a + b == N):
                print(i, j)
                return
  
    # If no solution exists
    print(-1)
  
# Driver Code
if __name__ == '__main__':
     
    N = 129
  
    findValX_Y(N)
 
# This code is contributed by mohit kumar 29

C#

// C# program to implement
// the above approach
using System;
class GFG{
    
// Function to find the
// value of power(X, N)
static int power(int x,
                 int N)
{   
  // Stores the value
  // of (X ^ N)
  int res = 1;
 
  // Calculate the value
  // of power(x, N)
  while (N > 0)
  {        
    // If N is odd
    if ((N & 1) != 0)
    {
 
      // Update res
      res = (res * x);
    }
 
    // Update x
    x = (x * x);
 
    // Update N
    N = N >> 1;
  }
  return res;
}
 
// Function to find the
// value of X and Y that
// satisfy the condition
static void findValX_Y(int N)
{    
  // Base Case
  if (N <= 1)
  {
    Console.WriteLine(-1);
    return;
  }
 
  // Stores maximum
  // possible of X.
  int xMax;
 
  // Update xMax
  xMax = (int)Math.Log(N);
 
  // Stores maximum possible
  // of Y.
  int yMax;
 
  // Update yMax
  yMax = (int)(Math.Log(N) /
               Math.Log(5.0));
 
  // Iterate over all possible
  // values of X
  for(int i = 1; i <= xMax; i++)
  {
    // Iterate over all possible
    // values of Y
    for(int j = 1; j <= yMax; j++)
    {
      // Stores value of 2^i
      int a = power(2, i);
 
      // Stores value of 5^j
      int b = power(5, j);
 
      // If the pair (i, j)
      // satisfy the equation
      if (a + b == N)
      {
        Console.Write(i + " " + j);
        return;
      }
    }
  }
 
  // If no solution exists
  Console.WriteLine("-1");
}
 
// Driver Code
public static void Main()
{
  int N = 129;
  findValX_Y(N);
}
}
 
// This code is contributed by surendra_gangwar

Javascript

<script>
 
// JavaScript program to implement the above approach
 
// Function to find the value
// of power(X, N)
function power(x, N)
{
     
    // Stores the value
    // of (X ^ N)
    let res = 1;
     
    // Calculate the value of
    // power(x, N)
    while (N > 0)
    {
         
        // If N is odd
        if ((N & 1) != 0)
        {
             
            // Update res
            res = (res * x);
        }
         
        // Update x
        x = (x * x);
         
        // Update N
        N = N >> 1;
    }
    return res;
}
 
// Function to find the value of
// X and Y that satisfy the condition
function findValX_Y(N)
{
     
    // Base Case
    if (N <= 1)
    {
        document.write(-1);
        return;
    }
 
    // Stores maximum possible
    // of X.
    let xMax;
     
    // Update xMax
    xMax = Math.log(N);
     
    // Stores maximum possible
    // of Y.
    let yMax;
     
    // Update yMax
    yMax = Math.log(N) / Math.log(5.0);
     
    // Iterate over all possible
    // values of X
    for(let i = 1; i <= xMax; i++)
    {
         
        // Iterate over all possible
        // values of Y
        for(let j = 1; j <= yMax; j++)
        {
             
            // Stores value of 2^i
            let a = power(2, i);
             
            // Stores value of 5^j
            let b = power(5, j);
                 
            // If the pair (i, j)
            // satisfy the equation
            if (a + b == N)
            {
                document.write(i + " " + j);
                return;
            }
        }
    }
         
    // If no solution exists
    document.write("-1");
}
 
// Driver Code
 
    let N = 129;
    findValX_Y(N);
     
    // This code is contributed by susmitakundugoaldanga.
</script>

Producción:

2 3

Complejidad de tiempo: O(log 2 N * log 5 N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

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