原文:https://www . geesforgeks . org/check-if-a-number-n-可表示为-x-or-not 的幂之和/
给定两个正数 N 和 X ，任务是检查给定的数字 N 是否可以表示为XT9】的不同次幂之和。如果发现为真，则打印“是”，否则打印“否”。
例:
输入: N = 10，X = 3输出:是说明:给定值 N(= 10)可写成(1 + 9) = 3 0 + 3 2 。因为 X(= 3)的所有幂都是不同的。因此，打印“是”。
输入: N= 12，X = 4T5输出:**否
方法:给定的问题可以通过检查号 N 是否可以写成 base X 来解决。按照以下步骤解决问题:
- 迭代一个循环直到 N 的值至少为0并执行以下步骤:
- 当 N 除以 X 时，计算余数 rem 的值。
- 如果 rem 的值至少为2，则打印“否”并返回。
- 否则，将 N 的值更新为 N / X 。
- 完成上述步骤后，如果不存在任何终止，则打印“是”，因为 N 处的结果可以用 X 的不同幂表示。
下面是上述方法的实现:
C++
// C++ program for the above approach#include using namespace std;// Function to check if the number N// can be expressed as the sum of// different powers of X or notbool 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 Codeint main(){ int N = 10, X = 3; if (ToCheckPowerofX(N, X)) { cout << "Yes"; } else { cout << "No"; } return 0;}
Java 语言(一种计算机语言，尤用于创建网站)
// Java program for the above approachimport 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 notstatic 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 Codepublic 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
Python 3
# 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 notdef 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 Codeif __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 approachusing System;class GFG{// Function to check if the number N// can be expressed as the sum of// different powers of X or notstatic 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 codepublic 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,
java 描述语言
Output:
Yes
时间复杂度: O(log N)辅助空间: O(1)