Reverse String

Question:
Write a function that takes a string as input and returns the string reversed.
(Reference: https://leetcode.com/problems/reverse-string/)

Solution:
Let's take a couple of example to check the input and expected output of the given problem.
Example 1:
Input: "johny"
Output: "ynhoj"

Example 2:
Input: ""trump"
Output: "pmurt"

Solution 1:
Using String Builder:

    public String reverseString(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        StringBuilder sb = new StringBuilder();
        int len = s.length();
        for(int i = 0; i < len; i++) {
            sb.insert(0, s.charAt(i));
        }
        
        return sb.toString();
    }

Solution 2:

Using character array:

    public String reverseString(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        char[] arr = s.toCharArray();
        for(int i = 0; i < arr.length/2; i++) {
            char c = arr[i];
            arr[i] = arr[arr.length-1-i];
            arr[arr.length-1-i] = c;
        }
        
        return String.valueOf(arr);
    }

Please do let me know your comments about this blog post.

Thanks. Happy Coding :)

Maximum Depth of Binary Tree

Question:
Given a binary tree, find its maximum depth.
(Reference: https://leetcode.com/problems/maximum-depth-of-binary-tree/)

Solution:
The maximum depth of a binary tree is defines as the number of nodes along the longest path from the root node down to the farthest leaf node. Let us take an example and try to understand what does the maximum depth means.

In the above image we can see that the root Node (10) has two child nodes (5 and 20) and the two children have their respective sub-trees.  The maximum depth in the above binary tree is the number of nodes along the path from Node 10 to Node 16 as Node 10 is the root node and Node 6 is the farthest leaf Node which is available in the tree. Thus the depth is 5.

Like most of binary tree problems, our approach to solve this problem will be recursive. The challenge in this problem is to find the farthest node and in the process of finding the farthest leaf node we will calculate the maximum depth. The above shown binary tree can be divided into two sub trees.

Left Sub-Tree

Right sub-tree

Th maximum depth of the binary tree depends upon the maximum depth of it's two sub trees. If we find the maximum depth of the two individual sub-trees, then we can find the maximum depth of the original sub-tree by taking the maximum depth of the two sub-trees and increment it by one. The code for this algorithm is as follows:

1 2 3 4 5

public int maxDepth(TreeNode root) { if(null==root) return 0; return 1 + (Math.max(maxDepth(root.left), maxDepth(root.right))); }

Please do let me know your comments about this blog post.

Thanks. Happy Coding :)

Add Digits

Question:
Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
(Reference: https://leetcode.com/problems/add-digits/)

Solution:
Let's take a couple of example to check the input and expected output of the given problem.
Example 1:
Input:  267
Step 1: 2+6+7 = 15
Step 2: 1+5 = 6 (Expected output as this number has single digit)

Example 2:
Input: 7713
Step 1: 7+7+1+4 = 19
Step 2: 1+ 9 = 10
Step 3: 1+0 = 1 (Expected output as this number has only 1 digit)

By looking at the above examples the first solution that comes to mind is that we can take the input number and find the sum of individual digits by using recursion (or iteration). If the result is not a single digit code we ill process the result again and keep doing it until it returns a single digits. This methods is correct and works for all the valid inputs. The code for this algorithm can be writtes as follows:

1 2 3 4 5 6 7 8 9 10 11 12

public int addDigits(int num) { while(num/10>0){ num = sumDigits(num); } return num; } public int sumDigits(int n){ if(n==0) return 0; return (n%10) + sumDigits(n/10); }

Can we find anything better than the above solution. Let's take a couple of more example and see if we can deduce some pattern for the result:
Example 3:
Input:  10
Step 1: 1+0  = 1 (Expected output)

Example 4:
Input:  11
Step 1: 1+1 = 2 (Expected output)

Example 5:
Input:  12
Step 1: 1+2 = 3 (Expected output)


Example 6:
Input:  18
Step 1: 1+8 = 9 (Expected output)

Arguments: In mathematics we have learnt that any number that is divisible by 9, the sum of the digits in the number is also divisible by 9. Also, here we know that the result of the problem is an integer lying in the range [0,9] .

From the above arguments and samples, we can see that the result depends on the divisibility of a number by 9. The code can be written as follows:

1 2 3 4 5 6 7 8

public int addDigits(int num) { if(num<10) return num; else if(num%9 ==0) return 9; else return num%9; }

Please do let me know your comments about this blog post.

Thanks. Happy Coding :)

Nim Game

Question:
You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones. Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap. (Reference: https://leetcode.com/problems/nim-game/ )

Solution:
One of the best ways to derive a solution is by finding the cases when the person who is removing the stones (1, 2 or 3) can be confident of winning the game. We will analyse some cases below and see what happens when I am the taking the first turn to remove the stones.

case 1:
Number of stones - 1, 2 or 3
Analysis - Since, I am allowed to remove a maximum of 3 stones, I will win this case.

case 2:
Number of stones - 4
Analysis - If I remove 1, the opposition removes rest 3 and wins the game .
                 If I remove 2, the opposition removes rest 2 and wins the game.
                 If I remove 3, the opposition removes the remaining 1 stone and wins the game.
                 Thus, if the number of initial stones are 4 I will lose the game. We can also conclude that whoever has 4 stones in their turn loses the game.

case 3:
Number of stones - 5
Analysis: If I remove 1, the opposition gets 4 and thus he loses and I win.

case 4:
Number of stones - 6
Analysis: If I remove 2, the opposition gets 4 and thus he loses and I win.

case 5:
Number of stones - 7
Analysis: If I remove 3, the opposition gets 4 and thus he loses and I win.

case 6:
Number of stones - 8
Analysis: If I remove 1, the opposition gets 7 stones and wins the game .
                 If I remove 2, the opposition gets 6 stones and wins the game.
                 If I remove 3, the opposition gets 5 stones and wins the game.
                 Thus, if the number of initial stones are 8 I will lose the game. We can also conclude that whoever has 8 stones in their turn loses the game.

From the above cases we see that if the number of stones during my turn is a multiple of 4 I will lose the game. Thus the code we will write is:

1 2 3

public boolean canWinNim(int n) { return !(n%4 == 0); }

Please do let me know your comments about this blog post.

Thanks. Happy Coding :)