Given two numbers w and m, we need to determine whether it is possible to represent m in terms of powers of w. The powers of number w can be added or subtracted to obtain m and each powers of w can be used only once .
Examples:
Input : 3 7 Output : Yes As 7 = 9 - 3 + 1 (3^2 - 3^1 + 3^0 ) so it is possible . Input : 100 50 Output : No As 50 is less than 100 so we can never represent it in the powers of 100 .
Here we have to represent m in terms of powers of w used only once so it can be shown through the following equation .
c0 + c1*w^1 + c2*w^2 + … = m —— (Equation 1)
Where each c0, c1, c2 … are either -1 (for subtracting that power of w ), 0 (not using that power of w ), 1 (for adding that power of w ) .
=> c1*w^1 + c2*w^2 + … = m – c0
=> w(c1 + c2*w^1 + c3*w^2 + … ) = m – c0
=> c1 + c2*w^1 + c3*w^2 + … = (m – c0)/w —— (Equation 2)
Now, notice equation 1 and equation 2 — we are trying to solve the same problem all over again. So we have to recurse till m > 0 . For such a solution to exist (m — ci) must be a multiple of w, where ci is the coefficient of the equation . The ci can be -1, 0, 1 . So we have to check for all three possibilities ( ( m – 1 ) % w == 0), ( ( m + 1 ) % w == 0) and ( m % w == 0) . If it is not, then there will not be any solution.
C++
// CPP program to check if m can be represented// as powers of w.#include <bits/stdc++.h>using namespace std;bool asPowerSum(int w, int m){ while (m) { if ((m - 1) % w == 0) m = (m - 1) / w; else if ((m + 1) % w == 0) m = (m + 1) / w; else if (m % w == 0) m = m / w; else break; // None of 3 worked. } // If m is not zero means, it can't be // represented in terms of powers of w. return (m == 0);}// Driver codeint main(){ int w = 3, m = 7; if (asPowerSum(w, m)) cout << "Yes" << endl; else cout << "No" << endl; return 0;} |
Java
// Java program to check if m can // be represented as powers of w.class GFG{ static boolean asPowerSum(int w, int m) { while (m > 0) { if ((m - 1) % w == 0) m = (m - 1) / w; else if ((m + 1) % w == 0) m = (m + 1) / w; else if (m % w == 0) m = m / w; else break; // None of 3 worked. } // If m is not zero means, it can't be // represented in terms of powers of w. return (m == 0); } // Driver function public static void main (String[] args) { int w = 3, m = 7; if (asPowerSum(w, m)) System.out.println("Yes"); else System.out.println("No"); }}// This code is contributed by Anant Agarwal. |
Python3
# Python3 program to check if m can # be represented as powers of w.def asPowerSum(w, m): while (m > 0): if ((m - 1) % w == 0): m = (m - 1) / w; elif ((m + 1) % w == 0): m = (m + 1) / w; elif (m % w == 0): m = m / w; else: break; # None of 3 worked. # If m is not zero means, it can't be # represented in terms of powers of w. return (m == 0);# Driver codew = 3; m = 7;if (asPowerSum(w, m)): print("Yes");else: print("No");# This code is contributed by mits |
C#
// C# program to check if // m can be represented// as powers of w.using System;class GFG{ static bool asPowerSum(int w, int m) { while (m > 0) { if ((m - 1) % w == 0) m = (m - 1) / w; else if ((m + 1) % w == 0) m = (m + 1) / w; else if (m % w == 0) m = m / w; else break; // None of 3 worked. } // If m is not zero means, // it can't be represented // in terms of powers of w. return (m == 0); } // Driver Code static public void Main () { int w = 3, m = 7; if (asPowerSum(w, m)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// This code is contributed // by akt_mit. |
PHP
<?php// PHP program to check if m can // be represented as powers of w.function asPowerSum($w, $m){ while ($m) { if (($m - 1) % $w == 0) $m = ($m - 1) / $w; else if (($m + 1) % $w == 0) $m = ($m + 1) / $w; else if ($m % $w == 0) $m = $m / $w; else break; // None of 3 worked. } // If m is not zero means, it can't be // represented in terms of powers of w. return ($m == 0);}// Driver code$w = 3; $m = 7;if (asPowerSum($w, $m)) echo "Yes\n";else echo "No\n";// This code is contributed by mits?> |
Javascript
<script>// Javascript program to check if m can // be represented as powers of w. function asPowerSum(w, m) { while (m > 0) { if ((m - 1) % w == 0) m = (m - 1) / w; else if ((m + 1) % w == 0) m = (m + 1) / w; else if (m % w == 0) m = m / w; else break; // None of 3 worked. } // If m is not zero means, it can't be // represented in terms of powers of w. return (m == 0); } // Driver code let w = 3, m = 7; if (asPowerSum(w, m)) document.write("Yes"); else document.write("No"); // This code is contributed by sanjoy_62.</script> |
Output:
Yes
Time complexity: O(m)
Auxiliary space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!