 # Digit sum Power

Pls share the efficient approach for finding sum of digits of 2^n
where n is given integer

Link to original Problem? 1 Like

Pls share the approach

# include <math.h>

main()

{
int n, i, sum = 0, m;
scanf("%d", &n);
unsigned long long int num = pow(2, n);
while (num>0)
{
m = num%10;
sum = sum + m;
num = num/10;
}
printf(“Summantion of digits of 2^n for n = %d is %d”, n, sum);
}

This won’t work as `n` can be up to 10^4, and 2^{10^4} is far too large to fit into a `unsigned long long int` Simply emulating decimal multiplication by 2 is enough to get AC:

``````// Simon St James (ssjgz) - 2019-12-31
//
// Solution to: https://www.hackerrank.com/contests/code-plus/challenges/euler016
//
#include <iostream>
#include <vector>

#include <cassert>

using namespace std;

template <typename T>
{
assert(cin);
}

int main(int argc, char* argv[])
{
ios::sync_with_stdio(false);

vector<int> sumOfDigitsForPowerOf2;
sumOfDigitsForPowerOf2.push_back(1); // 2^0.

const int maxN = 10'000;

// The decimal representation of 2^n, stored backwards for efficiency as prepending to a string is O(N).
string powerOf2Backwards = "1";

for (int n = 1; n <= maxN; n++)
{
// Emulate decimal multiplication by 2.
int carry = 0;
string nextPowerOf2Backwards;
for (int digitIndex = 0; digitIndex < powerOf2Backwards.size(); digitIndex++)
{
const int digitValue = powerOf2Backwards[digitIndex] - '0';
int doubleDigitValue = 2 * digitValue + carry;
carry = 0;
if (doubleDigitValue >= 10)
{
carry = 1;
doubleDigitValue -= 10;
assert(doubleDigitValue < 10);
}
nextPowerOf2Backwards += doubleDigitValue + '0';
}
if (carry)
nextPowerOf2Backwards += '1';

powerOf2Backwards = nextPowerOf2Backwards;

int64_t digitSum = 0;
for (const auto digit : powerOf2Backwards)
{
digitSum += (digit - '0');
}
sumOfDigitsForPowerOf2.push_back(digitSum);
}

for (int t = 0; t < T; t++)
{
cout << sumOfDigitsForPowerOf2[n] << endl;

}

assert(cin);
}
``````
1 Like

just do in python
x = 2**n
sum of digits in x

``````t = int(input())
for _ in range(t):
n = int(input())
x = 2**n
sum=0
while(x):
sum+=x%10;
x//=10;
print(sum)``````

we can do in python for n = 1000000 , but i don’t know for larger than 10 power 6

1 Like