Count possible ways to construct buildings - GeeksforGeeks

Count possible ways to construct buildings - GeeksforGeeks
Given an input number of sections and each section has 2 plots on either sides of the road. Find all possible ways to construct buildings in the plots such that there is a space between any 2 buildings.
N = 3
Output = 25
3 sections, which means possible ways for one side are
BSS, BSB, SSS, SBS, SSB where B represents a building
and S represents an empty space
Total possible ways are 25, because a way to place on
one side can correspond to any of 5 ways on other side.

We can simplify the problem to first calculate for one side only. If we know the result for one side, we can always do square of the result and get result for two sides.

A new building can be placed on a section if section just before it has space. A space can be placed anywhere (it doesn’t matter whether the previous section has a building or not).

Let countB(i) be count of possible ways with i sections
              ending with a building.
    countS(i) be count of possible ways with i sections
              ending with a space.

// A space can be added after a building or after a space.
countS(N) = countB(N-1) + countS(N-1)

// A building can only be added after a space.
countB[N] = countS(N-1)

// Result for one side is sum of the above two counts.
result1(N) = countS(N) + countB(N)

// Result for two sides is square of result1(N)
result2(N) = result1(N) * result1(N) 

int countWays(int N)

{

    // Base case

    if (N == 1)

        return 4;  // 2 for one side and 4 for two sides

 

    // countB is count of ways with a building at the end

    // countS is count of ways with a space at the end

    // prev_countB and prev_countS are previous values of

    // countB and countS respectively.

 

    // Initialize countB and countS for one side

    int countB=1, countS=1, prev_countB, prev_countS;

 

    // Use the above recursive formula for calculating

    // countB and countS using previous values

    for (int i=2; i<=N; i++)

    {

        prev_countB = countB;

        prev_countS = countS;

 

        countS = prev_countB + prev_countS;

        countB = prev_countS;

    }

 

    // Result for one side is sum of ways ending with building

    // and ending with space

    int result = countS + countB;

 

    // Result for 2 sides is square of result for one side

    return (result*result);

}

Optimized Solution:
Note that the above solution can be further optimized. If we take closer look at the results, for different values, we can notice that the results for two sides are squares of Fibonacci Numbers.

N = 1, result = 4 [result for one side = 2]
In general, we can say

  result(N) = fib(N+2)2
 
  fib(N) is a function that returns N'th
         Fibonacci Number.
 
Therefore, we can use O(LogN) implementation of Fibonacci Numbers to find number of ways in O(logN) time.

SImilar as: Count number of binary strings without consecutive 1's - GeeksforGeeks
Given a positive integer N, count all possible distinct binary strings of length N such that there are no consecutive 1's.
Let a[i] be the number of binary strings of length i which do not contain any two consecutive 1’s and which end in 0. Similarly, let b[i] be the number of such strings which end in 1.
We can append either 0 or 1 to a string ending in 0, but we can only append 0 to a string ending in 1. This yields the recurrence relation:
a[i] = a[i - 1] + b[i - 1]
b[i] = a[i - 1]
Read full article from Count possible ways to construct buildings - GeeksforGeeks

Data Structures and Algorithm: Find maximum and minimum

Data Structures and Algorithm: Find maximum and minimum

Given an array of integers, find the maximum and minimum of the array.

If rather than comparing each number with max and min, we can first compare the numbers in pair with each other. Then compare the larger number with max and compare the smaller number with min. in this way the number of comparison for a pair of numbers are 3. So number of comparisons are 1.5 *n.

 int i = 0;
  for (; i < arr.length / 2; i++)
  {
   int num1 = arr[i * 2];
   int num2 = arr[i * 2 + 1];
   if (arr[i * 2] >= arr[i * 2 + 1])
   {
    if (num1 > max)
     max = num1;
    if (num2 < min)
     min = num2;
   }
   else
   {
    if (num2 > max)
     max = num2;
    if (num1 < min)
     min = num1;
   }
  }
  if (i * 2 < arr.length)
  {
   int num = arr[i * 2];
   if (num > max)
    max = num;
   if (num < min)
    min = num;
  }

Divide and  methodconquer

In this approach we are dividing the list in two parts, each part is recursively providing the min and max of that part and then two min max are compared to decide the ultimate min and max. Recursively when the array is reduced to only a single element then the element itself become min and max.

http://www.fgdsb.com/2015/01/03/max-and-min/
http://somnathkayal.blogspot.in/2012/08/finding-maximum-and-minimum-using.html

  T(n) = 2T(n/2) + 2

           = 2(2T(n/4) + 2) + 2

           = 4T(n/4) + 4 + 2

           .

           .

           .

           = 2^k-1 T(2) + ∑(1≤i≤k-1) 2^k

           = 2^{k-1 +} 2^k – 2

           = 3n/2 – 2 = O(n)

Note that 3n/2 – 2 is the best, average, worst case number of comparison when n is a power of two.

Read full article from Data Structures and Algorithm: Find maximum and minimum

Segregate Even and Odd numbers - GeeksforGeeks

Segregate Even and Odd numbers - GeeksforGeeks
Given an array A[], write a function that segregates even and odd numbers. The functions should put all even numbers first, and then odd numbers.

The problem is very similar to our old post Segregate 0s and 1s in an array, and both of these problems are variation of famous Dutch national flag problem.

Algorithm: segregateEvenOdd()
1) Initialize two index variables left and right:  
            left = 0,  right = size -1 
2) Keep incrementing left index until we see an odd number.
3) Keep decrementing right index until we see an even number.
4) If lef < right then swap arr[left] and arr[right]

oid segregateEvenOdd(int arr[], int size)

{

  /* Initialize left and right indexes */

  int left = 0, right = size-1;

  while(left < right)

  {

     /* Increment left index while we see 0 at left */

     while(arr[left]%2 == 0 && left < right)

        left++;

 

     /* Decrement right index while we see 1 at right */

     while(arr[right]%2 == 1 && left < right)

        right--;

 

     if(left < right)

     {

       /* Swap arr[left] and arr[right]*/

       swap(&arr[left], &arr[right]);

       left++;

       right--;

     }

  }

}

Read full article from Segregate Even and Odd numbers - GeeksforGeeks