Coding Recipies: October 2014

4 Oct 2014

Algo #116: Square Root (using Newton Ralpson Method)

Problem Statement:
Calculate the square root of a number using Newton Raphson's Method .

Download Source Code
Solution:

Newton Raphson's method is used for finding successive better approximate roots of a functions, at every successive iteration , the result tends towards the root of the function.

In this technique we use the logic of approximation by calculating the tangent line of the function f(x), derivative of the function f(x) represents the tangent line to the function curve f(x).

Geometrical Interpretation:
Let r be a root of f(x), that is f(r) =0. Assume that $f'(r) \neq 0$ . Let x₁ be a number close to r (which may be obtained by looking at the graph of f(x)). The tangent line to the graph of f(x) at (x₁,f(x₁)) has x₂ as its x-intercept

Fig1: Representing f(x) and f '(x) and r being the root f(r)=0

From the above picture, we see that x₂ is getting closer to r. Successive iterations will lead to results closer to 'r'. x1 was the intial guess which lead to a better result x2.

Now,

here Er represent the percentage error.

Lets calculate the square root of 44.89,
we will assume out initial guess to be 44.89, using the formula

Now code up our logic for calculating the square root.

float squareRoot(float num)
 {
  float x1 = num,x2=0,temp=num,e=0.001f;
  do 
  {
   x1 = temp;
   x2 = 0.5f * (x1 + num/x1);
   temp=x2;
   
  }while(Math.abs(x2-x1)> e);
  
  System.out.println(num + " ----> " + x2);
  return x2;
 }

Rare Scenarios which might happen when using Newton Raphson Method:

1. If the initial estimate is not close enough to the root, the Newton Method may not converge, or may converge to the wrong root.

2. The successive estimates of the Newton Method may converge to the root too slowly, or may not converge at all.

Please comment and post your suggestions.
Happy Coding !! :)

References:
1. http://www.sosmath.com/calculus/diff/der07/der07.html
2. https://www.math.ubc.ca/~anstee/math104/104newtonmethod.pdf
3. http://www.codecogs.com/eqnedit.php
4. Wiki

Algo #115: Reverse words in a character array

Problem Statement:
Reverse Words of the String given in the form of Character array without additional space.

Fig 1

Download Source Code
Solution:

1st Approach:
Our first approach will require K-1 iterations inorder to get the desired result , where K is the number of words, in each iteration we will move the first word to the end.

Fig 2

At every iteration we will have to hold 1 word in temp memory. Since this approach requires memory equal to 1 word, we will move to our in-place approach.

Time Complexity : O(KN) , where K is number of words and N is the Size of character array.

2nd Approach :
We can divide this approach in two steps.
1. Reverse the character array completely.
2. Reverse each word in the reverse array.

Lets show this by the diagram.

Fig 3

Lets implement the above logic.

/**Reverse Words in an array
  */
 private static void reverseWords(char[] str) {
  if(str==null || str.length==0)
   return ;
  
  String temp = new String(str);
  int len = str.length, l=0,r=0;

  //Reverse the input array
  reverseArr(str, 0, str.length-1);
  
  while(r<len && str[r] == ' ') //Skip initial Spaces, if any
   r++;
  
  while(r<len)
  {
   l=r; //l hold the start character of the word
   while(r== len-2 || (r<len-1 && str[r+1] != ' ')) //Get the last character of the word in r
    r++;
      
   reverseArr(str,l,r++);

   while(r<len && str[r] == ' ') //Find the next character using r
    r++; 
  }
  System.out.println(temp +" ----> " +new String(str));
 }
 
 
 /**
  * Reverse the character array between i and j (inclusive)
  */
 private static void reverseArr(char[] s,int i, int j) {
  int len=i+(j-i)/2;  //look carefully this line, when i is not 0
  for(;i<=len;i++,j--)
   swap(s,i,j);
 }

 /**
  * Swaps the ith and jth indices
  */
 private static void swap(char[] arr,int i, int j) {
  char temp  = arr[i];
  arr[i] = arr[j];
  arr[j]=temp;
 }
 
 public static void main(String[] args) {
  String s1 = "  Coding    Recipes is Super   Cool  ";
  String s2 = "I live to code";
  String s3 = "Recursion is Recursion";
  //reverseWords1(s.toCharArray());
  reverseWords(s1.toCharArray());
  reverseWords(s2.toCharArray());
  reverseWords(s3.toCharArray());
  reverseWords("   ".toCharArray());
  reverseWords(null);
 }

