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 .
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.
// CPP program to check if m can be represented
// as powers of w.
((m - 1) % w == 0)
m = (m - 1) / w;
((m + 1) % w == 0)
m = (m + 1) / w;
(m % w == 0)
m = m / w;
// None of 3 worked.
// If m is not zero means, it can't be
// represented in terms of powers of w.
(m == 0);
// Driver code
w = 3, m = 7;
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/representation-number-powers/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements