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? :slight_smile:

1 Like

Pls share the approach

include <stdio.h>

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 :confused:

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>
T read()
{
    T toRead;
    cin >> toRead;
    assert(cin);
    return toRead;
}

int main(int argc, char* argv[])
{
    ios::sync_with_stdio(false);
    
    const auto T = read<int>();

    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++)
    {
        const int n = read<int>();
        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