Bulb Switcher

Problem: 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. Return the number of bulbs that are on after n rounds.

Example:

Input: n = 2
Output: 1
Explanation: At first, the three bulbs are [off, off].
After the first round, the three bulbs are [on, on].
After the second round, the three bulbs are [on, off].
So we should return 1 because there is only one bulb is on.

Approach: Let's understand the problem first. All the bulbs are off at the beginning. After the first round, all the bulbs will be in on state(1,2,3,4,5,...n). After the second round, every second bulb will change its state which means state of bulbs at position 2,4,6,8,...(multiples of 2) will be changed. After the third round, state of every third bulb i.e. 3,6,9,12,...(multiples of 3) will be changed and so on.

Now if we see closely we will find out if odd numbers of operations are applied on a bulb then it will be in On state because starting state is off. for example Bulb one(1) will be always on because only one operation can be performed on this so we just have to find the number of operations performed on each bulb to decide it's state. if number of operations performed is odd then the bulb will be on and off otherwise. We can use the number of factors to know the number of operations as number of operations performed on bulb 'n' will be equal to number of factors of 'n'. Let's take an example to make it more clear:

Say n = 9. Let's see the factors of the numbers less than or equal to 9 -

• 1 - 1
• 2 - 1,2
• 3 - 1,3
• 4 - 1,2,4
• 5 - 1,5
• 6 - 1,2,3,6
• 7 - 1,7
• 8 - 1,2,4,8
• 9 - 1,3,9

Lets see when bulb 8 will be toggled:

• Round 1: Yes, every bulb is toggled
• Round 2: Yes, every 2nd bulb is toggled
• Round 3: No
• Round 4: Yes, every 4th bulb is toggled
• Round 5: No
• Round 6: No
• Round 7: No
• Round 8: Yes, every 8th bulb is toggled
• Round 9: No

Now if you see the number of times bulb 8 is toggled is equal to number of factors of 8 i.e. 4 (1, 2, 4 and 8). 

We know that factors always comes in pair for example 8 (1 and 8, 2 and 4) or 6 (1 and 6, 2 and 4) except numbers which are perfect square like 9(3 and 3 => only 3, 1 and 9) or 4 (1 and 4, 2 and 2 => only 2) so now we just have to check how many perfect square numbers are there which are less than or equal to our input number say 'n'. Now this is simple math, we can take the floor of the square root of 'n' to get this number. That's all. 

Implementation in C#:

        public static int BulbSwitch(int n)

        {

            return (int)Math.Sqrt(n);

        }

Complexity: O(1)

Coin Change

Problem: You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example:

Input: coins = [1,2,5], amount = 12
Output: 3
Explanation: 12 = 5 + 5 + 2

Approach: We are going to use DP here. We can maintain a 1D table where table[i] will tell the minimum number of coins required to make up amount "i". Obviously table[amount] will be our answer. Let's see how to fill this table:

1. FOR i = 0 to amount
• table[i] =  amount + 1
2. table[0] = 0
3. FOR i = 1 to amount
• FOREACH coin in coins // check for each coin
• IF coin <= i
• table[i] = Min (table[i], table[i - coin] + 1) // minimum number of coins for i - coin amount and 1 for this particular coin

That's all!

Implementation in C#:

        public int CoinChange(int[] coins, int amount)

        {

            int[] table = new int[amount + 1];

            Array.Fill(table, amount + 1);

            table[0] = 0;

            for (int i = 1; i <= amount; ++i)

            {

                for (int j = 0; j < coins.Length; ++j)

                {

                    if (coins[j] <= i)

                    {

                        table[i] = Math.Min(table[i], table[i - coins[j]] + 1);

                    }

                }

            }

            return table[amount] > amount ? -1 : table[amount];

        }

Complexity: O(m * n) where m is amount and n is length of coins array.

Vertical Order Traversal of Binary Tree

Problem: Given a binary tree, print it vertically. Look at the below image to understand it better

