Category Archives: CodeChef

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.

Maximum length of subarray with non-zero elements

Given an array of of size N, How do we find the longest sub-array with all non-zero elements?

For example consider the array {34, 0, 18, 3, 0, 1, 4, 5, 0, 12}, the longest sub-array with non-zero elements is 3 i.e {1,4,5}.

This problem is from Codechef. Follow this link to solve this problem in your own.

The solution is simple. The array contains non zero segments of numbers separated by one or more zeros. While traversing the elements, use two variables current_len, and max_len to track the length of the current segment and maximum segment length seen so far.

Here is the Python implementation of the above. This runs in O(n) time.

GCD queries

This problem is from Codechef January challenge. Click on the link to try this problem on your own.

The problem statement is as follows.

Given an array of size N and two indices L and R. We need to find the GCD (Greatest Common Divisor) of all the array elements except in the range [L,R]. The indices start from 1. We have to answer multiple queries of this type.

An obvious solution could be to find the GCD of all the elements from [1,L-1] and [R+1,N] and find the GCD between these two numbers. But this solution is O(n) for each query in the worst case.

First let us pre-process these array to gain some efficiency. Define cumulative GCD as follows.

If A is an array of N elements, the cumulative GCD of an array A from left to right consists of the following.

cgcd[0] = A[0]
cgcd[1] = gcd(cgcd[0], A[1])
cgcd[2] = gcd(cgcd[1], A[2])
…. and so on

Lets create an array fgcd which stores the cumulative GCD from left to right. Also create an array bgcd which stores the cumulative GCD from right to left.

After calculating these values, answering the query is simply finding the GCD of fgcd(L-1) and bgcd(R+1).

Here is the C++ implementation of the above. This each query takes only O(1) time and it takes O(n) extra space to store the pre-processed values.

Permutation cycles – Code chef problem

This is a problem from CodeChef. Follow this link if you want to try this problem on your own.

Given a permutation of numbers from 1 to N. You can walk through the permutation to find cycles in it.
Here is how you can do it. Consider the permutation {3, 5, 2, 1, 4, 6}

Start with the first number at index 1, it contains 3.
Go to index 3, it contains 2.
Go to index 2, it contains 5.
Go to index 5, it contains 4.
Go to index 4, it contains 1.
Here we come back to index 1 again. This completes a cycle {1,3,2,5,4,1}
And if we start with 6, we end up there itself. This is a one element cycle {6,6}.

Similarly the permutation {3,2,1,5,4,6} contains 4 such cycles
1 3 1
2 2
4 5 4
6 6

The problem is given a permutation as input, you have to print the number of cycles and the cycles also.
 

To solve this problem we can maintain a visited array to store whether the element is already explored or not. Run a loop until you find a unvisited element, and start walking to find the cycle.
This is a purely an implementation challenge and does not need any algorithmic thinking.

Here is the simple C++ implementation.

Birthday candles – Codechef problem

This is from CodeChef practice problems. Follow this link to try on your own!

Here is the simplified problem statement.

A number of candles are given each of them labelled with the digit 0-9. We have to find the minimum positive number that can not be formed with the given candles. 

The input is given as an array of size 10.
Array[0] indicates the number of ‘0’ candles
Array[1] indicates the number of ‘1’ candles and so on upto Array[9].

For example:

  • For input 1 6 2 1 1 2 1 1 2 0, the output is 9. Since we have zero ‘9’ candles, the minimum number that can not be formed is 9.
  • For input 2 3 2 2 1 2 1 1 1 1, the output is 44; because we have only one ‘4’ candle.
  • For input 0 1 1 1 1 1 1 1 1 1, the output is 10;  We have one ‘1’ candle so we can not form 10 with the given candles.
Note: Even though we don’t have any ‘0’ candles, the minimum number is not 0 because the answer should be a positive number.

Here is the approach to solve this problem.

  • Identify the left most digit with minimum count. It can be ‘0’ also.
  • Form a number by repeating the minimum digit  (count+1) times
  • A special case occurs when ‘0’ candle has minimum count, we have to prefix ‘1’ to it, as we can not have all zeros.
  • One more special case is when 0 and some other digit has the same minimum count, we have to consider the left most non-zero digit. Take a look at the following case to understand the situation. 
    • 2  3  4   7  6  2  8  3  5  9
    • Both ‘0’ and ‘5’ has the count of 2. If we consider zero, the output becomes 1000 according to the above algorithm. If we consider ‘5’, the output becomes 555. Since 555 < 1000; the answer should be 555.
Here is the C++ code for this problem.