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