Integer to Binary Using Recursion

Problem:
Get binary equivalent of a number using Recursion.
getBinary(2)       = 10
getBinary(5)       = 101
getBinary(1024) = 10000000000

Iterative implementation of this problem is quite trivial. But here it's expected to be done recursively!

Approach 1

The approach is quite simple -  Divide the decimal value by 2 and write down the remainder. Repeat this process until you can't divide anymore. 

Calculate for 13,

 13/2 = 6 and remainder = 1

 6/2   = 3 and remainder = 0

 3/2   = 1 and remainder = 1

 1/2   = 0 and remainder = 1        

To get binary, we write down the value of reminder from bottom to top. So it gives 1101. Let's apply recursive thinking to solve this problem. 

Subproblem will be dividing the number by 2 in each iteration. 

Base Case - binary of 1 is 1 (or 0 is 0) . 

Combining subproblem result might be tricky as it needs to be done in a reverse way. This can be achieved if the method is called first (and then the remainder operation is performed). This will ensure that the remainder is performed only when base case is reached.

public static String getBinary(int num) {
 if (num < 2) {
  return "" + num;
 }

 return getBinary(num / 2) + num % 2;
}

Stack Progress
getBinary(13)
    --> getBinary(13/2) + 13%2
             --> getBinary(6/2) + 6%2
                     -->getBinary(3/2) + 3%2
                             -->getBinary(1)    //base case, return 1
                     --> ""+ 1+ 1
             --> ""+1+1+0
     -->""+1+1+0+1   

Approach 2

Let's explore on another approach which uses bit manipulation to generate a binary equivalent. 

Binary of 5 is 101. Now let's see if we can get the bit values (1, 0 and 1) of the number by some bit manipulation technique. 

5 & 100 = 100   

5 & 010 = 000

5 & 001 = 001

Notice that, And operation (&) is performed with a number whose all values are 0 except leftmost position. And then that keeps on shifting to the right side. And the output will be 1 at that position if the bit value is 1 in the number (and 0 otherwise).

When you apply recursive thinking, it's quite clear that method needs another argument which will help in getting bit value at a given position. Integer in Java is 32 bit long, so that number will take the initial value of 1 << 31 (i.e. leftmost bit is 1 and rest all are 0). And when all bit positions (from MSB to LSB) are explored the recursion should stop. 

public static String getBinary2(int num, int and){
 if(and == 0){
      return "";   //if all bits are checked; just return
 }

 /**
  * If value at position is 1 in num; it will give and value
  */
 int t = (num & and) == and ? 1 : 0;
 
 return ""+ t + getBinary2(num, and >>> 1);
}

String binary = getBinary2(5, 1<<31);

//binary = 00000000000000000000000000000101

Can you try to come up with stack progress as shown for first approach?
Do post your feedback/doubts below!
---
keep coding !!!

Recursive Thinking

Usually, most of the programmers (poor ones like me :p) think iteratively to solve a problem. This works, until you get a problem which is expected to be solved recursively or even worse what if non-recursive solution is bit tricky. Take a classic example of binary tree traversal, it's a breeze if it needs to be done recursively (just few lines would do the job). You are not going to always get such commonly occurring or well known problems. What if you land to a brand new problem to be solved recursively? How you going to check if recursion can be applied or not ?

Your ability to come up with multiple solutions to a problem will be limited if you don't try to come up with recursive solution. It takes time to develop the recursive thinking, and ofcourse with lots of persistent hard work. 

Let's go through some of the fundamental aspects which can be invaluable to develop recursive thinking (cap). In this post, I will cover recursion,  rules for solving a problem recursively and finally explain the concept through couple of problems.

Recursion

Recursion is another approach to solve problems which require repetition. Problem is solved by reducing it to a smaller problem of the same kind. This process is continued until we reach to a very small problem (base case) which can be solved directly. Base condition stops the further method call. 

Let's start with a simple problem of printing all numbers between two given numbers(both inclusive).

//Java Implementation

public void print(int a, int b){

      if(a == b){

          System.out.println(a);

          return;

      }

      else{

            System.out.println(a);

            print(a+1, b);

      }

}

Above recursive algorithm reduces the problem to a smaller problem in each call (until base condition is reached). So, print(2,5) becomes print(3,5) after first call and so on until both a and b are same.

print(2,5)

   -->print(3,5)

           -->print(4,5)

                   -->print(5,5) //base case

Basic idea in recursion is to reduce problem to smaller problem of the same kind. 

Recursive Thinking

Developing recursive thinking is about your ability to ask few (important) questions for solving any problem. 

1. How can the problem be broken down to one or more subproblems (smaller problem)?
2. What is the base case?
3. Does each subproblem has a (partial) solution? How that should be combined to get final result?