Output is :

 Coding    Recipes is Super   Cool   ---->   Cool   Super is Recipes    Coding  
I live to code ----> code to live I
Recursion is Recursion ----> Recursion is Recursion

Time Complexity: O(n)
Space Complexity: O(1)

Please post your comments , queries or any suggestions.
Happy Coding !! :)

Algo #114: Rotate Array

Problem Statement:
Rotate array by K with constraints
Time Complexity: O(n)
Space Complexity : O(1)

For K=3

Notice that 1 is poped out and pushed at the back of 10 , similar thing happened for 2 and 3 as well.

Solution:

Our approach will consist of three steps.
1. Reverse (0 to K )
2. Reverse (K+1 to len-1)
3. Reverse Entire array.

Lets See this by fig.

Fig : Step wise transformation of array.

Implementation of the above approach:

/**
  * Rotate array by k
  */
  void rotate2(int[] arr, int k) {
  if(k<=0 || arr==null || arr.length==0)
   return ;
  int[] old = Arrays.copyOf(arr, arr.length);
  k--;
  
  int i=0,j=k,len=arr.length;
  for (; i <=k/2 ; i++,j--)
   swap(arr, i, j);
  
  int temp=  i + (len-i)/2;
  for (i=k+1,j= arr.length-1; i <= temp ; i++,j--)
   swap(arr, i, j);
  
  
  for (i=0,j= len-1; i "+ Arrays.toString(arr));
 }

Please post your comments and suggestions
Happy Coding !! :)

Algo #113: Inverse of a number (without division)

Problem Statement:
Calculate Inverse of number without using '/ ' operator.

Solution:
There could be multiple techniques for solving this problem but in this post i will solve this problem using Newton Raphson's Method. Refer to my earlier post on Newton Raphson for Square Roots.

Lets code up our logic.

public static void main(String[] args) {

  inverse(0.2f);
  inverse(0.3f);
  inverse(3.3f);
 }

 private static float inverse(float num) {
  float x1= num,x2=0,temp=num,e=0.001f;
  do 
  {
   x1 = temp;
   x2 = x1 * (2 - num*x1);
   temp=x2;
  }while(Math.abs(x2-x1)> e);
  
  System.out.println(num + " ----> " + x2);
  return x2;
 }

PS: The choice of the initial value may or may not converge the function and thus may not give correct result which is drawback of Newton Raphson's method

References:
1. http://www.sosmath.com/calculus/diff/der07/der07.html
2. https://www.math.ubc.ca/~anstee/math104/104newtonmethod.pdf
3. http://www.codecogs.com/eqnedit.php
4. Wiki

Algo #112: Number to Words

Problem Statement:
Given a number convert it to words.

e.g. 1327 as One thousand three hundred twenty seven

Solution:

Implementation:

/**
 * Convert a given number to a word
 * @author PRATEEK
 */
public class NumberToWord {

 private static String ones[] = { " ", " one", " two", " three", " four",
   " five", " six", " seven", " eight", " Nine", " ten", " eleven",
   " twelve", " thirteen", " fourteen", "fifteen", " sixteen",
   " seventeen", " eighteen", " nineteen" };

 private static String tens[] = { " ", " ", " twenty", " thirty", " forty",
   " fifty", " sixty", "seventy", " eighty", " ninety" };

 
 private static void word(StringBuilder result , int val, String place) {
  if (val > 19)
   result.append(tens[val / 10] + " " + ones[val % 10]);
  else
   result.append(ones[val]);
  if (val > 0)
   result.append(place);
 }

 public static String convertToWord(int num)
 {
  if (num <= 0)
   return "";
  
  StringBuilder result = new StringBuilder("");
  word(result, num / 1000000000, " Hundred");
  word(result, (num / 10000000) % 100, " crore");
  word(result ,(num / 100000) % 100, " lakh");
  word(result, (num / 1000) % 100, " thousand");
  word(result,(num / 100) % 10, " hundred");
  word(result,num % 100, " ");
  System.out.println(num + " --> "+result.toString().trim());
  return result.toString().trim();
 }
 
 public static void main(String[] args) {
  convertToWord(117);
  convertToWord(1327);
 }
}

Please post your comments and suggestions.
Happy Coding !! :)

2 Oct 2014

Algo #111: Nth Fibbonacci Number in log(n) complexity

Problem Statement:
Find the Nth Fibbonaci number in log(n) complexity.

Download Source Code
Solution:

