Home > Article > Backend Development > C++ represents the number of powers of a number
Discuss the problem of expressing one number by using the power of another number. Given two numbers, x and y. We need to determine whether y can be expressed in terms of powers of x, where each power of As an example of power representation, we can form an equation −
Input: x = 4, y = 11 Output: true Explanation: 4^2 - 4^1 - 4^0 = 11 Hence y can be represented in the power of x. Input: x = 2, y = 19 Output: true Explanation: 2^4 + 2^1 + 2^0 =19 Hence y can be represented in the power of x. Input: x = 3, y = 14 Output: false Explanation: 14 can be represented as 3^2 + 3^1 + 3^0 + 3^0 but we cannot use one term of power of x twice.
c0(x^0) + c1(x^1) + c2(x^2) + c3(x^3) + … = y ….(1),
Taking x as a common factor,
c1(x^1) + c2(x^2) + c3(x^3) + … = y - c0,
From equations (1) and (2) we can represent the numbers again, in order for there to be a solution, (y - Ci) should be divisible by x, while Ci can only contain -1, 0 and 1.
So finally we need to check until y>0, whether it satisfies [(y-1) % x == 0] or [(y) % x == 0] or [(y 1) % x = = 0], or if no solution exists.
Example
c1(x^0) + c2(x^1) + c3(x^2) + … = (y - c0)/x ….(2),
Output
#include <bits/stdc++.h> using namespace std; int main(){ int x = 2, y = 19; // checking y divisibility till y>0 while (y>0) { // If y-1 is divisible by x. if ((y - 1) % x == 0) y = (y - 1) / x; // If y is divisible by x. else if (y % x == 0) y = y / x; // If y+1 is divisible by x. else if ((y + 1) % x == 0) y = (y + 1) / x; // If no condition satisfies means // y cannot be represented in terms of power of x. else break; } if(y==0) cout<<"y can be represented in terms of the power of x."; else cout<<"y cannot be represented in terms of the power of x."; return 0; }
The above is the detailed content of C++ represents the number of powers of a number. For more information, please follow other related articles on the PHP Chinese website!