Given an integer N, the task is to check if it is a solution to the equation 2 * reverse(N) – 1 = N
Examples:
Input: N = 73
Output: Yes
Explanation:
2 * reverse(N) = 2 * 37 = 74
N + 1 = 73 + 1 = 74Input: N = 83
Output: No
Naive Approach: The simplest approach is to find the reverse of the given number and check if it satisfies the equation 2 * reverse(N) = N + 1 or not and print “Yes” or “No” accordingly.
Below is the implementation of the above approach:
C++
// C++ program of the// above approach#include <bits/stdc++.h>using namespace std;// Iterative function to// reverse digits of numint 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 equationbool check(int n){ return 2 * rev(n) == n + 1;}// Driver Codeint main(){ int n = 73; if (check(n)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java program of the// above approachimport java.util.*;class GFG{// Iterative function to// reverse digits of numstatic 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 equationstatic boolean check(int n){ return 2 * rev(n) == n + 1;}// Driver Codepublic 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 = 73if (check(n)): print("Yes") else: print("No") # This code is contributed by code_hunt |
C#
// C# program of the above approachusing System;class GFG{// Iterative function to// reverse digits of numstatic 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 equationstatic bool check(int n){ return 2 * rev(n) == n + 1;}// Driver Codepublic 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 numfunction 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 equationfunction check(n){ return 2 * rev(n) == n + 1;}// Driver Codevar n = 73;if (check(n)) document.write( "Yes");else document.write( "No");</script> |
Output:
Yes
Time Complexity: O(log10N)
Auxiliary Space: O(1)
Efficient Approach: The key observation to optimize the above approach is that the numbers satisfying the given equation can be represented by:
X = 8 * 10(n-1) – 7
To check if a number X satisfies the above equation, it needs to be checked if the number (X + 7) / 8 is a power of 10 or not.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to check y is a power of xbool 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 + 1bool check(int n){ int x = (n + 7) / 8; if ((n + 7) % 8 == 0 && isPower(10, x)) return true; else return false;}// Driver Codeint 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 approachimport 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 = 73if (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> |
Output:
Yes
Time Complexity: O(log N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
