Puzzle : Count possible combinations of coins

Q. Given a sum of value S and infinite supply of coins each of value C = { C1, C2, .. , Cn}, how many ways can you make the change? The order of coins doesn’t matter.

For example, for S = 5 and S = {1,2}, there are three solutions:  (1, 1, 1, 1, 1), (1, 1, 1, 2), (1, 2, 2) . So output should be 3. For S = 10 and C = {2, 5, 3, 6}, there are five solutions: (2,2,2,2,2), (2,2,3,3), (2,2,6), (2,3,5) and (5,5). So the output should be 5.

Yes, I agree; this question is hard. But can we simplify it to come up with a solution that will solve this tough one!

What if C was { 1 } and S was 10? Number of combinations possible is 1; Ten times 1 is the only way to form the sum 10. That was quick and easy, right? ūüėÄ

Lets take it to next level. This time, lets try with more coins: 1 and 2 and same sum: 10. Yes, many combinations flashed my mind too. Lets cross this bridge one step at a time. Lets first list out all the combinations

1464_1

How do I convert this to a program!!! Lets walk through the process that happened in my brain when I wrote down those combinations.

  1. I took zero 2 and tried to form the remaining sum with all 1. I could use ten 1 to form the sum.
  2. I took one 2 and tried to form the rest of the sum with all 1.
  3. Took three 2 and got six 1
  4. Took four 2 and got four 1
  5. Took five 2 and got two 1
  6. Took six 2 and got zero 1

Good question (if this already came up in your mind)! what if I tried to find the count of 2 by giving values to number of 1. Lets work it out.

1464_2

Both cases, I did nothing but iterate from 0 till a number which when multiplied with the chosen coin (2 in first case and 1 in second case) is larger than sum. In every step, I tried to form the remaining “sum” with rest of the denominations.

We encountered more steps than in the previous one but at the end it turned out to be the same number of combinations. Obvious! Trying out both ways helped us discover an optimization: Larger Denominations First. Lets shorten it to LDF ūüėČ

So lets transform our knowledge to algorithm now. For that, lets set some terminologies.

Terminologies:

  1. D : All denominations(coins) in ascending order. Why sorting? Sorting is just to implement LDF (Larger Denominations First) and is optional.
  2. D[i] : value of i-th coin . Assume that index starts with 1.
  3. S : sum to be formed.
  4. F(i, S) : Returns the maximum combinations possible with first ‘i’ denominations to form sum ‘S’
  5. F(i, n, S) : Returns the maximum combinations possible with first ‘i’ denominations using i-th denomination ‘n’ times. This function is to find the maximum combinations possible with remaining denominations while keeping the count of i-th denomination to a particular value.

For our case where D = { 1, 2 } and S = 10:

  • F(2, 10) should give us 6 since there are 6 different ways to form a sum of 10 with 1 and 2
  • F(1, 10) should give 1.
  • F(2, 0, 10) should give 1
  • F(2, 1, 10) should give 1
  • F(2, 2, 10) should give 1
  • F(2, 3, 10) should give 1
  • F(2, 4, 10) should give 1
  • F(2, 5, 10) should give 1
  • F(2, 6, 10) should give 0
  • F(2, 7, 10) should give 0

Lets try to define F(i, S) in terms of F(i, n, S).

1464_3

This is nothing but mathematical representation of a for-loop with variable x iterating from 0 to (S/D[i]),  beyond which the x*D[i] will be greater than S.

Now we should define F(i, n, S). As stated before, F(i, n, S) is the maximum number of combinations possible with D[i] used ‘n’ times. With the number of D[i] fixed to n, we just need to iterate through the rest of the coins. So it can be defined as

1464_4

It is a recursive function which reduces the sum by D[i]*n and finds the maximum combinations with rest of the coins. But what should it do when it reaches the last denomination? It should be able to divide the sum without any remainder; if not, there is no possible combination with the chosen numbers. Simple!