(Image taken from geeksforgeeks)

Example:

              1
          /     \
         2       3
        /  \    /  \
       4    5  6    7
                \  /  \
                 8 9   10 
                     \
                     11
                       \
                          12             
              
The output of print this tree vertically will be:
4
2
1 5 6
3 8 9
7 11
10 12

Approach: We can use horizontal distances of the node to see what all the nodes are in same vertical line or not. We can define horizontal distance as follows:

1. Horizontal distance of root is 0.
2. if a node's horizontal distance is n then horizontal distance of node's left and right will be n - 1 and n + 1 respectively.

We can maintain a hash with key as horizontal distance and value as list of nodes. We will do a level order traversal fill the hash with horizontal distance and nodes. In the end we will just print all the values of hash in key's sorted order.

Note that we could use Pre Order traversal too instead of level order traversal but it could result in incorrect order of nodes at a particular horizontal distance. If you look at the example given in the problem, you will observe with pre-order traversal 12 will come before 10 which is not right.

Implementation in C#:

        public List<List<int>> VerticalOrderTraversal()

        {

            if (this.Root == null)

            {

                return new List<List<int>>();

            }

            int hd = 0;

            Queue<Tuple<BinaryTreeNode, int>> queue = new Queue<Tuple<BinaryTreeNode, int>>();

            queue.Enqueue(new Tuple<BinaryTreeNode, int>(this.Root, hd));

            SortedDictionary<int, List<int>> hash = new SortedDictionary<int, List<int>>();

            while(queue.Count > 0)

            {

                Tuple<BinaryTreeNode, int> tuple = queue.Dequeue();

                BinaryTreeNode node = tuple.Item1;

                hd = tuple.Item2;

                if (!hash.ContainsKey(hd))

                {

                    hash.Add(hd, new List<int>());

                }

                hash[hd].Add(node.Value);

                if (node.LeftNode != null)

                {

                    queue.Enqueue(new Tuple<BinaryTreeNode, int>(node.LeftNode, hd - 1));

                }

                if (node.RightNode != null)

                {

                    queue.Enqueue(new Tuple<BinaryTreeNode, int>(node.RightNode, hd + 1));

                }

            }

            List<List<int>> result = new List<List<int>>();

            foreach (int key in hash.Keys)

            {

                result.Add(hash[key]);

            }

            return result;

        }

Complexity: O(n)

Nth Super Ugly Number

Problem: Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whose all prime factors are in the given prime list of size k.

Example:

Input: n = 5, primes = [2,7]
Output: 8 
Explanation: [1,2,4,7,8] is the sequence of the first 5 super ugly numbers given primes = [2,7].

Approach: The approach will be same as finding Nth Ugly Number. Here the primes are given in an array where as in the previous problem we have only 2, 3 and 5 as primes. You can understand it by just looking at the implementation and the approach of the previous problem.

Implementation in C#:

        public static int NthSuperUglyNumber(int n, int[] primes)

        {

            if (n == 0)

            {

                return 0;

            }

            List<int> table = new List<int> { 1 };

            int[] primesCount = new int[primes.Length];

            for (int i = 0; i < n - 1; ++i)

            {

                table.Add(NextSuperUglyNumber(table, primes, primesCount));

            }

            return table.Last();

        }

        private static int NextSuperUglyNumber(List<int> table, int[] primes, int[] primesCount)

        {

            int nextSuperUglyNumber = int.MaxValue;

            for (int i = 0; i < primes.Length; ++i)

            {

                nextSuperUglyNumber = Math.Min(nextSuperUglyNumber, primes[i] * table[primesCount[i]]);

            }

            for (int i = 0; i < primes.Length; ++i)

            {

               if (nextSuperUglyNumber == primes[i] * table[primesCount[i]])

                {

                    ++primesCount[i];

                }

            }

            return nextSuperUglyNumber;

        }

Complexity: O( n* m) where m is the size of primes array

Burst Balloons

