Home > Backend Development > C++ > C++ represents the number of powers of a number

C++ represents the number of powers of a number

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
Release: 2023-08-27 09:05:13
forward
782 people have browsed it

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.
Copy after login

where c0, c1, c2 can be -1, 0, 1, indicating whether to subtract the (-1) term, add the (1) term, Excluding the (0) term −

c0(x^0) + c1(x^1) + c2(x^2) + c3(x^3) + … = y ….(1),
Copy after login

Taking x as a common factor,

c1(x^1) + c2(x^2) + c3(x^3) + … = y - c0,
Copy after login

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),
Copy after login

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;
}
Copy after login

Conclusion

In this tutorial, we discussed how to check whether the representation of a number can be expressed in terms of another number Expressed by powers. We discussed a simple way to solve this problem by checking whether the current number, the previous number and the next number are divisible by y.

We also discussed C programs to solve this problem, which we can implement using programming languages ​​​​such as C, Java, and Python. Hope this tutorial is helpful to you.

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!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template