0
likes
48 views
0
comments

I present the solutions for 'SAP Community Coding Challenge Nr.2- collatz sequence'. In the given algorithmic problem 3 different approaches of tackling the problem which are a result of optimizations are explained. The approaches are a result of consistent reduction in time and space complexity.

i. Space complexity is analyzed based on the maximum elements that all data structures are holding in the course of solution.

ii. Time complexity is based on the number of steps (computations) that the system has to undergo to derive the solution. (which will reflect as the computation time)

**Approach 1-**

A simple implementation and meeting the expectations of the problem statement.

// Basic version let max_steps=0,steps=0,max_val=0,val=0; for(i=1;i<=1e6;i++) { val=i; steps=0; while(val!=1) { if(val%2==0) val/=2; else val=3*val+1; steps++; } if(steps>max_steps) { max_steps=steps; max_val=i; } } console.log('The maximum value is ' +max_val+' , number of steps is '+max_steps);

Link- https://repl.it/@NishchalManjanb/Basic-Collatz-Soln

We can compute the total number of steps that are taken to complete the computation. Ex- 2->1 -> chain length of 1. 3->10->5->16->8->4->2->1 -> chain length of 7. ...

If we add all the chains up to a million we come to 131,434,424. Also by using hash map we can compute the number of unique integers that are visited in this course, which turns out to be 2,168,610. So an optimal approach would be to store/cache the results. As we can see we are unnecessarily computing the numbers again and again.

**Drawbacks-**

1. A very time consuming procedure.

2. ~131 million steps are taken to reach the answer.

**Approach 2-**

1. Caching/ storing the intermediate results.

2. Array is used for caching as a lookup table.

3. Recursion is used so we can add the intermediate steps into cache array.

let max_steps=0,steps=0,max_val=0,val=0; var cache=[]; cache[1]=0; let cal_steps = (n)=> { if(cache[n]==undefined) cache[n]=1+cal_steps(n%2?3*n+1:n/2); return cache[n]; } for(let i=2;i<=1e6;i++) { steps=cal_steps(i); if(steps>max_steps) { max_steps=steps; max_val=i; } } console.log('The maximum value is ' +max_val+' , number of steps is '+max_steps); // console.log('Length of cache memory is ' + cache.length);

Link- https://repl.it/@NishchalManjanb/cached-collatz

We compute the largest element that is reached in the course of computation up to 1 million, which is 56,991,483,520. Since dynamic array is used, the size of cache utilized is 4,286,786,813. So in order to store the steps reachable from around 2.168 million unique elements we are wasting large amounts of memory.

**Drawbacks-**

A lot of space is wasted, just to store 2.168 million steps for numbers,we have an array that takes large space.

**Approach 2.2**- (Tweaking the above approach)

We can limit the size of array to 1 million and populate the array when we have fully computed the number of steps for a particular element under consideration.

Ex- 2->1 update cache[2]=1, 3->10->5->16->8->2->1 update cache[3]=7. Though we can limit the size of array to 1 million instead of running in billions, we are missing on important computations. In case of number 3, we see that from 10 we can reach 1 in 6 steps and from 5 in 5 steps. But we are missing out on these essential computations and recalculating when we are processing for 5 and 10. Though we are saving on space we are less efficient in dynamic caching.

**Approach 3-**

1. Make use of key-value pair/hash map.

2. Instead of an array where index represented the number, and value of array represented the number of steps, the key-value pair take the job respectively.

let max_steps=0,steps=0,max_val=0,val=0; var dict={1:0}; //object: key-value pair, instead of an array.Map also can used. let cal_steps = (n)=> { if(dict[n]==undefined) dict[n]=1+cal_steps(n%2?3*n+1:n/2); return dict[n]; } for(let i=2;i<=1e6;i++) { steps=cal_steps(i); if(steps>max_steps) { max_steps=steps; max_val=i; } } console.log('The maximum value is ' +max_val+' , number of steps is '+max_steps); // console.log('Number of elements stored in Map = '+ Object.keys(dict).length);

Link- https://repl.it/@NishchalManjanb/map-approach

We can see that the size of the hash map is ~ 2.168 million which is equal to the number of unique numbers visited in the course.

**Improvement points-**

1. Can statistical analysis provide which elements are more prone to larger chains, and if we can leverage that aspect. 2. For all numbers ending at powers of 10, the element is always found after 60%th of the limit (safe assumption).-

From (10^1 to 10^17 ) Ex- For 10, number with largest chain- 9. For 10^4, number with largest chain- 6171. For 10^8, number with largest chain- 63,728,127. Refer- https://www.tcs.uj.edu.pl/documents/35126571/144955658/2020.04.09+-+Mikolaj+Twarog+-+Callatz+Conjecture/541f4826-9c49-400d-8bef-fbf3b35919b0, page 6/22.

Instead of looping from 1 to 1 million in our case, we can start from 600,000 to 1,000,000. And combining it with map method we can see that computations reduced from 2,168,611 to 2,086,665.

Thank You.

capture.png
(43.2 kB)

capture3.png
(12.0 kB)

* Please Login or Register to Comment on or Follow discussions.

thub.nodes.view.add-new-comment