1464_5

Now, lets try to apply our new algorithm.

F(2, 10) = F(2, 0, 10) +
           F(2, 1, 10) +
           F(2, 2, 10) +
           F(2, 3, 10) +
           F(2, 4, 10) +
           F(2, 5, 10)
         = F(1, 0, 10) + F(1, 2, 10) + F(1, 3, 10) + F(1, 4, 10) + F(1, 5, 10) + F(1, 6, 10) + F(1, 7, 10) ++ F(1, 8, 10) + F(1, 9, 10) + F(1, 10, 10) +           F(1, 0, 8) + F(1, 1, 8) + F(1, 2, 8) + F(1, 3, 8) + F(1, 4, 8) + F(1, 5, 8) + F(1, 6, 8) + F(1, 7, 8) ++ F(1, 8, 8) + 
           F(1, 0, 8) + F(1, 1, 8) + F(1, 2, 8) + F(1, 3, 8) + F(1, 4, 8) + F(1, 5, 8) + F(1, 6, 8) + F(1, 7, 8) ++ F(1, 8, 8) + 
           F(1, 0, 6) + F(1, 1, 6) + F(1, 2, 6) + F(1, 3, 6) + F(1, 4, 6) + F(1, 5, 6) + F(1, 6, 6) +
           F(1, 0, 4) + F(1, 1, 4) + F(1, 2, 4) + F(1, 3, 4) + F(1, 4, 4) + 
           F(1, 0, 2) + F(1, 1, 2) + F(1, 2, 2) + 
           F(1, 0, 0)
         = 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 1 +
           0 + 0 + 0 + 0 + 0 + 0 + 0 + 1 +
           0 + 0 + 0 + 0 + 0 + 1 +
           0 + 0 + 0 + 1 +
           0 + 1 +
           1 
         = 6

That worked!

Lets write some Java now..

package fun.puzzles;

import java.util.Arrays;
import java.util.List;

public class CoinCombinationsPuzzle {
    
    private final List<Integer> coins; 
    
    public CoinCombinationsPuzzle(List<Integer> coins) {
        this.coins = coins;    
    }
    
    public int maximumPossibleCombinations(int numOfCoins, Integer sum) {
        coins.sort(null);
        int maxIteration = sum/coins.get(numOfCoins);
        int maxPossibleCombinations = 0;
        for (int i = 0; i <= maxIteration; i++) {
            maxPossibleCombinations += maximumPossibleCombinations(numOfCoins, i, sum);
        }
        return maxPossibleCombinations;
    }
    
    public int maximumPossibleCombinations(int numOfCoins, int count, Integer sum) {
        // safety check
        if (numOfCoins < 0) { return 0;    }
        if (numOfCoins < 1) {
            if (count * coins.get(numOfCoins) == sum) {
                return 1;
            }
            else {
                return 0;
            }
        }
        // Reduce the fixed denomination from sum
        sum -= (count * coins.get(numOfCoins));
        int maxIteration = sum/coins.get(numOfCoins-1);
        int maxPossibleCombinations = 0;
        for (int i = 0; i <= maxIteration; i++) {
            maxPossibleCombinations += maximumPossibleCombinations(numOfCoins-1, i, sum);
        }
        return maxPossibleCombinations;
    }
    
    public int maximumPossibleCombinations(Integer sum) {
        return maximumPossibleCombinations(coins.size()-1, sum);
    }
    
    public void printMaximumPossibleCombinations(Integer sum) {
        System.out.printf("Coins: %-50s Sum: %-5d MaximumPossibleCombinations: %-5d\n", 
                coins, sum, maximumPossibleCombinations(coins.size()-1, sum));
    }
    
    public static void main(String[] args) {
        List<Integer> coins;
        CoinCombinationsPuzzle ccp;
        
        coins = Arrays.asList(1, 2);
        ccp = new CoinCombinationsPuzzle(coins);
        ccp.printMaximumPossibleCombinations(5);
        
        coins = Arrays.asList(1, 2);
        ccp = new CoinCombinationsPuzzle(coins);
        ccp.printMaximumPossibleCombinations(10);
        
        coins = Arrays.asList(1, 2, 3);
        ccp = new CoinCombinationsPuzzle(coins);
        ccp.printMaximumPossibleCombinations(100);
        
        coins = Arrays.asList(1, 2, 5, 10);
        ccp = new CoinCombinationsPuzzle(coins);
        ccp.printMaximumPossibleCombinations(1074);
    }
}

Output:

1464_6

This solution can still be optimized by caching the results of recursive method: maximumPossibleCombinations(int numOfCoins, int count, Integer sum)

 

Find the biggest black square from an N*N matrix of black or white squares

Question:

Find the biggest black square from an N*N matrix of squares. 1 means it’s black, 0 means it’s white. Output should be the list of squares which forms the largest black square.

Input ¬†¬† ¬†: ‘{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#1#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}’

Output    :    {(3#0,3#1,3#2,3#3),(4#0,4#1,4#2,4#3),(5#0,5#1,5#2,5#3),(6#0,6#1,6#2,6#3)}

 

Solution(Python):

    # Author            :        Sreejith Sreekantan
    # Description        :        

    #                         Find the biggest black square from an N*N matrix of squares. 1 means it's black, 0 means it's white
    #                         Input     : '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#1#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
    #                         Output    :    {(3#0,3#1,3#2,3#3),(4#0,4#1,4#2,4#3),(5#0,5#1,5#2,5#3),(6#0,6#1,6#2,6#3)}
    

#!/usr/bin/python

def largestSquareAt(sq, i, j, k=1):
    if not ( i+k<len(sq) and="" j+k<len(sq[i])="" ):=""   =""    =""  return="" 0=""  for="" x="" in="" range(0,k):=""  if="" sq[i+x][j+k-1]="='0':" y="" sq[i+k-1][j+y]="='0':" 1="" +="" largestsquareat(sq,="" i,="" j,="" k+1)  =""  ="" def="" biggestsquare(input1):="" len(input1)="=0" or="" not="" (="" input1.count('{')="=input1.count('}')" )="" :="" ''=""  i="str(input1)"  j="i" for="" j]=""  resx="-1"  rexy="-1"  ressize="-1"  res="[]" range(0,len(j)):=""  res.append([])="" range(0,len(j[x])):=""  res[x].append(largestsquareat(j,="" x,="" y))="" ressize<res[x][y]:=""  resy="y"  resstring="" ressize="">0:                                
        resstring = "{"
        for x in range(resx,resx+ressize):
            if x>resx:
                resstring += ","
            resstring += "("
            for y in range(resy,resy+ressize):
                if y>resy:
                    resstring += ","
                resstring += (str(x)+"#"+str(y))
            resstring += ")"    
        resstring += "}"
    
    return resstring  

input = '{0#1#1#0,0#1#1#1,0#1#1#1,1#1#1#1}'
input1 = '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#1#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
input2 = '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#0#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
input3= '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,0#1#0#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
input4 = '{0#0#0#0,0#0#0#0,0#0#0#0,0#0#0#0}'
print biggestSquare('')    
print biggestSquare(input1)    
print biggestSquare(input2)        
print biggestSquare(input3)        
print biggestSquare(input4)

Given a string of length N, output “Correct” if brackets close in correct order else output “Incorrect”

Question:

Given a string of length N, output “Correct” if brackets close in correct order else output “Incorrect”

Input     :   ({}[((({{}})[{()}]))])

Solution(Python):

    # Author            :        Sreejith Sreekantan
    # Description        :        

    #                         Given a string of length N, output "Correct" if brackets close in correct order else output "Incorrect"
    #                         Input     : ({}[((({{}})[{()}]))])
    #                         

#!/usr/bin/python
def validString(input1):
    stk = []
    flag = True
    for x in input1:
        if x in ['{', '(', '[']:
            stk.append(x)
        else:
            if  len(stk)==0:
                flag = False
            elif x == '}' and not stk[len(stk)-1]=='{' :
                flag = False    
            elif x == ')' and not stk[len(stk)-1]=='(' :
                flag = False 
            elif x == '}' and not stk[len(stk)-1]=='{' :
                flag = False    
            if not flag:
                return "Incorrect"
            else:
                stk.pop()
    return "Correct"
 

input1 = '({}[((({{}})[{()}]))])'
input2 = '({}((({{}})[{()}]))])'
print validString(input1)    
print validString(input2)

Count Inversions in an array

This file contains all of the 100,000 integers between 1 and 100,000 (inclusive) in some order, with no integer repeated.

Your task is to compute the number of inversions in the file given, where the ith row of the file indicates the ith entry of an array.

 

Tips:

If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.
Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

Eg: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

 

 

You can get working program from here

Input files :     Input1            Input2

 

Answer for input1 :

Answer for input 2: 25

Algorithm Puzzles

Q:

You are given a sorted (from smallest to largest) array A of n distinct integers which can be positive, negative, or zero. You want to decide whether or not there is an index i such that A[i] = i. Design the fastest algorithm that you can for solving this problem.

Ans.

Input: Array a[0..n-1] of n elements

pseudocode:

func(a, i, k) {
j = (i + k)/2
if      (a[j]==j)    return True
else if (a[j]<j) ¬†¬†=”” return=”” <span=”” class=”hiddenSpellError” pre=”return ” data-mce-bogus=”1″>func(a, j, k)¬†¬†¬†¬†¬†¬† // since all numbers are distinct, a[x]
else                 return func(a, i, j)        // since all numbers are distinct, a[x]>x for all x > j
}

C++ Brain Teaser : Virtual Destructor

Hi All,

This time I plan to explain to you a C++ brain teaser I came across. With no further adieu, let me get directly to the question:

C++ Brain Teaser : Virtual Destructor Question

What is the problem with this code, if any?

(Assurance from me: this code will compile and execute fine. ie. no compilation error)

.

.

.

.

.

.

Hope you have put enough thought on it. Some might have already cracked it. For the rest of the folks, let me reveal it.

Yes, this code has some serious problem at run-time. If not compilation-error, what is it?

You are right; the worst nightmare, memory leak! But where is it leaking?

Let pause that question for a few minutes to discuss something in C++ language.

In a scenario where a Child class inherits a Parent class, when a Child object is created, first the Parent-Constructor is invoked and then the Child-Constructor and when the Child object is destroyed, first the Child-Destructor is invoked and then the Parent-Destructor is executed.

In our above program, we use a variable of type “Parent” to point to a “Child” object. Lets use below program to check if the order of invocation of constructor and destructor is followed in this case.

virtual Destructor program with cout

Output of the above program is:

Screen Shot 2014-02-04 at 2.33.23 PM

As you can see, here the child destructor is not invoked, which means, whatever we coded in the Destructor method of Child class is not executed. In our main program, we allocate an array of memory in the Constructor of Child and delete the same in its Destructor. So our main program successfully allocates an array of memory but don’t delete it, which will result in Memory Leak.

So we have answered our question. Now lets see how we can avoid it.

Here is where Virtual-Destructor comes for help. Make the destructor of “Parent” class virtual and this issue is solved.

New implementation of “Parent”:

Virtual Destructor New Parent impNew output:

Virtual Destructor new output

To put it straight, virtual destructor forces the parent class to check for child class destructors and executes it.

Use a virtual destructor if you ever expect a derived class to be destroyed through a pointer to the base class to ensure that the destructor of the most derived classes gets called.

It’s a good practice to make the destructors of all interface classes, ie. any class with at-least one virtual method, as virtual.