Tuesday, January 27, 2015

Next greater number with same digits

Given a number, how do we find the next greater number with the same digits?

For example if the given number is 123, the next greater number with the same digits is 132.
Similarly for 23876, the output is 26378.

If all the digits of the number are in decreasing order (Eg. 54321), there is no greater number with the same digits.

Let us look at the solution approach. If we simply sort the digits of the number in descending order, we will surely get the greater number with the same digits.

For example if we sort the digits of 123, we get 321.

But we are looking for the least among all greater numbers. In the above example 132 is least among {132, 213, 231, 312, 321}. How do form such a number?

If we swap any two digits a number, it's value either increases or decreases depends on their order.

For example consider 58762
  • If we swap 8,7 the value (57862) decreases because the bigger digit appears before smaller digit. 
  • If we swap 5,6 the value (68752) increases because the lesser digit appears before the bigger digit. 
So we have to find a pair of digits such that the lesser digit appears before the bigger digit.

We know that as we move from right to left digits in a number, the place value of them increases. So to keep the value as low as possible, we need to find such a pair from right to left.

Even after swapping, the value can be minimized further. 

For example 57862, we don't  swap 8,2 or 8,6 as they are in descending order. 
We swap the 7,8; the value becomes 58762. If we order the digits after 8 in ascending order, it becomes 58267 which is the required answer.

Here is the C++ implementation of the above. For python code click this link.

Friday, January 23, 2015

How to check if a string is a rotation of another string

Given two strings, how to check one is a rotation of the other?

For example consider the strings "abcd", "cdab". If we rotate any string twice, you will get the other string.

A simple way of solving this problem is to rotate one string, and see if it matches the other string. 

But we don't know after how many rotations, it matches with the other string. In worst case, there will be (L-1) rotations, where L is the length of the string. Because If we rotate a string L times, it restores it's original order. Each time we rotate, we have to check the equality of strings which is O(n) time in worst case. So the overall complexity of this solution is O(n2).

Is there any other simpler technique? Yes!

The trick here is to observe that if we append a string to itself, it contains all of its rotation patterns! 

For example consider the string "abc", after appending to itself it becomes "abcabc". Now try to see all it's rotation patterns like "bca", "cab" appear in it.

So the problem is simply finding the sub-string in the expanded string. Here is the simple program written in C++/Python.

Wednesday, January 14, 2015

Joining an array of numbers to form the biggest number

Given an array numbers, we have to join them in such a way that it forms the biggest number.

For example consider the simple three element array [10,3,2], they can be joined in following ways
1032, 1023, 2103, 2310, 3102, 3210. Among these numbers 3210 is the biggest number.

To solve this problem we definitely have to sort the given numbers using some criteria to form the biggest number. 
Considering the above example, if we simply sort them in descending order, the array becomes [10,3,2] which does not form the biggest number.

Similarly we can also sort numbers by comparing the numbers string comparison. This does not work in cases like [1,10]. Since "10" > "1" the array in sorted as [10,1], but 110 is the biggest number.

We should think of a custom comparison function which guarantees us the biggest number when joined. Let us join the two numbers to be compared in two ways and compare them.

Considering the above example, they become 110 ("1"+"10"), 101( "10"+"1"). Since 110 is higher we place 1 first in sorting order before 10.

Here is the simple python implementation of the above algorithm. Also see my post on geeksforgeeks for C++ implementation of the same algorithm.

Monday, January 12, 2015

Printing all K combinations from N numbers

Given two numbers N and K, how do we print all the K-combinations of numbers from the set {1,2,...N}.

For example consider N = 4, K = 3, the possible combinations are
 [1, 2, 3]
 [1, 2, 4]
 [2, 3, 4]
 [1, 3, 4]

Let us look how to solve this combination problem. This problem can be recursively defined as follows. To generate K-combinations from N elements, we have two possibilities.
  1. Generate K-Combinations from (N-1) elements.
  2. Generate (K-1)-Combinations from (N-1) elements and append N to all of them.
Let us simulate this with an example. Assume N = 3, K = 2

Generate 2-Combinations from 2 elements i.e N = 2, K = 2
This will be just one combination i.e [1, 2]

Generate 1-Combinations from 2 elements i.e N = 2, K = 1
[1], [2]
Append 3 to each of them
[1, 3], [2,3]

So there are totally 3 combinations [ [1, 2], [1, 3], [2, 3] ].

Here is the recursive implementation in C++.

Wednesday, January 7, 2015

Implementing power function

Given the base and exponent, how do we implement the pow(base,exp) function efficiently?

