Dado un número entero N, la tarea es verificar si es una solución a la ecuación 2 * inversa (N) – 1 = N
Ejemplos :
Entrada: N = 73
Salida: Sí
Explicación:
2 * inverso (N) = 2 * 37 = 74
N + 1 = 73 + 1 = 74Entrada: N = 83
Salida: No
Enfoque ingenuo: el enfoque más simple es encontrar el reverso del número dado y verificar si satisface la ecuación 2 * reverso (N) = N + 1 o no e imprimir «Sí» o «No» en consecuencia.
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;
// Iterative function to
// reverse digits of num
int rev(int num)
{
int rev_num = 0;
// Loop to extract all
// digits of the number
while (num > 0) {
rev_num
= rev_num * 10 + num % 10;
num = num / 10;
}
return rev_num;
}
// Function to check if N
// satisfies given equation
bool check(int n)
{
return 2 * rev(n) == n + 1;
}
// Driver Code
int main()
{
int n = 73;
if (check(n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program of the
// above approach
import java.util.*;
class GFG{
// Iterative function to
// reverse digits of num
static int rev(int num)
{
int rev_num = 0;
// Loop to extract all
// digits of the number
while (num > 0)
{
rev_num = rev_num * 10 +
num % 10;
num = num / 10;
}
return rev_num;
}
// Function to check if N
// satisfies given equation
static boolean check(int n)
{
return 2 * rev(n) == n + 1;
}
// Driver Code
public static void main(String[] args)
{
int n = 73;
if (check(n))
System.out.print("Yes");
else
System.out.print("No");
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program of the above approach
# Iterative function to
# reverse digits of num
def rev(num):
rev_num = 0
# Loop to extract all
# digits of the number
while (num > 0):
rev_num = (rev_num * 10 +
num % 10)
num = num // 10
return rev_num
# Function to check if N
# satisfies given equation
def check(n):
return (2 * rev(n) == n + 1)
# Driver Code
n = 73
if (check(n)):
print("Yes")
else:
print("No")
# This code is contributed by code_hunt
C#
// C# program of the above approach
using System;
class GFG{
// Iterative function to
// reverse digits of num
static int rev(int num)
{
int rev_num = 0;
// Loop to extract all
// digits of the number
while (num > 0)
{
rev_num = rev_num * 10 +
num % 10;
num = num / 10;
}
return rev_num;
}
// Function to check if N
// satisfies given equation
static bool check(int n)
{
return 2 * rev(n) == n + 1;
}
// Driver Code
public static void Main(String[] args)
{
int n = 73;
if (check(n))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program of the
// above approach
// Iterative function to
// reverse digits of num
function rev(num)
{
var rev_num = 0;
// Loop to extract all
// digits of the number
while (num > 0) {
rev_num
= rev_num * 10 + num % 10;
num = parseInt(num / 10);
}
return rev_num;
}
// Function to check if N
// satisfies given equation
function check(n)
{
return 2 * rev(n) == n + 1;
}
// Driver Code
var n = 73;
if (check(n))
document.write( "Yes");
else
document.write( "No");
</script>
Producción:
Yes
Enfoque eficiente: la observación clave para optimizar el enfoque anterior es que los números que satisfacen la ecuación dada se pueden representar mediante:
X = 8 * 10 (n-1) – 7
Para verificar si un número X satisface la ecuación anterior, se debe verificar si el número (X + 7) / 8 es una potencia de 10 o no.
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 check y is a power of x
bool isPower(int x, int y)
{
// logarithm function to
// calculate value
int res1 = log(y) / log(x);
double res2 = log(y) / log(x);
// Compare to the result1 or
// result2 both are equal
return (res1 == res2);
}
// Function to check if N
// satisfies the equation
// 2 * reverse(n) = n + 1
bool check(int n)
{
int x = (n + 7) / 8;
if ((n + 7) % 8 == 0
&& isPower(10, x))
return true;
else
return false;
}
// Driver Code
int main()
{
int n = 73;
if (check(n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to check y is a power of x
static boolean isPower(int x, int y)
{
// logarithm function to
// calculate value
double res1 = Math.log(y) / Math.log(x);
double res2 = Math.log(y) / Math.log(x);
// Compare to the result1 or
// result2 both are equal
return (res1 == res2);
}
// Function to check if N
// satisfies the equation
// 2 * reverse(n) = n + 1
static boolean check(int n)
{
int x = (n + 7) / 8;
if ((n + 7) % 8 == 0 &&
isPower(10, x))
return true;
else
return false;
}
// Driver Code
public static void main (String[] args)
{
int n = 73;
if (check(n))
System.out.print("Yes");
else
System.out.print("No");
}
}
// This code is contributed by code_hunt
Python3
# Python3 program to implement
# the above approach
import math
# Function to check y is a power of x
def isPower(x, y):
# logarithm function to
# calculate value
res1 = math.log(y) // math.log(x)
res2 = math.log(y) // math.log(x)
# Compare to the result1 or
# result2 both are equal
return (res1 == res2)
# Function to check if N
# satisfies the equation
# 2 * reverse(n) = n + 1
def check(n):
x = (n + 7) // 8
if ((n + 7) % 8 == 0 and
isPower(10, x)):
return True
else:
return False
# Driver Code
n = 73
if (check(n) != 0):
print("Yes")
else:
print("No")
# This code is contributed by code_hunt
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to check y is a power of x
static bool isPower(int x, int y)
{
// logarithm function to
// calculate value
double res1 = Math.Log(y) / Math.Log(x);
double res2 = Math.Log(y) / Math.Log(x);
// Compare to the result1 or
// result2 both are equal
return (res1 == res2);
}
// Function to check if N
// satisfies the equation
// 2 * reverse(n) = n + 1
static bool check(int n)
{
int x = (n + 7) / 8;
if ((n + 7) % 8 == 0 &&
isPower(10, x))
return true;
else
return false;
}
// Driver Code
static public void Main ()
{
int n = 73;
if (check(n))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by code_hunt
Javascript
<script>
// JavaScript program for
// the above approach
// Function to check y is a power of x
function isPower(x, y)
{
// logarithm function to
// calculate value
let res1 = Math.log(y) / Math.log(x);
let res2 = Math.log(y) / Math.log(x);
// Compare to the result1 or
// result2 both are equal
return (res1 == res2);
}
// Function to check if N
// satisfies the equation
// 2 * reverse(n) = n + 1
function check(n)
{
let x = (n + 7) / 8;
if ((n + 7) % 8 == 0 &&
isPower(10, x))
return true;
else
return false;
}
// Driver code
let n = 73;
if (check(n) != 0)
document.write("Yes");
else
document.write("No");
// This code is contributed by splevel62.
</script>
Producción:
Yes
Complejidad temporal: O(log N)
Espacio auxiliar: O(1)