[Challenge] Stepped Sum

[xcessive]

In this problem you will have to write a function that can calculate the stepped sum of a given number. The "stepped sum" of a number is itself, plus its integer division by 2, added to its integer division by 3, and plus the stepped sum of both of these resulting numbers. You must write a program that takes a given number, and calculates its stepped sum.

Here is an example of the stepped sum of 3:
3 + 3/2 + 3/3 + steppedSum(3/2) + steppedSum(3/3)

The maximum size of the number for which you will have to calculate a stepped sum is 10000000.
There will be 100000000 test cases.
Your program must run in 30 seconds or less.

Example of usage in C++
for(int i = 0; i < 100000000; i++)
{
steppedSum((rand() % 10000000 + 1));
}

[Jordan]

Dynamic programming.

#include <iostream>
#include <ctime>
#include <cstdlib> // rand & srand

using namespace std;

static int *dTable;

int steppedSum(int n) {
      if(n == 0) {
            return 0;
      }
      else if(dTable[n] != -1) {
            return dTable[n];
      }

      int originalN = n;
      int steppedTwo = n / 2;
      int steppedThree = n / 3;
      n = n + steppedTwo + steppedThree;

      if(steppedTwo > 0) {
            if(dTable[steppedTwo] != -1) {
                  n = n + dTable[steppedTwo];
            }
            else {
                  n = n + steppedSum(steppedTwo);
            }
      }

      if(steppedThree > 0) {
            if(dTable[steppedThree] != -1) {
                  n = n + dTable[steppedThree];
            }
            else {
                  n = n + steppedSum(steppedThree);
            }
      }

      dTable[originalN] = n;

      return n;
}

int steppedSumRecursive(int n) {
      if(n == 0) {
            return 0;
      }
      int steppedTwo = n / 2;
      int steppedThree = n / 3;
      n = n + steppedTwo + steppedThree + steppedSum(steppedTwo) + steppedSum(steppedThree);
      return n;
}

int main() {
      dTable = new int[1000000];

      for(int i = 0; i < 1000000; i++) {
            dTable = -1;
      }

      clock_t start;
      clock_t stop;
      double runningTime;

      srand(time(NULL));

      start = clock();
      for(int i = 0; i < 1000000000; i++) {
            steppedSum(rand() % 1000000 + 1);
      }
      stop = clock();

      runningTime = ((double)stop - (double)start) / (double)CLOCKS_PER_SEC;
      cout << "Time: " << runningTime << endl;

      delete [] dTable;

      return 0;
}

Look familiar?

[xcessive]

Oct 17, 2012 21:43:43 GMT -5 Jordan said:

Dynamic programming.

#include <iostream>
#include <ctime>
#include <cstdlib> // rand & srand

using namespace std;

static int *dTable;

int steppedSum(int n) {
      if(n == 0) {
            return 0;
      }
      else if(dTable[n] != -1) {
            return dTable[n];
      }

      int originalN = n;
      int steppedTwo = n / 2;
      int steppedThree = n / 3;
      n = n + steppedTwo + steppedThree;

      if(steppedTwo > 0) {
            if(dTable[steppedTwo] != -1) {
                  n = n + dTable[steppedTwo];
            }
            else {
                  n = n + steppedSum(steppedTwo);
            }
      }

      if(steppedThree > 0) {
            if(dTable[steppedThree] != -1) {
                  n = n + dTable[steppedThree];
            }
            else {
                  n = n + steppedSum(steppedThree);
            }
      }

      dTable[originalN] = n;

      return n;
}

int steppedSumRecursive(int n) {
      if(n == 0) {
            return 0;
      }
      int steppedTwo = n / 2;
      int steppedThree = n / 3;
      n = n + steppedTwo + steppedThree + steppedSum(steppedTwo) + steppedSum(steppedThree);
      return n;
}

int main() {
      dTable = new int[1000000];

      for(int i = 0; i < 1000000; i++) {
            dTable = -1;
      }

      clock_t start;
      clock_t stop;
      double runningTime;

      srand(time(NULL));

      start = clock();
      for(int i = 0; i < 1000000000; i++) {
            steppedSum(rand() % 1000000 + 1);
      }
      stop = clock();

      runningTime = ((double)stop - (double)start) / (double)CLOCKS_PER_SEC;
      cout << "Time: " << runningTime << endl;

      delete [] dTable;

      return 0;
}

Look familiar?

F# solution. Terse as hell.


let cache = Array.create 10000001 -1
let rec steppedSum2 = function
| 0 -> 0
| i -> (if cache.[i] = -1 then cache.[i] <- i + i/2 + i/3 + steppedSum2 (i/2) + steppedSum2 (i/3)); cache.[i]


[Jordan]

Damn, that's pretty terse.

The C++ above is my solution from 4OUR, haha.

[xcessive]

Oct 18, 2012 15:06:47 GMT -5 Jordan said:

Damn, that's pretty terse.

The C++ above is my solution from 4OUR, haha.

Yeh I noticed that! I still have it in my 4OUR folder. I really thought it would take you more than a few hours. At least its shorter than prads's solution. He made an entire binary tree structure and created it top down.

[Jordan]

Oct 18, 2012 19:02:20 GMT -5 xcessive said:

Oct 18, 2012 15:06:47 GMT -5 Jordan said:

Damn, that's pretty terse.

The C++ above is my solution from 4OUR, haha.

Yeh I noticed that! I still have it in my 4OUR folder. I really thought it would take you more than a few hours. At least its shorter than prads's solution. He made an entire binary tree structure and created it top down.

Ha, I have a 4OUR folder with all of this stuff too. ;P

Prads is the type of guy that will go all out. I really liked that guy.