从2到n-1不同进制下数字的各位数字之和

---

问题陈述包括打印用户输入的数字N在从2到N-1的不同进制下的各位数字之和。

在这个问题中，我们将得到任意正整数N，我们需要将该数字表示为从2到N-1的不同进制数系统，并找到每个不同进制数系统中数字的和。

在n进制数系统中，任何数字在该数系统中的表示形式中的每个数字从右到左分别代表n的0次幂到31次幂的倍数。

例如，当5用2进制数系统表示时，

它表示为101，即 $\mathrm{2^{2}+2^{0}=5}$

同时，当5用3进制数系统表示时，

它表示为12，即 $\mathrm{3^{1}+2*3^{0}=3+2=5}$

让我们通过下面的例子来理解这个问题。

输入

N=6

输出

2 2 3 2

解释 - 给定的输入是6。因此，我们需要找到N（即6）在从2到5的不同进制数系统中表示时的各位数字之和。

当6用2进制数系统表示时，它写为110，即$\mathrm{2^{2}+2^{1}=6}$

6在2进制表示下的各位数字之和为2

6在3进制数系统中的表示为20，即$\mathrm{2*3^{1}=6}$。6在3进制下的各位数字之和为2。

6在4进制数系统中的表示为12，即$\mathrm{4^{1}+2*4^{0}=4+2=6}$。6在4进制表示下的各位数字之和为1+2=3。

6在5进制数系统中的表示为11，即$\mathrm{5^{1}+5^{0}=6}$。6在5进制数系统中的各位数字之和为2。

因此，我们需要的输出是2 2 3 2。

输入

N=9

输出

2  1  3  5  4  3  2

解释 - 由于输入是9，我们需要将9表示为从2到8的不同进制数系统，并找到每个表示的各位数字之和。因此，

9在2进制下：1001，因此各位数字之和为2。

9在3进制下：100，因此各位数字之和为1。

9在4进制下：21，各位数字之和为3。

9在5进制下：14，各位数字之和为5。

9在6进制下：13，各位数字之和为4。

9在7进制下：12，各位数字之和为3。

9在8进制下：11，各位数字之和为2。

因此，我们需要的输出是2 1 3 5 4 3 2。

让我们了解一下打印数字在不同进制数系统中表示时的各位数字之和的算法。

算法

由于我们需要找到数字N在从2到N-1的每个进制中的表示的各位数字之和，我们将创建一个函数来查找每个进制表示的N的和。

为了将任何数字N表示为任何进制数，我们取该数字与进制数的模，这表示从右到左的每个数字，然后将数字除以进制数，直到N变为0，以获得该数字在特定进制数系统中的表示。

例如，我们需要将9表示为5进制数系统。

将9除以5得到余数4，因此最右边的数字将是4，然后通过将9除以5来更新N，得到1。

现在，将1除以5得到余数1，因此前一个数字左边的下一个数字将是1，然后N将为0。

因此，9在5进制数系统中的表示将是14，表示$\mathrm{5^{1}+4*5^{0}=9}$

由于我们只需要N在不同进制值中表示的各位数字之和，我们将简单地将N除以进制值得到的余数加到存储各位数字之和的变量中，然后通过将N除以进制值来更新N，直到N大于0，以获得N在不同进制值中表示时的各位数字之和。

为了解决这个问题，我们将使用此算法来计算我们在方法中从2到N-1的不同进制值中表示的N的各位数字之和。

方法

在我们的方法中实现上述算法的步骤

• 我们将简单地创建一个函数，用于给出N在从2到N-1的不同进制值中表示时的各位数字之和，其中传递的参数将是N和进制数。

• 我们将在一个while循环中迭代，直到N大于0，在该循环中，我们将找到N除以进制数的余数，并将其添加到存储各位数字之和的变量中，然后通过将N除以进制数来更新N。

• 一旦N变为0，返回存储在变量中的各位数字之和。

• 在一个for循环中从i=2迭代到i<=N-1，以找到N在不同进制数中表示时的各位数字之和，其中i代表特定的进制数。

• 我们将通过调用函数来打印每个不同进制的各位数字之和，该函数用于计算N在for循环中从2到N-1的每个i值的不同进制中表示时的各位数字之和。

示例

// C++ program to print the Sum of digits written in different bases from 2 to N-1
#include<bits/stdc++.h>

using namespace std;

//function to give the sum of digits of N when represented in a particular base
int sumOfDigit(int N,int B)
{
    int sum = 0;  //variable to store the sum of digits
    //iterate until N is greater than zero
    while(N > 0)
    {
        
     int rem=N % B;  //finding the remainder of N when divided by base number 
     
     sum=sum + rem;  //add remainder with sum  to store the sum of digits
     
     N=N / B;  //update N by dividing N by base number
     
    }
    
    return sum;  //return the sum of digits stored in the variable
}
int main()
{
    int N=10;
    
    cout<<"Sum of digits written in different bases from 2 to N-1 : " <<endl;
    
    //using for loop from i=2 to i<=N-1 to find the sum of digits of N when represented in different base number
    for(int i =2; i<=N-1; i++){
        
        //printing the sum of digits of each different bases by calling the function to calculate the sum of digits of N 
        cout<<sumOfDigit(N,i)<<"  ";
        
    }
    return 0;
}

输出

Sum of digits written in different bases from 2 to N-1 
2  2  4  2  5  4  3  2 

时间复杂度 - O(N*logN)，因为它花费了log N的时间来计算不同进制中各位数字之和。

空间复杂度 - O(1)，因为我们的方法没有使用额外的空间。

结论

本文讨论了打印N在从2到N-1的不同进制中表示时的各位数字之和的概念。我们使用了一种有效的方法，在C++中以(log N)的运行时间和常量空间内找到N在不同进制值中的各位数字之和。

我希望您在阅读本文后能够理解这个概念和问题的解决方案。