We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #16: Power digit sum
  4. Discussions

Project Euler #16: Power digit sum

  • jacobdorais25
     + 0 comments

    in C++, I don't think there are a built in bigInteger like in Java or Python, so I made whatever I needed to make it work.

    #include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <sstream>

constexpr size_t mod = 10000000000000000; // power of 10 relatively close to int64 max.

void doubling(std::vector<size_t>& num)
{
	size_t ret = 0;
	for (int i = 0; i < num.size(); i++)
	{
		size_t localNum = num[i];
		localNum = localNum*2 + ret;
		ret = localNum / mod;
		num[i] = localNum % mod;
	}
	if (ret > 0)
	{
		num.push_back(ret);
	}
}

// for each test case
void run(int n)
{
	std::vector<size_t> num = { 1 };
	for (int i = 0; i < n; i++)
	{
		doubling(num);
	}

	std::stringstream numStream;

	for (int i = num.size() - 1; i >= 0; i--)
	{
		numStream << num[i];
	}

	std::string strnum = numStream.str();
	size_t sum = 0;
	for (char c : strnum)
	{
		sum += (static_cast<int>(c) - '0');
	}

	std::cout << sum << std::endl;

}

int main()
{
	int t;
	std::cin >> t;
	for (;t > 0; t--)
	{
		int n;
		std::cin >> n;
		run(n);
	}
	return 0;
}