Problem: You are given n balloons. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. After the burst, the i - 1 and i + 1 then becomes adjacent.

Return the maximum coins you can collect by bursting the balloons wisely.

Example:

Input: nums = [6, 11]
Output: 77
Explanation:
First burst nums[0] then coins earned = 1 * 6 * 11 = 66
then burst nums[1] then coin earned =  1*11*1 = 11 so total coins earned are 66 + 11 = 77

Approach: We are going to use DP here. We are going to use 2D table say Table where Table[i][j] will tell the maximum coins earned for sub array nums[i...j]. Obviously Table[0][n - 1] will be our answer.

Now let's see how to fill this table:

1. FOR len = 1 to Length // for every possible length or every subarray
• For left = 0  to Length - len // left index of subarray
• right = i +  len - 1 // Right index of sub array so target sub array is (left...right)
• For last = left to right // Max coin earned by considering each element of sub array as last balloon to burst
• leftValue = nums[left - 1] // all the balloons are burst so we need to take the left of the subarray
• rightValue = nums[right + 1] // all the balloons are burst so we need to take the right of the subarray
• numOfCoinsEarnedBeforeLastBalloonBurst = Table[left][last - 1] // coins earned from left subarray of last balloon which will be (left...last-1)
• numOfCoinsEarnedAfterLastBalloonBurst = Table[last + 1][right] // coins earned from right subarray of last balloon which will be (last + 1...right)
• currentValue = leftValue * nums[last] * rightValue + numOfCoinsEarnedBeforeLastBalloonBurst + numOfCoinsEarnedAfterLastBalloonBurst 
• Table[left][right] = MAX(currentValue, Table[left][right]).

As usual we need to take care of corner cases in above steps which you can see in the implementation. That's all!

Implementation in C#:

        public int MaxCoinsByBurstingBalloons(int[] nums)

        {

            if (nums?.Length == 0)

            {

                return 0;

            }

            int[,] table = new int[nums.Length, nums.Length];

            for (int length = 1; length <= nums.Length; ++length)

            {

                for (int i = 0; i <= nums.Length - length; ++i)

                {

                    int j = i + length - 1;

                    for (int k = i; k <= j; ++k)

                    {

                        int left = i == 0 ? 1 : nums[i - 1];

                        int right = j == nums.Length - 1 ? 1 : nums[j + 1];

                        int beforeCoins = k == i ? 0 : table[i, k - 1];

                        int afterCoins = k == j ? 0 : table[k + 1, j];

                        table[i, j] = Math.Max(table[i, j], left * nums[k] * right + beforeCoins + afterCoins);

                    }

                }

            }

            return table[0, nums.Length - 1];

        }

Complexity: O(n^3)

Best Time to Buy and Sell Stock with Cooldown

Problem: Like the previous Buy and Sell stock problems, you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. 

You may complete as many transactions as you like with the following two restrictions:

1. You may not engage in multiple transactions at the same time (i.e. you must sell the stock before you buy again).
2. After you sell your stock, you cannot buy stock on next day. (i.e. cooldown of 1 day)

Example:

Input: [2,3,4,1,5]
Output: 5 
Explanation: transactions = [buy, sell, cooldown, buy, sell]

Approach: Like in previous problems, we are going to use DP approach here too. Let's have 2 1D Tables, say Buy where Buy[i] will tell the minimum money we can invest on buying stock till ith day and another table is Sell where Sell[i] will tell the maximum money we made till ith day by selling the stocks. Obviously Sell[n] will be our answer.

Here is how we can fill these tables:

