Calculating Fibonacci series

Formal Definition : The Fibonacci series is described recursively as:
                                       f(0) = 0, f(1) = 1
                                       f(n) = f(n-2) + f(n-1) if n>1
giving 0,1,1,2,3,5,8,13,21,34,55,89,144,....

Naive method : Just go on calculating blindly. There is a simple recursive solution. As the definition itself is recursive, to think it as it is much simpler.

Pseudo code:

Fib(n):
    if n < 2:
        return n
    else :
        return Fib(n-1) + Fib(n-2)

Time Complexity : O(Fib(n))
Space Complexity : O(Fib(n)) (may overflow recursion depth in large numbers)

That's all. It is the most simple way to do it.
Explanation:

This is how the recursion calls look like. But observe that Fib(2) , Fib(3) , Fib(1) , Fib(0) are called multiple times resulting into redundancy.
To over come this problem we can store the values that were calculated and use them later.

pseudo code:

Fib(n):
    if db[n] != NULL:
        return db[n]
    else:
        db[n] = Fib(n-1) + Fib(n-2)
        return db[n]

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

Explanation:

Now the Fib(1) is not required for left Fib(2) and Fib(4) does not calls Fib(3) and Fib(2) as they are already calculated. Thus reducing precious operation. The naive method uses 13 calls for calculating Fib(5) (or 8 terminal calls i.e. the leaves of the tree) which are themselves Fibonacci numbers but the optimised method just used 5 steps and got Fib(i) : i belongs to [1,5].

You may not believe but this was a simple example of Dynamic Programming paradigm. This involves brute force with some sense.

another implementation (Non-recursive) would be:

Fib(n):

    db = [0,1]
    for i in [2..n]:
        db[i] = db[i-1] + db[i-2]
    return db[n]

Simple enough to understand. :D

The actual Problem arises when n also rises to lengths such as n = 10^16. now how would you get the term. Doing a Linear time solution would not suffice. A general notion is that if the limit rises above 10^6 we generally think of a log(N) solution.So we dig in a little bit.

Pop fact: Did you know about an irrational number phi or the golden ratio



This is to do with some ratio mumbo-jumbo... But we find an interesting property here with Fibonacci numbers.

These relations can be used to prove almost all the identities that involve Fibonacci numbers.

But for our concern we were calculating all the numbers previous to our required number. How about if we could just find the required number and save lots of operations. Let us talk about a simple matrix.

Now we can see that F(n) A = F(n+1) .  and A^2 = F(2) taking terms from 1,2,3,5,8,13,..

thus we can conclude that F(n) = A^n. This is again a linear time operation, but we need faster. Remember the previous post on Binary Exponentiation. That will help on logarithmic complexity.

Pseudo Code:

Fib(n):
    A = [[1,1],[1,0]]
    F = [[1,0],[0,1]]
    while n>0:
        if n%2==1:
            F = F*A
        A = A*A
        n = n/2
    return F[0][0]

Python Implementation :

def mul(x,y):
    lst = [[0,0],[0,0]]
    lst[0][0] = x[0][0]*y[0][0] + x[0][1]*y[1][0]
    lst[0][1] = x[0][0]*y[0][1] + x[0][1]*y[1][1]
    lst[1][0] = x[1][0]*y[0][0] + x[1][1]*y[1][0]
    lst[1][1] = x[1][0]*y[0][1] + x[1][1]*y[1][1]
    return lst
def Fib(n):
    a = [[1,0],[0,1]]
    d = [[1,1],[1,0]]
    while n:
        if n&1:
            a = mul(a, d)
        d = mul(d,d)
        n >>= 1
    return a[0][0]

Most of the competitive programming questions are logic based and not on number crunching. So you would not find normally to get Fib(10^18) but you may find Fib(10^18) (mod N). Go ahead and just add a modulo operator in the mul(x,y) function to each multiplication and we are done.

Time Complexity : O(log(N))

Space Complexity : O(1)

  

