Cacher is the code snippet organizer for pro developers

>> from leetcode https://leetcode.com/problems/power-of-three/#/hints
>>>> Recursive solution :

public class Solution {
    public boolean isPowerOfThree(int n) {
        
        if (n == 1) {
            return true;
        } 
        
        if (n % 3 != 0 || n == 0) {
            return false;
        } 
        
        return isPowerOfThree(n /3);
    }
}


>>>> Non-recursive solution :

public class Solution {
    public boolean isPowerOfThree(int n) {
        if (n < 1) {
            return false;
        }

        while (n % 3 == 0) {
            n /= 3;
        }

        return n == 1;
    }
}

private void inorder(TreeNode root) {
        if (root == null) 
           return;
           
        inorder(root.left);
        System.out.println(root.val);
        inorder(root.right);
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
  public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
      
    if (t1 == null && t2 == null) {
        return null;
    }
    
    int val = (t1 == null ? 0 : t1.val) + (t2 == null ? 0 : t2.val);
    TreeNode newN = new TreeNode(val);
    
    newN.left = mergeTrees(t1 == null ? null : t1.left,t2 == null ? null : t2.left);
    newN.right = mergeTrees(t1 == null ? null : t1.right,t2 == null ? null : t2.right);
    
    return newN;
      
  }
    
}




Complexity Analysis

Time complexity : O(m). A total of m nodes need to be traversed. Here, m represents the minimum(?????) number of nodes from the two given trees.

Space complexity : O(m). The depth of the recursion tree can go upto m in the case of a skewed tree. In average case, depth will be O(logm).

Source - topcoder

Problem statement - Is it possible to get from the ‘S’ to the ‘E’ without passing through any ‘*’ characters in the following maze-image.md file?

>>>>Flaw in the following code:

function isMazeSolveable(maze[][])
{
    declare variables x,y,startX,startY
    startX=-1
    startY=-1

    // Look through grid to find our starting point
    for each x from A to H
    {
        for each y from 1 to 8
        {
            if maze[x][y]=='S' then 
            {
                startX=x
                startY=y
            }
        }
    }

    // If we didn't find starting point, maze isn't solveable
    if startX==-1 then return false  

    // If we did find starting point, start exploring from that point
    return exploreMaze(maze[][],startX,startY)
}


function exploreMaze(maze[][],x,y)
{
    // If the current position is off the grid, then
    // we can't keep going on this path
    if y>8 or y<1 or x<'A' or x>'H' then return false

    // If the current position is a '*', then we
    // can't continue down this path
    if maze[x][y]=='*' then return false

    // If the current position is an 'E', then 
    // we're at the end, so the maze is solveable.
    if maze[x][y]=='E' then return true

    // Otherwise, keep exploring by trying each possible
    // next decision from this point.  If any of the options
    // allow us to solve the maze, then return true.  We don't
    // have to worry about going off the grid or through a wall - 
    // we can trust our recursive call to handle those possibilities
    // correctly.
    if exploreMaze(maze,x,y-1) then return true  // search up
    if exploreMaze(maze,x,y+1) then return true  // search down
    if exploreMaze(maze,x-1,y) then return true  // search left
    if exploreMaze(maze,x+1,y) then return true  // search right

    // None of the options worked, so we can't solve the maze
    // using this path.
    return false
}

The flaw : If you’re keen eyed, you likely noticed a flaw in our code above. Consider what happens when we’re exploring from our initial position of B3. From B3, we’ll try going up first, leading us to explore B2. From there, we’ll try up again and go to B1. B1 won’t work (there’s a ‘*’ there), so that will return false and we’ll be back considering B2. Since up didn’t work, we’ll try down, and thus we’ll consider B3. And from B3, we’ll consider B2 again. This will continue on until we error out: there’s an infinite cycle.

>>> Rule of recursion : we need to make sure the problem we’re considering is somehow getting smaller or simpler with each recursive call.
As the number of places we’ve considered grows, the problem gets simpler and simpler because each decision will have less valid options.


>>> Solution to remove the flaw in the code : A good solution would be to pass around another 2 dimensional array of true/false values that would contain a “true” for each grid cell we’ve already been to. A quicker-and-dirtier way would be to change maze itself, replacing the current position with a ‘*’ just before we make any recursive calls. 

>> A function is said to be recursive if it calls itself.
>> Where to use recursion - Graph, maze

>> return statement from a base case will return to the recursion call, and recursion call return statement will return the FINAL solution to the calling function.

function fib(n)
{
    if(n<1)
      return 0
      
    if(n==1)
      return 1
      
    return fib(n-2) + fib(n-1)
}

>>>> if you find a recursive solution for a problem, but find that the solution runs too slowly, then the solution is often memoization.


function fib(n)
{
    declare variable i,memo[n]
    
    for each i from 0 to n
    {
        memo[i]=-1
    }
    memo[0]=0
    memo[1]=1

    return calcFibonacci(n,memo)
}

function calcFibonacci(n,memo)
{
    // If we've got the answer in our memo, no need to recalculate
    if memo[n]!=-1 
       return memo[n]

    // Otherwise, calculate the answer and store it in memo    
    memo[n] = calcFibonacci(n-2,memo) + calcFibonacci(n-1,memo)

    // We still need to return the answer we calculated
    return memo[n]
}

>>>> Recursive solution :

public static long factorial(int n) { 
    if (n == 1) 
      return 1; 
      
    return n * factorial(n-1); 
} 

>>> source - leetcode : 258. Add Digits
https://leetcode.com/problems/add-digits/#/description


public class Solution {
   public  int addDigits(int num) {
        int ans = num;

        if (num / 10 == 0) {
            return num;
        }else {

            while (ans / 10 != 0){
                ans = getAns(ans);
            }
        }

        return ans;
    }

    public  int getAns(int num){

        if (num / 10 == 0) {
            return num;
        }

        return num % 10 + getAns(num / 10);
    }    

}