# Tag Archives: algorithms

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Examples :

```Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
```

This problem was taken from Leetcode

[tabby title=”Solution”]

The solution:

### Java Script

```/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/

function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}

/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {

function doSum(a,b, carry) {
var result = {
val: 0,
carry: 0
}
var sum = a + b + carry;
if(sum > 9) {
result.val = sum - 10;
result.carry = 1;
}
else {
result.val = sum;
result.carry = 0;
}
return result;
}

var nodeA = l1;
var nodeB = l2;
var end = false;
var carry = 0;
var result = new ListNode(0, null);
var resultPointer = result;
var tmp = null;

while(nodeA != null || nodeB != null) {
var valA = nodeA == null ? 0 : nodeA.val;
var valB = nodeB == null ? 0 : nodeB.val;
var sumResult = doSum(valA, valB, carry);
carry = sumResult.carry;

resultPointer.val = sumResult.val;
resultPointer.next = new ListNode(0, null);
tmp = resultPointer;
resultPointer = resultPointer.next;

nodeA = nodeA ? nodeA.next : null;
nodeB = nodeB ? nodeB.next : null;
}

if(carry != 0) {
tmp.next.val = carry; // add carry to the val of the last node
}
else
tmp.next = null; // remove the last empty node.
return result;
};

var l1 = new ListNode(9,
new ListNode(9,
new ListNode(9,
new ListNode(9, null)
))
);

var l2 = new ListNode(9,
new ListNode(9,
new ListNode(9,
new ListNode(9,
new ListNode(9,
new ListNode(9,
new ListNode(9, null)
)))))
)

// [9,9,9] , [9,9,9,9,9]
// result: [8,9,9,0,0,1]

console.log(result);```

[tabbyending]

# Climbing stairs

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2

Explanation:

``` There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
```

Example 2:

Input: 3
Output: 3

Explanation:

``` There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
```

This problem was taken from Leetcode

[tabby title=”Solution”]

The solution:

Let’s look at the possible scenarios:

[table id=1 /]

If we look at the # of ways to climb, we clearly see that the ways to climb grows in Fibonacci sequence: `1, 2,  3,  5,  8,  13, 21`

Then all we need to do is to iterate n times (where `n`  is the number of stairs) and to find the corresponding Fibonacci number.

## Using while loop

• basically we use `temp` to store previous Fibonacci number `temp = a` , initially 1
• then we calculate the next number `a = a + b` , initially a = 0 + 1
• then we set up `b = temp` which stores the last Fibonacci number in order to be ready for the next iteration. Initially 1.

Looking at the numbers from the first iteration, it is clear that on the second one we will have:
`temp = a = 1`
`a = a + b = 1 + 1 = 2`
`b = temp = 1`

third iteration will produce:
`temp = a = 2`
`a = a + b = 2 + 1 = 3`
`b = temp = 2`
forth iteration:
`temp = a = 3`
`a = a + b = 3 + 2 = 5`
`b = temp = 3`

and so on … `a` will always return the Fibonacci number for the current `n` position.

Java Script

```/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
if( n < 4)
return n;

fibonacci = function(n) {

var a = 1, b = 0, temp, num = 1;

while(num <= n) {
temp = a;
a = a + b;
b = temp;
num ++;
}
return a;
}

return fibonacci(n);
};
```

## Using For loop

This is the easiest to comprehend:

• we create an array to store the Fibonacci numbers `var fn = [1,1]` with the first two numbers pre-set so the `for` loop could generate the next one.
• created `for` loop that picks the `fn[i - 1]` and `fn[i - 2]` numbers and generate the next one.
• pushed newly calculated Fibonacci number into an array so we could use to generate next one.
• keep looping till we reached `i < n + 1` which is the  answer.

Java Script

```/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
if( n  < 3)
return n;

var fn = [1,1];
for(var i = 2; i < n + 1; i ++) {
var nextNumber = fn[i - 1] + fn[i - 2];
fn.push(nextNumber);
}

return fn[fn.length - 1];
};```

## Third solution: Using recursive function.

Java Script

```/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
if( n < 4)
return n;

fibonacci = function(n) {
if(n < 2) {
return n;
}
var result = fibonacci(n - 1) + fibonacci(n - 2);
return result;
}

return fibonacci(n + 1);
};

```

The idea here is to call fibonacci(n) function to generate the next Fibonacci number.
For `n` < 2 the function will simply return `n` 0,1,2.
For n = 3 the function will call itself recursively asking for previous two Fibonacci numbers (2 and 1) and will calculate the next number which is the sum of the previous two, and so on.

## Optimize the recursive function to use Memoization.

Memoization is simple technique where we are storing the value of already computed parameter into a HashMap function and quickly retrieve it when we need it.

In our current example since the keys are just a numbers we could store the Fibonacci numbers in a regular array (line 9). Then we simply check if the value already is set up into `memo` array and return it or call `fibonacci` function once again.
Then we set up memo array with the next solved Fibonacci number with index `n`

Java Script

```/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
if( n < 4)
return n;

var memo = [];
fibonacci = function(n) {
if(n < 2) {
return n;
}
var a = memo[n - 1] ? memo[n - 1] : fibonacci(n - 1);
var b = memo[n - 2] ? memo[n - 2] : fibonacci(n - 2);

return memo[n] = a + b;
}

return fibonacci(n + 1);
};```

You might also want to check Fibonacci sequence generator.

[tabbyending]