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