You need to have answer to all questions to solve a problem. Over a period of time, this pattern becomes very obvious and smart programmers can find it quite easily. You need to practice a lot to make recursive thinking part of your (algorithmic) problem solving toolkit. 

Let's apply recursive thinking on above method, print(a,b) -

1. Problem can be broken down to smaller subproblem - Yes. Print first argument and then print all numbers between first argument + 1 and second argument. 
2. Base case - print numbers until first argument becomes second argument (i.e. a==b)
3. Does each subproblem has a solution -No. They just print the value on console so there is no intermediate answer or partial solution. 

Problems

Let's apply recursive thinking on few problems. I will use RT#1, RT#2, RT#3 to look for valid answer to the three Recursive Thinking questions:

p1: Find the length of a string

RT#1: How can this problem be divided into subproblems? So instead of finding length of complete string, can we find length of a smaller string to somehow get the full length ?

      

         length("abc") = can we find the full length if we know, length("bc")

    or, length("abc") = can we find the full length if we know, length("ab")

RT#2: Base case is something whose answer we already know. 

        length("") = 0

   or, length("a") = 1  

RT#3: Yeah subproblem has a solution. 

              length("abc") = 1 + length("bc")

         or, length("abc") = 1 + length("ab");

algorithm:

    int length(str){

           if(str.hasOneChar())

                return 1;

            else

                return 1 + length(str.substring(1));

     }  

p2: Compute power(X,n) (i.e. X^n = X*X*X.....*X, n of them)

RT#1: Quite clear, power(X, n-1) can be one of the subproblem (let's stick with this for now).

RT#2: Base case, n = 0 then power(X,n)  would be 1

RT#3: X^n = X* X^(n-1)

algorithm:

    int power(x,n){

         if(n == 0)

            return 1;

         else return x*power(x,n-1);             

     }

Complexity of above problem = O(n). Subproblem reduces the length by 1 in each call.

Above is a legitimate recursive solution, but it can be improved to a better recursive solution with complexity of O(log n).  Can we reduce size of problem to half in each recursive call (something like binary search) ?

algorithm:
    int power(x,n){

         if(n == 0)

            return 1;

         else 

              int p = power(x,n/2)

              if ( n is even ) return p*p;             

              else x*p*p;

     }

Recursive Problems:
https://github.com/raiskumar/algo-ds/tree/master/recursion

Backtracking: http://www.thegeekstuff.com/2014/12/backtracking-example/

Do post your feedback below.

---

think recursion, thank recursion !!!
keep coding !

Longest Substring Without Repeating Characters

Problem:
Given a string, find the longest substring without repeating characters.
"abcabcd"  --> "abcd"
"aaaaaa"    --> "a"
"abcad"     --> "bcad"

Solution

This problem might be trivial if there is no restriction on time complexity. But if the expected time complexity is linear then it becomes quite interesting. Let's see how we going to approach to solve it. 

Once you start moving from left to right in the given input string (one character each time), there will be a need to find if the character already exists before? 

if the character doesn't exist earlier - continue further.

if the character exists earlier - this substring (starting from a given index) could be a potential answer. 

So we need a start index which points to the beginning of the current potential answer. And another index which keeps on incrementing to find that maximum substring. 

how to check if character is already found ?

str = "abac"

Assume, startIndex = 0, currentIndex = 2

The character at currentIndex(i.e. 'a') will have to be checked if it's already there in the substring before it (i.e. "ab"). Brute force approach to check if the character exists in the substring will result in complexity O(substring.length()).

We can optimize it by using hashing mechanism, but keep in mind that hashing technique will increase the space overhead. 

Java Implementation

 public static String longestSubstringWithoutRepeatingCharars(String str) {
  if (str == null || str.length() < 2) {
   return str;
  }

  Set<Character> unique = new HashSet<>();
  int startIndex = 0, endIndex = 0;
  char ch;
  String max = " ";

  while (endIndex < str.length()) {
   ch = str.charAt(endIndex);
   if (unique.contains(ch)) {

    // check if max can be optimized
    if (str.substring(startIndex, endIndex).length() >= max
      .length()) {
     max = str.substring(startIndex, endIndex);
    }

    // reset both indexes to find the next substring
    startIndex++;
    endIndex = startIndex;

    // reset set so that it can again store all unique chars
    unique.clear();
   } else {
    endIndex++;
    unique.add(ch);
   }
  }

  // check if max can be optimized
  if (str.substring(startIndex, endIndex).length() >= max.length()) {
   max = str.substring(startIndex, endIndex);
  }
  return max;
 }

longestSubstringWithoutRepeatingCharars("abcad");

output: bcad

Reference:
http://articles.leetcode.com/2011/05/longest-substring-without-repeating-characters.html

---
keep coding !!!