The recurrence Relation for the Fibonacci series given by
f(n) = f(n-1) + f(n-2)

We can code up the Recursive and DP (Dynamic programming) Solution for the above equation, these techniques gives us a exponential complexity and O(n) complexity respectively.

Recursive Solution:

int fib1(int n) {
   if(n<=1)
    return n;
   return fib1(n-1) + fib(n-2);
  }

Time Complexity: Exponential

Dynamic Programming Approach:

int fib2(int n)
 {
  if(n==0)
   return 0;
  int old1=0 , old2=1 , curr,i=2;
  for(;i<=n;i++)
  {
   curr = old1 + old2;
   old1= old2;
   old2 = curr;
  }
  return old2;
 }

Time Complexity: O(n)

Now we will discuss an approach which is of the order of O(n) and is called as Matrix Exponentiation.

Matrix Exponentiation is used to find the nth element of a series which can be represented in the form of a recurrence equation.

Now our recurrence equation can be represented in the form of Matrix multiplication

f(n) = f(n-1) + f(n-2)

which can be represented as

| f(n)  |  =  I x  | f(n-1) |
| f(n-1)|          | f(n-2) |

where I = | a  b |
          | c  d |

Expanding and solving, we get

f(n) = a*f(n-1) + b*f(n-2)
and 
f(n-1) = c*f(n-1) + d*f(n-2)

solving we get,

I = | a  b |  =  | 1  1 |
    | c  d |     | 1  0 |

Our goal is to find [ f(n) f(n-1)] , from bottom to top by recursive doubling (Matrix exponentiation)

To get 
| f(n)   | = I x | f(n-1) |  , where I = | 1 1 |
| f(n-1) |       | f(n-2) |              | 1 0 |

We start with 

| f(2) | =  I x | f(1) |   , where | f(1) | = | 1 |
| f(1) |        | f(0) |           | f(0) |   | 1 |
then, 
| f(3) | =  I x | f(2) | = I^2 x | f(1) |
| f(2) |        | f(1) |         | f(0) |
then
| f(4) | =  I x | f(3) | = I^3 x | f(1) |
| f(3) |        | f(2) |         | f(0) |
...
...
...
| f(n)   | =  I x | f(n-1) | = I^(n-1) x | f(1) |
| f(n-1) |        | f(n-2) |             | f(0) |

You can observe that now we are left out with calculating I^(n-1) this is where matrix exponentiation will yield its result in O(log N) time.

Lets understand logic behind recursive doubling, which reduces the computation time to O(log N)

Now lets suppose we have to calulate I^n , 
If n is odd 
             I^n = I^((n-1)/2)  * I^((n-1)/2) * I 
If n is even 
             I^n = I^(n/2) * I^(n/2)

example 
   1. n = 9 (odd)
            I^9 = I^4 * I^4 * I

   2. n=12 (even)
             I^12 = I^6 * I^6

Now lets code up our logic.

private static int[][] F = { { 1, 1 }, { 1, 0 } }; // will change , capture rsult here
private static int[][] I = { { 1, 1 }, { 1, 0 } }; //will remain fixed
 
 public static int fib(int n){
  if(n==0)
   return 0;
  power(F,n-1);
  
  return F[0][0];
 }
 
 /**
  * Calculates F to the power n
  * @param F
  * @param n
  */
 private static void power(int[][] F, int n) {
  if(n==0 || n==1)
   return;
  
  power(F,n/2);
  multiplyMatrix(F,F);
  
  if(n%2!=0)
   multiplyMatrix(F, I);
 }
 
 /**
  * Multiples Matrixes of size 2X2
  */
 public static int[][] multiplyMatrix(int[][] A, int[][] B)
 {
    int x =  A[0][0]*B[0][0] + A[0][1]*B[1][0];
    int y =  A[0][0]*B[0][1] + A[0][1]*B[1][1];
    int z =  A[1][0]*B[0][0] + A[1][1]*B[1][0];
    int w =  A[1][0]*B[0][1] + A[1][1]*B[1][1];
   
    A[0][0] = x;
    A[0][1] = y;
    A[1][0] = z;
    A[1][1] = w;
    
    return A;
 }
 
 public static void main(String[] args) {
  //1,1,2,3,5,8,13,21,34,55,89...
  int n = 8;
  System.out.println(n + "--->" + fib(n));
 }

References:
1. CodeChef
2. Wikipedia

Please comment and post your suggestions.
Happy Coding !!