Check if a number N can be expressed as the sum of powers of X or not
Given two positive numbers N and X, the task is to check if the given number N can be expressed as the sum of distinct powers of X. If found to be true, then print “Yes”, Otherwise, print “No”.
Examples:
Input: N = 10, X = 3
Output: Yes
Explanation:
The given value of N(= 10) can be written as (1 + 9) = 30 + 32. Since all the power of X(= 3) are distinct. Therefore, print Yes.Input: N= 12, X = 4
Output: No
Approach: The given problem can be solved by checking if the number N can be written in base X or not. Follow the steps below to solve the problem:
- Iterate a loop until the value of N is at least 0 and perform the following steps:
- Calculate the value of remainder rem when N is divided by X.
- If the value of rem is at least 2, then print “No” and return.
- Otherwise, update the value of N as N / X.
- After completing the above steps, if there doesn’t exist any termination, then print “Yes” as the result at N can be expressed in the distinct power of X.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if the number N // can be expressed as the sum of // different powers of X or not bool ToCheckPowerofX( int n, int x) { // While n is a positive number while (n > 0) { // Find the remainder int rem = n % x; // If rem is at least 2, then // representation is impossible if (rem >= 2) { return false ; } // Divide the value of N by x n = n / x; } return true ; } // Driver Code int main() { int N = 10, X = 3; if (ToCheckPowerofX(N, X)) { cout << "Yes" ; } else { cout << "No" ; } return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG{ // Function to check if the number N // can be expressed as the sum of // different powers of X or not static boolean ToCheckPowerofX( int n, int x) { // While n is a positive number while (n > 0 ) { // Find the remainder int rem = n % x; // If rem is at least 2, then // representation is impossible if (rem >= 2 ) { return false ; } // Divide the value of N by x n = n / x; } return true ; } // Driver Code public static void main (String[] args) { int N = 10 , X = 3 ; if (ToCheckPowerofX(N, X)) { System.out.print( "Yes" ); } else { System.out.print( "No" ); } } } // This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach # Function to check if the number N # can be expressed as the sum of # different powers of X or not def ToCheckPowerofX(n, x): # While n is a positive number while (n > 0 ): # Find the remainder rem = n % x # If rem is at least 2, then # representation is impossible if (rem > = 2 ): return False # Divide the value of N by x n = n / / x return True # Driver Code if __name__ = = '__main__' : N = 10 X = 3 if (ToCheckPowerofX(N, X)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by bgangwar59 |
C#
// C# program for the above approach using System; class GFG{ // Function to check if the number N // can be expressed as the sum of // different powers of X or not static bool ToCheckPowerofX( int n, int x) { // While n is a positive number while (n > 0) { // Find the remainder int rem = n % x; // If rem is at least 2, then // representation is impossible if (rem >= 2) { return false ; } // Divide the value of N by x n = n / x; } return true ; } // Driver code public static void Main(String []args) { int N = 10, X = 3; if (ToCheckPowerofX(N, X)) { Console.Write( "Yes" ); } else { Console.Write( "No" ); } } } // This code is contributed by code_hunt, |
Javascript
<script> // JavaScripts program for the above approach // Function to check if the number N // can be expressed as the sum of // different powers of X or not function ToCheckPowerofX(n, x) { // While n is a positive number while (n > 0) { // Find the remainder var rem = n % x; // If rem is at least 2, then // representation is impossible if (rem >= 2) { return false ; } // Divide the value of N by x n = n / x; } return true ; } // Driver Code var N = 10, X = 3; if (ToCheckPowerofX(N, X)) { document.write( "Yes" ); } else { document.write( "No" ); } </script> |
Output:
Yes
Time Complexity: O(log N)
Auxiliary Space: O(1)