[hacker rank] Extra long factorial

문제 링크

 

풀이

배열 요소에 하나에 한 자리씩 넣어서 표현하면 됩니다. 올림 수는 그다음 배열로 넘기면 됩니다. 올림 수를 다음 배열로 넘겨야 하는데 배열의 공간이 부족할 때는, push_back(0)을 하여 0을 임시값으로 넣어주고 배열 공간을 늘립니다.

 

코드1

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	int N = 25;	
	vector<int> answer;
	answer.push_back(1);
	// number to multifly
	for (int i = 2; i <= N; ++i)
	{
		for (auto it = answer.begin(); it != answer.end(); ++it)
			*it *= i;
		for (size_t j = 0; j < answer.size(); ++j)
		{
			auto a = answer[j];
			if (a < 10) continue;

			if (answer.size() == j + 1)
				answer.push_back(0);// increae digit
			answer[j] = a % 10;
			answer[j + 1] += a / 10;
		}
	}
	for (auto it = answer.rbegin(); it != answer.rend(); ++it)
		cout << *it;
}

 

코드2(추가)

#include <cstdio>
#include <vector>
using namespace std;

void extraLongFactorials(int n)
{
	vector<int> answer;
	answer.push_back(1);
	for (int i = 2; i <= n; ++i)
	{
		int carry = 0;
		for (int j = 0; j < answer.size(); ++j)
		{
			auto res = i * answer[j] + carry;
			if (res < 10)
			{
				answer[j] = res;
				carry = 0;
				continue;
			}
			else if (j + 1 == answer.size())
				answer.push_back(0);
			answer[j] = res % 10;
			carry = res / 10;
		}
	}
	for (auto it = answer.rbegin(); it != answer.rend(); ++it)
		printf("%d", *it);
}