For example 
pow(2.0,5) = 32
pow(0.4,2) = 0.16
pow(2.0,-2) = 0.25

For simplicity, let us assume that the base can be a decimal number and exponent can be any integer. A straight forward implementation that comes to mind is simply multiplying the base with itself for 'e' times where e is the exponent.

There is one more efficient way to calculate this value using divide and conquer technique. If we have to calculate an, we can divide the computation into two similar tasks i.e we can calculate an/2 once, and multiplying it with itself gives the required value
an = an/2*an/2

Here is the C++ implementation of the above algorithm. This reduces the number of multiplications required for calculating the power. Observe how different test cases are handled in the program.

Monday, January 5, 2015

Minimum number of characters to insert to make a palindrome

Given a string, how do you find the minimum number of characters to insert to make it a palindrome?

For example given a string "abbc", the number of characters to insert is 2, and the resulting palindrome is "cabbac"

Take another example "abc", we need to insert two characters at a minimum to make it a palindrome "abcba"

If the given string is already a palindrome, the result is 0.

Let us analyze the problem to find out a solution. Given a string, we have two possible cases
  • Case 1:The first and last characters are equal. In this case, the minimum number of characters to insert depends on the sub-string between the first and last characters. 
    • For example consider the string "abca", the value depends on the sub-string "bc"
  • case 2:The first and last characters are not equal. In this case, we have to make the first and last characters equal to make it a palindrome. We can do this in two ways. Either we can insert a new character before the first character, or next to the last character. 
    • For example consider "gcc", to make first and last characters equal, we can insert a "c" first or insert a "g" last. It either becomes "cgcc" or "gccg". since "gccg" is minimal way of making a palindrome, We just need to insert 1 character.
Let us denote the minimum number of characters to insert as MCI. It can be defined as follows. str is a string of length n.

MCI(str) = MCI( str[1:n-2] ) if str[0] = str[n-1]
         = Min( MCI(str[0:n-2]), MCI(str[1:n-1]))+1 otherwise

A naive recursive implementation is straight forward. To implement dynamic programming solution, we create a a two dimensional table of size n*n.

table[i][j] indicates MCI of the sub-string str[i:j] the table is calculated using the following rules.

table[i][i] is always 0 because a single character is a palindrome.

table[i][j] = table[i+1][j-1] if str[i] = str[j]
            = Min(table[i+1][j], table[i,j-1])+1 otherwise

We construct this table in bottom up manner i.e solve the smaller problems first and use their result to solve bigger problems. Finally table[0][n-1] contains the required value.

Below is the dynamic programming implementation in C++.

Thursday, January 1, 2015

Longest common subsequence problem

This is a famous computer science problem with various applications in tools such as file diff, bio informatics etc. For more information read this on wiki.

Given a set of strings, how do we find the longest common sub-sequence(LCS) among them?

For example, LCS{"ATDACG","CTDACGA"} is  "TAG".

In this post, we will look at the algorithm to find the LCS of two strings. To understand the solution, let us walk through a simple example.

Let us consider the strings "ACDG", "CAG". We can recursively define the LCS of two strings str1, str2 of lengths n,m as follows.
LCS(str1, str2) = 
    LCS(str1[0:n-2], str2[0:m-2])+str1[n-1] if str1[n-1] = str2[m-1]
    Max(LCS(str1,str2[0:m-2], LCS(str1[0:n-2],str2)) otherwise

Using the above definition
LCS("ACDG","CAG") = LCS("ACD", "CA") + "G"

This means that since the last character is same, in the sub-problem we can delete it from both the strings.
Further calculations go as follows

LCS("ACD", "CA") = Max( LCS("AC", "CA"), LCS("ACD","C") )
LCS("ACD", "C") = Max( LCS("AC", "C"), LCS("ACD","") )

and so on... 

we can see that LCS("ACD","CA") is "C"; so "CG" is the final output.

If we implement this naive recursion, we repeat the calculation for many sub problems. For efficient implementation we use a 2 dimensional array of size (n+1)*(m+1).The table is calculated using the rules given below which directly follow from the recursive definition given above.
table[i][j]= 0 if either of the string is empty
           = 1 + table[i-1][j-1] if their last characters are equal
           = max(table[i-1][j], table[i][j-1]) otherwise
Here is an example table.

  ∅ B A C B A D
∅ 0 0 0 0 0 0 0
A  0 1 1 1 1 1 1
B  0 1 1 1 2 2 2
A  0 1 2 2 2 3 3
Z  0 1 2 2 2 3 3
D  0 1 2 2 2 3 4
C  0 1 2 3 3 3 4
Here are the python implementations of both approaches.