CCC2: Approach to solve SAP Community Coding Challenge Nr.2

There are 2 approaches one with cache and without cache. as caching is efficient for this challenge, but need to can easily break with huge number will limited memory capacity.

Approach:

1. Create a cache to hold results, that are already processed.
2. Initialize Cache with predefined values, i.e 1 will always by 1. (1 => 3*1+1 => 4/2 => 2/2 => 1). We can also predefined multiple values such as Sq-rt(2) till max values, as this always produces liner results ( 2 requires 2 step, 4=>3 steps, 8=> 4, 16=>5,...so on). but since i am not sure whether this holds good for this challenges, i am not pre-initializing them.
3. I am using array for caching, as we know the size of the cache, and lookup on array are much faster then looking up on object(sorted / unsorted).
4. Coming to calculation, as state in question, if the number is even divide by 2(n/2) else three times the value and add one (3n+1). With basic math we can reduce the problem to Reduced Collatz conjecture which state, if number is odd then ((3n + 1) / 2) else (n/2), thus reducing the number of recursion. i.e odd number multiplied by odd number will always yield odd value, and adding 1 to odd value will always make it even. So the movement we execute (3n + 1), it will make the next number as even number, knowing that we can process 2 steps at a time.
5. Here we can also calculate the number of steps required to make this even number odd, i.e for value 100, it takes 2 steps 100/2 => 50/2 => 25, thus reducing 2 loops. The performance will impact depending upon the execution time required to identify the number of steps.
6. The exit condition for the loop. if the processing values go down the actual value, then we can just simply lookup to the cache for remaining steps, as we are calculating from the lowest number.
7. Once we exit compare the current results and previous max value, and swap if current value is greater than previous. (calculating on the entire Array with Math.max might burst out memory)
8. For checking odd or even, the modulus operator and bit wise operator didn't make much difference on the performance, but the bit wise shift for divide helped to get a slight better performance.

Posting both approach, with cache and without cache.

With Cache:

Executable Code: https://repl.it/@girishnvmg/CollatzSequenceWithCache

console.log("SAP CCD-2: Longest Collatz sequence with cache")

let maxNumber = 1000000;
let cache = new Array(maxNumber + 1).fill(false);
let processStartTime = process.hrtime();
let maxStep = 0;
let maxValue = 0;
cache[0] = cache[1] = 1;

let calcSteps = (value) => {
    let val = value
    let step = 0;
  
    while(value >= val)
    {
      if(value & 1)  { value = 3 * value + 1; step ++ }
      value = value >>> 1;
      step += 1;
    }
    
    if((step + cache[value]) > maxStep)
    {
      maxStep = step + cache[value];
      maxValue = val;
    }
    return step + cache[value];
}

for(let i = 2; i < maxNumber; i++)
  cache[i] = calcSteps(i);

console.log(`Value: ${maxValue} - Steps: ${maxStep}. [Time Taken :  ${process.hrtime(processStartTime)[1] /1000000 }ms]`)

Without Cache

Executable Link: https://repl.it/@girishnvmg/CollatzSequenceWithoutCache

console.log("SAP CCD-2: Longest Collatz sequence without cache")

let maxNumber = 1000000;
let processStartTime = process.hrtime();
let maxStep = 0;
let maxValue = 0;
let i = 1

let calcSteps = (value) => {
    let val = value;
    let step = 1;
    while (value != 1) {
      if(value & 1)  { value = 3 * value + 1; step ++ }
      value = value >>> 1;
      step += 1;
    }
    if(maxStep < step)
      {
        maxStep = step;
        maxValue = val;
      }
}

while(i <= maxNumber)
  calcSteps(i++);

console.log(`Value: ${maxValue} - Steps: ${maxStep}. [Time Taken :  ${process.hrtime(processStartTime)[1] /1000000 }ms]`)

#Stay Healthy, #Stay Safe.