Calculating A^B mod N

Binary Exponentiation

We frequently need to calculate terms like a^b and most programming contests have a need to find modulo of the above exponent i.e. (a^b)%Mod_value.  Now there is a Brute force and a simple and a clever method to find that.

suppose for integers A, q, B, r we can have A = qB + r

now the modulo is the simple manipulation of the above property.

we can rewrite the above as A = r (mod q) or conversely we can say that 

A = r (mod Mod_value ) is an expression equivalent to A = q*Mod_value + r where q can be any integer.

Some properties of the modulo 

1. if a = r1 (mod q)  and  b = r2 (mod q) then :

             a + b = (r1 + r2) (mod q) and same goes for subtraction,

             a*b = (r1 * r2) (mod q)

the above can be proved easily by taking the expanded form of the expression i.e a = qz + r1, b = qw + r2

2. Now the above multiplication property can be used to get the exponent part which we are interested in.

suppose we have a = b , then we r1 = r2,  so we have a^2 = r^2 (mod q)

we could also get by multiplying a = r(mod q)

 = a^2 * a = r^2 * r (mod q) 

 = a^3 = r^3 (mod q)

lets find a^5 (mod q). we could surely use five times multiplication of a = r (mod q), taking 5 steps or we could use a = r (mod q) and a^4 = r^4 (mod q), we can get a^4 in 2 steps or lg(4) steps and a total of 3 steps to get the answer. (Observe 5 = 101 in base 2 and the no of steps is the number of bits or more precisely { lg(N) } where {.} is the largest integer function), (Similarly we can get 2^K th power of a in K steps getting a logarithmic complexity.)

Note that we used a^1 and a^4 exponents, and the places with 1's in 5's binary representation is also 1 and 4. 

Lets jump into the algorithm

 Now we just use the values that have 1 in their bit positions. 

 r = (127 x 17 x 289 x 917 x 44 x 66 x 842 ) (mod 1007) 

 r = 1399034822210256 (mod 1107)

 r = 867

which is the answer we need.

Why did we just take the bits with 1 in it ?

5223 = 1010001100111

thus we just need 2^0, 2^1, 2^2, 2^5, 2^6, 2^10, 2^12. just add them up and we get 5223

