# 3n+1 문제 ( Longest Collatz sequence )

#include <iostream>
#include <unordered_map>
#include <time.h>
using namespace std;

#define ARR_SIZE 1000000
#define MAX_NUMBER 1000000

unsigned int CalcChains(unsigned int _num, unsigned int* _chains);
void main() {

 clock_t startTime = 0;
 clock_t endTime = 0;

 unsigned int* chains = new unsigned int[ARR_SIZE];
 for (int i = 0; i < ARR_SIZE; i++) chains[i] = 0;

 unsigned maxChain = 0;
 unsigned maxNumber = 0;
 startTime = clock();
 for (unsigned int num = 1; num <= MAX_NUMBER; ++num) {
  unsigned int chain = CalcChains(num, chains);
  chains[num] = chain;
  if (chain > maxChain) {
   maxChain = chain;
   maxNumber = num;
  }
 }
 endTime = clock();
 cout << "max Chain is : " << maxChain << " and number is : " << maxNumber << endl;
 cout << "execution sec is : " << (double)(endTime - startTime) / CLK_TCK << endl;
 system("pause");
}

unsigned int CalcChains(unsigned int _num, unsigned int* _chainOfNumber) {
 unsigned int chains = 0;
 while (_num >= 1) {
  if (_num == 1) return ++chains;
  if ((_num < ARR_SIZE) && (_chainOfNumber[_num] > 0)) {
   chains += _chainOfNumber[_num];
   break;
  }
  if (_num % 2 == 0) { _num >>= 1; }
  else { _num = (_num * 3) + 1; }
  chains++;
 }
 return chains;
}