Today we continue to review a coding problem.
The problem statement:
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.
for example if there are five bulbs:
Initially  [ 0, 0, 0, 0, 0]
Round 1 [ 1, 1, 1, 1, 1]
Round 2 [ 1, 0, 1, 0, 1]
Round 3 [ 1, 0, 0, 0, 1]

Round 4 [ 1, 0, 0, 1, 1]

Round 5 [ 1, 0, 0, 1, 0]

The solution:

int bulbSwitch(int n){
      return Math.sqrt(n);
}

The reasoning:
A bulb ends up on only if it is switched an odd number of times.
bulbs 1 to n has a bulb i that is switched in round  d only if d divides i.
bulb i is in a switched on state only if it has an odd number of divisors.
but divisors come in pairs except for squares and pairs returns to original state
so only squares leave a toggled state and the initial state is all off
therefore we count only the squares uptil and inclusive of the number
Thus the answer is Math.sqrt(n)

courtesy: Stefan Pochmann

We implement square root with gradient method. If y ^ 2 = x then y = x / y
And we iteratively improve the approximation
Double SqRt (int n)
{
Double g = n/2;
Double y = n/g;
While(abs (y-g) > 0.001)
{
   g = (g + n/g) /2;
   y = n / g;
}
Return y;
}

Today we continue to review a few more dynamic programming problems. We discussed coin counting problem. Let us look at a variation that involves maximum number of ways in which coins can make a sum. We assume an infinite supply of coins and we could this by backtracking.
void CoinCount(ref List<int> coins, ref List<int>change, int amount, int start, int level)
{

for (int I = start; I < amount; I++)

{

for (int j = 1; i < coins.Count() && j <= amount/coins[I]; j++)

{

for (int k = 0; k < j; k++){
       change[level+k] = coins[i];
}

if (change.sum() == amount) Console.WriteLine("{0} with {1} elements", change.ToString(),
change.Count());

if (change.sum() < amount)
      CoinCount( ref coins, ref change, n, start+1, level+j);

for(int k = 0; k <j; k++){
      change[level+k] = 0;
}
}
From all the change set printed, we can find the the total count as the answer.
Note that we cannot apply the knapsack solution to another coin counting problem earlier we cannot apply a top down greedy choice method because we don't have a criteria to decide upfront how to generate a sequence that satisfies the sum.

The dynamic programming approach builds the solution in a bottom up manner. For each of the given denominations, either the denomination is part of the solution or it isn't. If the denomination is part of the solution, then the solution sub problem shrinks the sum otherwise it shrinks the denominations. If the denomination is part of the solution, then it shrinks the sum from any one of 1 to amount/denomination occurrences. Since there are overlapping subproblems, we could do well to reuse already memoize the computations.

We now look at a different problem which is to reconstruct itinerary. Itineraries consist of source destination pairs. They belong to the same traveler so they all connect. Build the itinerary starting with JFK and in the smallest lexical order.

List<string> GetItinerary(List<Tuple<string, string>> segments)
{
 segment.sort(); // based on source airport comparator

var startItem = segments.find("JFK");
segments.Remove(startItem);

var ret = new List<string>(){startItem.Item1, startItem.Item2};
while (segments.IsEmpty() == False)
{
    startItem = segments.find(startItem.Item2);
    ret.Add(startItem.Item2);
    segments.Remove(startItem);
}
return ret;
}

Allocate minimum number of pages to students
N books
Pi pages i = 1 to N
M students
int GetMinPages(int N, int M, List<int>Pi)
{
assert (Pi.Count() == N);
if (N == 0) return 0;
if (M == 0) return INT_MAX;
min = 0;
for (int i =0; i < N/M;i++)
   int val = GetMinPages(N-i+1, M-1, Pi.Range(i+1,N-i+1)) + Pi.Range(0,i).Sum();
   if val < min
      min = val;
return min;
}

Today we review the code for unit and fractional knapsack problems. In these problems, a thief is trying to fill his bag with as much value of items  with as little weight as possible.  The solution looks like this for the unit case:
recursive  solution
/ Input:
// Values (stored in array val)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
int knapsack( int W, int[] wt, int[] val, int n)
{
if (n== 0 || W == 0)
    return 0;
if (wt[n-1] > W)
   return knapsack(W, wt, val, n-1);

return max(
                    val[n-1] + knapsack(W-wt[n-1], wt, val, n-1),
                    knapsack(W, wt, val, n -1)
                   );
}
In the fractional case, we have the following:
int fractional-knapsack( int W, int[] wt, int[] val, int n) // wt is sorted based on val[i]/w[i]
{
if (n== 0 || W == 0)
    return 0;

return max(
                    val[n-1] + fractional-knapsack(W-wj + wj -w, wt, val, n),
                    val[n-1] + fractional-knapsack(W-wj, wt, val, n -1),
                    fractional-knapsack(W, wt, val, n-1)
                   );
}
which we can further improve by leaving the dynamic programming approach and applying the top down greedy choice property
wt.sort() // based on val[i]/wt[i]
n = wt.Count()
int fractional-knapsack-greedy-recursive(int W, int[] wt, int[] val, int n)
{
if (n== 0 || W == 0)
    return 0;

// first the selection
if (wt[n-1] > W)
{
return val[n-1]/wt[n-1]*W;
}
else
{
    // then the recursion
    return val[n-1] +  fractional-knapsack-recursive(W-wt[n-1], wt, val, n -1);
}
}

Today we review longest common subsequence instead of longest increasing subsequence
The LCS is based on the optimal substructure as follows: X, Y are sequences and Z is the LCS
1. if xm = yn, then zk = xm = yn and Zk-1 is the LCS of Xm-1 and Yn-1
2. if xm <> yn, then zk <> xm implies that Z is an LCS of Xm-1 and Y.
3. if xm <> yn, then zk <> yn, implies that Z is an LCS of X and Yn-1

The length of the longest common subsequence c[i,j] is :
1. 0 if i = 0 or j = 0
2. c[i-1, j-1] + 1 if i,j > 0 and xi = yj
3. max(c[i,j-1], c[i-1, j]) if i, j  > 0 and xi != yj

LCS-Length(x, y)
m <- length(x)
n<-length(y)
for i = 1 to m
     c[i, 0] = 0
for j = 0 to n
     c[0,j] = 0
for i = 1 to m
      for j = 1 to n
            if xi == yi
               c[i,j] = c[i -1, j-1] + 1
               b[i,j] = up-left
            elseif c[i-1,j]  >= c[i, j-1]
               c[i,j] = c[i-1, j]
               b[i,j] = up
            else c[i,j] = c[i,j-1]
               b[i,j] = left
return c and b
Now the LCS can be printed with :
PRINT-LCS( b, X, i, j) // PRINT-LCS(b, X, length(X), length(Y))
if i = 0 or j = 0
     then return
if b[i,j] == up-left
     then PRINT-LCS (b, X, i-1, j-1)
             print xi
else if b[i,j] == up
           then PRINT-LCS(b,X,i-1,j)
else PRINT-LCS(b,X, i, j-1)

It can be hard to choose between longest common subsequence and longest increasing subsequence as a solution to a problem. For example, consider the box stacking problem where boxes of different l x b x h exist and we have to stack them up such that we can find the tallest tower

Previously in our earlier blog post we incorrectly referred to it as the longest common subsequence but it is in fact longest increasing subsequence for the formation of the tower.

The solution remains the same:
var msh = new List<int>();
for (int i = 1; i < = n; i++)
   for (int j = 0; j < i; j++)
    {
                if (w (j)*l(j) > w (i)*l (i) && max (msh [j] + 1) > msh (i)
                MSH (i) = msh[j] + 1;
    }
return msh.max();

while dynamic programming considers choices repeatedly, back tracking never considers an invalid option and reduces the number of options from the permutations.

Today we review another coding problem
Problem: There are a lot of cuboid boxes of arbitrary sizes.  Find the largest subset of cubes that can fit into each other.
Solution: This problem can be simplified if we think about cubes. Cubes can fit into each other based on their sorted edges.. This reminds us of a longest increasing subsequence (LIS) problem.
We recall the solution of the LIS problem as :
x can be a single-element increasing sequence or
x can be appended at the end of the longest increasing subsequence ending at some y provided that y precedes x and y < x
For example, 
Edges          11, 1, 10,  4, 3, 2, 8, 7, 12, 6, 9, 5
Length of     1   1    2   2  2  2  3  3   4   3  4, 3
subsequence
This we can now code as :
int getLIS(List<int> cubeedges)
{
var lis = new List<int>();
for (int i = 0; i < cubeedges.Count(); i++)
{
 for (int j = 0; j < i; j ++)
  {
      if (cubeedges[j] < cubeedges[i] && lis[j] + 1 > lis[i])
                     lis[i] = lis[j] + 1;
   }
}
return list.max();
}
The above is O(N^2). We can have  a O( N LogN ) solution also
Formally,
Let X[i] represent the sequence 2, 3, 1
Let M[j] store the index k of the smallest value X[k] so that there is an increasing subsequence of length j ending at X[k] on the range k <=i and j <=k <= i.  j represents the length of the increasing subsequence and k represents the index of termination.
and Let P[k] store the index predecessor of X[k]
The longest Increasing subsequence  at any given point is given by X [M [1]], X [M [2]], ... X [M [L]] and if there is an increasing subsequence at i then there is one at i-1 which is X [P [M[i]]] and between these two bounds we can do a logarithmic search for j <=k <= i
Therefore the steps are:
P = array of length N  - all initialized to zero
M = array of length N + 1 // pad on the left so that we can use zero based index.
L = 0
for i in range 0 to N-1:
      Binary search for the largest positive j <= L
      such that X[M[j]] < X[i]
      lo = 1
      hi = L
      Binary Search between lo and hi adjusts lo and hi
      After searching lo is 1 greater than the length of the longest prefix
      newL = lo
      The predecessor of X[i] is the last index of the subsequence of length newL-1
      P[i] = M[newL -1]
      M[newL] = i
      if newL > L:
          if we found a subsequence longer than L, update L
          L = newL

   // Reconstruct the longest increasing subsequence
T = array of length L
k = M[L]
for i in range L-1 to 0:
    T[i] = X[k]
     k = P[k]

return T
The only difference between cubes and cuboids is that we compare not one dimension but all three.

This means that all the edges in one must be smaller than the corresponding of the other 

Today we review a few more coding questions.

We can compare the coin counting puzzle with the classical knapsack problem. The knapsack problem is defined this way:
A thief robbing a store finds n items.
The ith item is worth vi dollars and weighs wi pounds, where vi and wi are
integers. The thief wants to take as valuable a load as possible, but he can carry at
most W pounds in his knapsack, for some integer W . Which items should he take?
(We call this the 0-1 knapsack problem because for each item, the thief must either
take it or leave it behind; he cannot take a fractional amount of an item or take an
item more than once.)

If the thief removes an item j from this load, the remaining load must be the most valuable load, weighing at most W-wj that the thief can take from the n-1 original items excluding j .
Therefore the knapsack problem can be written as follows:
case 1: with weight wj, find the maximum weights among n-1 weights to fill a bag that can hold W-wj
case 2: without weight wj, find the maximum weights among n-1 weights to fill a bag that can hold W

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)

for j from 0 to W do:
     m[0, j] := 0

for i from 1 to n do:
     for j from 0 to W do:
         if w[i-1] > j then:
             m[i, j] := m[i-1, j]
         else:
             m[i, j] := max(m[i-1, j], m[i-1, j-w[i-1]] + v[i-1])



The knapsack and the coin change are similar because we have to select the fewest high denomination
coins to reach a sum

we substitute the capacity W with the sum  to reach, the number of distinct items as n, the number of weights as denominations and the values as 1 each. We find the minimum instead of the maximum value as count of coins.

We can solve the previous problem by using combinations as shown below:
void CoinCount(ref List<int> coins, ref List<int>change, int amount, int start, int level)
{

for (int I = start; I < amount; I++)

{

for (int j = 1; i < coins.Count() && j <= amount/coins[I]; j++)

{

for (int k = 0; k < j; k++){
       change[level+k] = coins[i];
}

if (change.sum() == amount) Console.WriteLine("{0} with {1} elements", change.ToString(),
change.Count());

if (change.sum() < amount)

      CoinCount( ref coins, ref change, n, start+1, level+j);

for(int k = 0; k <j; k++){
      change[level+k] = 0;
}
}


The dynamic programming approach is as follows:

//
// returns the maximum sum that cannot be met by the given coins
//
public int CoinSumDP(List<int> coins, ref List<int> change, int amount, int start, int end) // start is for the type of coins and end is for the number of same coin and all coins appear in sorted duplicate manner and using start,end for contiguity start = 0; end = change.Count [start,end] range initialized to zero
{
//pseudo code
if (coins.Count() == 1) return Coins[0];
int sum = 0;
for (int i = 0; i < Coins.Count(); i++)
    var q = CoinSumDP(Coins.ChooseK(), ref change, amount, start, end) +
                  CoinSumDP(Coins[start].Repeat(end-start), ref change, amount, start, end)
    if q > sum
        sum = q
return Sum;
}