using the property we use a^(2^0) * (a^(2^1) * (a^(2^2)) * (a^(2^5)) * .. * (a^(2^10) * a(^(2^12))

which is equal to a^(1+2+4+32+64+1024+4096) = a^(5223) which is what we require.

pseudo Code:

function(a, n, mod_value):
       ans = 1
       d = a
       repeat :
              if (n%2 == 1):
                     ans = (ans * d)%mod_value //use the value with bit 1
              d = (d*d)%mod_value //keep squaring
              n = n/2
       return ans

Python Implementation:

pow_mod(a, n, mod_value):
        ans = 1, d = n
        while n:
                if b&1:
                        ans = (ans * d)%mod_value
                d = (d*d)%mod_value
                b = b>>1
        return ans

C++ Function

define LL long long

LL pow_mod(LL a , LL n, LL mod_value)

{
LL ans = 1, d = n;
  while (n)   
  {
     if(n&1)
          ans = (ans * d)%mod_value;
      d = (d*d)%mod_value;
    n = n>>1;
  }
    return ans;
}

Time Complexity : O(Log(N))
Space Complexity : O(1)

Maximum Sum SubArray Problem

Maximum Subarray is well and standard algorithm.

Problem statement : You are given an array of N numbers. You need to Find a subarray such that the sum of the elements is maximum possible.

Naive solution : Find all the possible subarrays of length [0..N] and find their respective sums to get the largest array. Obviously the calculation results to O(N^2) complexity.

Pseudo Code:

function (array[]):
        declare sum[N][N] <- Initialise with 0
        sum[0][0] = a[0]
        //Using Zero-Indexed array
         for i in [1..N-1]:
                 sum[0][i] = a[i] + sum[0][i-1]

         for i in [1..N-1]:
                 for j in [0..i]:
                         sum[i][j] = array[k]

         for k in [i+1..N-1]:
                 sum[i][k] = array[i][k-1] + a[k]
         max_sum = 0
         posx = -1
         posy = -1

         for i in [0..N-1]:
                 for j in [0..N-1]:
                         if max_sum < sum[i][j]:
                                  max_sum = sum[i][j]
                                  posx = i
                                  posy = j
         print max_sum , posx, posy

C++ Implementation

//***********************************************************************

#include <bits/stdc++.h>
using namespace std;
int main()
{
 int i,j,k;
 int a[8] = {-2, -3, 4, -1, -2, 1, 5, -3}; // sample array
 int sum[9][9];
 sum[0][0] = a[0];
 for(i=1; i<8; i++)
         sum[0][i] = a[i] + sum[0][i-1];
 for(i=1; i<8; i++)
 {
          for(j=0; j<i+1; j++)
                   sum[i][j] = a[j];
          for(k=i+1; k<8; k++)
                   sum[i][k] = sum[i][k-1] + a[k];
 }
 //Prints the Sum Array
 for(i=0; i<8; printf("\n"),i++)
          for(j=0; j<8; j++)
                   printf("%d ", sum[i][j]);


 int max_sum=0, posx=-1, posy=-1;
 for(i=0; i<8; i++)
 {
          for(j=0; j<8; j++)
          {
                  if(max_sum < sum[i][j])

                 {
                           max_sum = sum[i][j];
                           posx = i;
                           posy = j;
                 }
          }
 }
 printf("%d %d %d\n",max_sum, posx, posy );
 return 0;
}
//***********************************************************************

This is a simple brute force that computes the sum array for the array [-2, -3, 4, -1, -2, 1, 5, -3] we get the sum array as

-2 -5 -1 -2 -4 -3  2 -1

-2 -3  1  0 -2 -1  4  1

-2 -3  4  3  1  2  7  4

-2 -3  4 -1 -3 -2  3  0

-2 -3  4 -1 -2 -1  4  1

-2 -3  4 -1 -2  1  6  3

-2 -3  4 -1 -2  1  5  2

-2 -3  4 -1 -2  1  5 -3

Note that the first one is the cumulative array. The second starts at a[1] and continues a cumulative array from pos 1 (zero based index) to end. Similarly the third and the fourth. This works because we want to take the sum of m elements starting from [0..N] eg:  

sum00 = -2 taking just the first element  
sum01 = -2+-3 taking 2 elements  
sum02 = -2 + -3 + 4 taking 3 elements

sum11 = -3 taking 1 elements from pos 1  
sum12 = -3 + -4 taking 2 elements from pos 1

Similarly for others... thus we have the sum of all contiguous blocks starting from 0 to N-1 Now we just need to select the sum. Also, just check out that the array was not random. Each position is the range sum for Sum[i][j] : Summation from a[i] to a[j] ,thus for the index we just need to print the indexes where the maximum was found. Time Complexity : O(N^2) Space Complexity : O(N^2)

Dynamic Programming Solution

The brute force method works but is not sufficient. In this method we use a Simple logic: Suppose we have a set MAX = {} containing the subarray and S[] storing the answer to the above problem upto index 'i' of A[] using the array A = [-2, -3, 4, -1, -2, 1, 5, -3] if S[upto i-1] + A[i] < A[i] then the solution is not optimum as we can get a subset that has sum greater than our best set till 'i'. MAX = {A[i]} now the new subset if S[upto i-1] + A[i] > A[i] then we get a subset with sum greater than the best sum subset till 'i'.

 Pseudo Code:

 dp = [max(A[i], 0] //Considering the choice of Null set or choosing the
      // first element
 for i in [1..N-1]:
         if A[i] > A[i-1] + dp[i-1]:
                   dp[i] = dp[i-1] + a[i]
   // Adding the element to the Set
         else:
                   dp[i] = a[i];
   // Reset the Sum array to new set
 max_Sum = maximum_Element in dp[]

Python Implementation:

#***********************************************************************
def max_subarray(lst):
        dp = []
        dp.append(max(lst[0],0))
        st = [0]
        end = [0]
        for i in range(1, len(lst)):
                if (lst[i] > lst[i-1]+dp[i-1]):
                        st.append(i)
                        end.append(0)
                else:
                        st.append(st[i-1])
                        end.append(end[i-1]+1)
                dp.append(max(lst[i], lst[i]+dp[i-1]))
        max_sum = max(dp)
        a = dp.index(max_sum)
        rt = (st[a], st[a]+end[a], max_sum)
        return rt
lst = map(int, raw_input().split(' '))
print max_subarray(lst)
#**********************************************************************

The above code keeps the track when the Set resets and the number of elements added getting the length of the set st[] = starting point of the set end[] = length of the set

  C++ Implementation

//*********************************************************************
#include <bits/stdc++.h>
using namespace std;
int main()
{
 int i,j,k,n,st,ed;
 scanf("%d", &n);
 int dp[n+1], mx;
 int a[1001];
 for(i=0; i<n; i++)
         scanf("%d", &a[i]);
 dp[0] = max(0, a[0]);
 st = 0; ed = 0;
 for(i=1; i<n; i++)

 {
         if(a[i] < dp[i-1]+a[i])
                 dp[i] = dp[i-1]+a[i];
         else
                 dp[i] = a[i] ,st = i;
 }

 mx = -1;
 for(i=0; i<n;i++)
         if(mx<dp[i])
                 mx = dp[i], ed = i;

 printf("Maximum Sum %d\n", mx);
 printf("Maximum Sum Subarray A[%d : %d]\n",st+1, ed+1);

 return 0;

}

//*********************************************************************

Time Complexity : O(n)
 Space Complexity : O(n) virtually no extra space

binary indexed tree code

Here I am writing  c/c++ code for implementing simple binary index tree (BIT). I will upload the explanation after some time.
A request from all the blog reader please suggest me the topics on which i can upload the tutorials.
mail me @ :- raj.nishant360@gmail.com

// © NISHANT RAJ
// source :-> http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
// created :-> 23 / 03 / 2014 ; 04 : 36
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <map>
#include <string>
#include <cstring>
#include <sstream>
#include <fstream>
#include <climits>
#include <ctime>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int a[100000],cum[100000],res[100000],maxval;
int get_value(int idx) // reading cumulative frequency of index idx O(log(maxval 
{
   int sum=0;
   while(idx>0)
  {
     sum+=res[idx];
     idx-=(idx & -idx);
  }
  return sum;
}
void update(int idx,int val)// updating frequency range 
{
   while(idx<=maxval)
  {
     res[idx]+=val;
     idx+=(idx & -idx);
  }
}
int main()
{
   int t;
   cin>>t;
   while(t--)
  {
    int j,idx,val,k;
    cin>>maxval;
    cum[0]=0;
    for(int i=1;i<=maxval;i++)
   {
     cin>>a[i];   //actual frequency given by user.
   cum[i]+=a[i]+cum[i-1];// cumulative frequency array.
  }
  for(int i=1;i<=maxval;i++)
  {
   j= i + 1 - (1<<(__lg(i & -i)));// __lg(num) ->calculates                                                        //the position of MSB
   res[i]=cum[i] - cum[j-1];// calcualting frequency of particular range
 }
  int qury;
  cin>>qury;
  string in,upd="U",find="S";
  while(qury--)
  {
   cin>>in;
   if(in==upd)
   {
    cin>>idx>>val;
    update(idx,val); // takes O(log(maxval)) time.
   }
   if(in==find)
   {
    cin>>j>>k;   // takes 2*O(log(maxval)) time.
    cout<<(get_value(k) - get_value(j-1))<<endl;
   }
  }
 }
 return 0;
}