1. Buy[0] = - Prices[0] and Buy[i] = MAX(Buy[i - 1], Sell[i - 2] - prices[i]). How? Here is the explanation:
• At a particular day i, either we don't do anything i.e. Buy[i - 1]. Take the previous day amount as we did not buy.
• Or we buy but to buy we need to serve the one day cooldown. That's why we will take Sell[i - 2]. Now if we buy we are spending Sell[i - 2] - prices[i] money. 
• We take the maximum of above these two numbers (hint: negative numbers) and assign it to Buy[i].
2. Sell[i] = Max(Sell[i - 1], Buy[i - 1] + prices[i]). Here is the explanation why:
• We can decide not to do any thing. In that case we will just take the previous day's amount and assign that is Sell[i - 1].
• We can decide to sell. In that case we will get Buy[i - 1] + prices[i]. Buy[i - 1] will give the minimum amount spent on buying till (i - 1)th day. 
• We take the maximum of above these two numbers and assign it to Sell[i].

We need to take care of some corner conditions and we are good to go. This will solve the problem in linear time which is very good but can we do something to optimize it further? It is obvious that we can't optimize time complexity as we have to touch each and every element of Prices array to decide the maximum profit. Then what we can do?

We can reduce space complexity. If you see we are using O(n) space which is not required. If we see closely at the above algorithm, we will find out that to calculate Buy[i] and Sell[i], we just need Buy[i - 1], Sell [i - 1] and Sell [i - 2]. That means we can use limited number of variables instead of maintaining two whole arrays to store these values. 

Let's say sell_1 is Sell[i - 1], sell_2 is Sell[i - 2] and buy_1 is Buy[i - 1]. For Buy[i] and Sell[i], we will use variables say currBuy and currSell respectively. Now our changed algorithm will look like: 

1. buy_1 = -Prices[0], sell_2 = 0, sell_1 = 0, currBuy = 0, currSell = 0
2. FOR i := 1 To n
• currBuy = MAX(buy_1, sell_2 - Prices[i])
• currSell = MAX(sell_1, buy_1 + Prices[i])
• sell_2 = sell_1
• sell_1 = currSell
• buy_1 = currBuy
3. Return currSell

You can see there is not much of change as such in algorithm except using variables instead of arrays. Hopefully its clear now and we can go to the implementation.

 

Implementation in C#:

        public int MaxProfitWithCoolDown(int[] prices)

        {

            if (prices?.Length <= 1)

            {

                return 0;

            }

            int buy_1 = -prices[0], sell_2 = 0, sell_1 = 0, currBuy, currSell = 0;

            for (int i = 1; i < prices.Length; ++i)

            {

                currBuy = Math.Max(buy_1, sell_2 - prices[i]);

                currSell = Math.Max(sell_1, buy_1 + prices[i]);

                sell_2 = sell_1;

                sell_1 = currSell;

                buy_1 = currBuy;

            }

            return currSell;

        }

Complexity: O(n)

Measuring 6L water from 4L and 9L buckets

Problem: You are given one 4 liter bucket and one 9 liter bucket. The buckets have no measurement lines on them either. How could you measure exactly 6 liter using only these buckets given you have as much extra water as you need.

Solution: Let's say 4L bucket is Bucket_4 and 9L bucket is Bucket_9. Initial value is [Bucket_4: 0, Bucket_9: 0](empty buckets). We can measure 6 liter by following below steps: 

1. Fill Bucket_9. [Bucket_4: 0, Bucket_9: 9]
2. Fill Bucket_4 from Bucket_9. [Bucket_4: 4, Bucket_9: 5]
3. Empty Bucket_4. [Bucket_4: 0, Bucket_9: 5]
4. Fill Bucket_4 from Bucket_9. [Bucket_4: 4, Bucket_9: 1]
5. Empty Bucket_4. [Bucket_4: 0, Bucket_9: 1]
6. Fill Bucket_4 (remaining 1 L water in Bucket_9) from Bucket_9. [Bucket_4: 1, Bucket_9: 0]
7. Fill Bucket_9. [Bucket_4: 1, Bucket_9: 9]
8. Fill Bucket_4 from Bucket_9. Bucket_4 can only take 3L more as 1L is already there in Bucket_4. [Bucket_4 : 4, Bucket_9: 6]

Now you can see that at step 8 Bucket_9 will have 6L (9 - 3) water.