Minimum number after removing K digits

Given a number N, and a number K, find the minimum number that can be formed by deleting K digits. The order of the digits should not be changed.

For example consider N = 234987, K = 2, we can remove 9,8 and the resulting number is 2347.

The solution is based on the following observation, consider the above case.

Let us delete a digit from 234987
Deleted Digit – Result
—————————
2             – 34987
3             – 24987
4             – 23987
9             – 23487
8             – 23497
7             – 23498
If we remove 9 we will get the minimum number. Observe that in the given number, 9 is the first digit which is greater than the next digit.

What if all the digits are in ascending order?

Let us walk through an example.
N = 12345, K = 3. If we remove 4,5 we will get the minimum number. The observation is that we need to keep on removing right-most digits in this case.

[This is a re-post after correcting my incorrect approach. Thanks to Jeff Senecal for pointing out the mistake.]

Here is the C++ implementation of the above approach.

Maximum nesting depth of a paranthesis expression

Given a parenthesis expression, We have to find the maximum nesting depth.
For example: the expression ()((()))(()) has a maximum nesting depth of 3.
The expression ((()())) has a maximum nesting depth of 3.
Let us output -1 for an unbalanced expressions such as (())) or ()(

This is a simple problem that can be asked in different forms. One such example can be
Given a sequence of jobs executed by a machine. What is the maximum number of parallel jobs executed at any point of time.

One more variation of this problem can be

Given a maximum capacity of a computer center, and a sequence of people arrived, how many people have to wait for their turn.

Check this question for details.

Here is the simple O(n) solution for the original problem.
1. Take two variables depth and max_depth initialize them to zero.
2. Increment depth if we see an open bracket and update the max_depth
3. Decrement depth if we see a closed bracket and check if it is going negative.If it goes negative, the expression is unbalanced.
4. Check if depth is zero. If it is not zero, then it is not a balanced expression.
5. Return max_depth
With minor modifications to this algorithm, we can design an algorithm for the second variation also.

Here is the Python implementation.The time complexity for this O(n) and space complexity is O(1).

Minimum number of chages to make equal groups

Given an array of numbers, how do we find the minimum number of changes(additions/subtractions) to the elements so that each number in the array is same or equal.

For example given the array {1, 2, 3, 4}, the minimum number of changes are 3. i.e we can choose any of the four elements and make the other three elements equal to the chosen element.

Similarly given the array {56, 29, 112, 29}, the minimum number of changes to make is 2. We can choose 29 as the common element and change the other two elements.

This problem is from recently concluded Codechef contest. Click on this link to read the complete problem statement.

The solution is evident from the second example. This is the problem of finding the number of occurrences of a most frequently appearing number (mode) and subtracting it from the total number of elements.

There are at least two different approaches to implement the solution.
One is to sort the array (takes O(n log n) time) first and find the maximum frequency in O(n) time.
The other is a map based approach to store the frequencies of elements while iterating through all the elements and find the maximum among them. This will take O(n) time bust consumes O(n) extra space.

Below is the C++ implementation of the first strategy. Read my previous post for the implementation of map based method.

Minimum number of symbols to change to make a chain

Given a string containing the only symbols ‘+’ or ‘-‘, how do we find the minimum number of changes to transform it to a chain. A chain of length N is the sequence of alternative + and – symbols.

For example “+-+-+” is a chain of length 5.
Similarly “-+-+-+” is a chain of length 6.
This is a problem from recently concluded Codechef contest. Here is the link to the original problem.

Some examples of input and output are as follows

Input   Output
————–
–+      1
-+-      0
+-+–+   2

We can solve this problem as follows.
Observation:
Given the length of the sequence N, there are only two possible chains; One starting with – (-+-+….), and the other starting with + (+-+….).
So it is just enough to compare the input string to these two patterns and find the number of changes to make it a chain. Minimum of these two numbers gives us the answer.

For an example consider the input
+–++
Difference with +-+-+ is 2
Difference with -+-+- is 3
So the minimum number of changes to make it a chain is 2.

Here is the C++ code which implements the above.

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 to 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.
After finding such a number, we need to swap this with least number greater than it and appearing to the right of it.
For example consider the number 6276530
Scanning from right to left 2 is the first number smaller than it’s right.
3 is the least number greater than 2 and appearing to the right of it.
Swapping 2 and 3, we get 6376520
Even after swapping, the value can be minimized further.

We have to order all the digits after 3 in ascending order, whih results in 6302567

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

Inverse permutation problem

This problem is from code forces. If you want to try this problem, follow this link.
Here is the simplified problem statement.
Given a group of N friends, each one has given a gift to other friend or themselves. An input array is given which indicates from whom each one has received their gifts. We have to print an array which shows to whom each one has given their gifts.

For example,

Let us consider a group of 5 friends. The input array {3, 1, 5, 2, 4} indicates that the ‘1’ has received the gift from ‘3’, and ‘2’ has received the gift from ‘1’, and so on…

The output should be {2, 4, 1, 5, 3}. This indicates that 1 has given gift to 2, 2 has given gift to 4, and so on…

This problem of finding the inverse permutation of a given sequence. The solution is described below.

Let us allocate a separate array B for output. For each A[i], fill  B[A[i]] with i by iterating through all the elements. At the end of the iteration, B has the required answer. This method runs in O(n) time.

Here is the C++ implementation of the above approach.

Minimum AND of all subsets

This problem is from a recent contest on Hackerrank. If you want to solve this problem on your own, Click on this link.

Here is the problem statement:

Given array of size N, we have to find all the subsets of size > 2 of this array. Apply AND (bitwise &) on all the subsets. Print the minimum among those numbers.

For example let us consider the array {2, 8, 13, 7}, the minimum AND of any subset of size > 2 is 0 for subset {7,8}

0111
1000
—-&
0000

At first look, this problem looks like combinations problem. This solution tries to generate all the subsets of given array and find the minimum of all of them. This solution is of exponential time complexity and prohibitively expensive for larger inputs. But there is a trick to solve this problem.

Suppose that there exists some numbers whose AND is the minimum value among all the subsets. If we add any number of elements to this set, we get the same result. In the above example if add any element to {7,8} the result is no less than zero.

So the solution is to simply AND all the elements of the array!

Here is the Java solution.