Category Archives: Adhoc

Edit distance 1

Given two strings, how do we check if their edit distance is 1?

Edit distance is defined as the number of characters that needs to be modified, inserted or deleted from one string to transform into the other string.

For example let us consider two strings “java”, “lava” they both differ by just one character. we can change the first character in either of them to make them equal.

Similarly, the words “at”, “bat” also have an edit distance of 1 because either we can add “b” to the first string, or delete “b” from the second string to make them euqal.

By looking at the problem statement, one can think of a dynamic programming solution which takes O(n^2) time. However, it would an over kill to solve this problem.

Let’s observe some thing. Two strings can not have an edit distance of 1 if their lengths differ by more than 1 characters.

So we can simplify our approach to work on the two use cases.
which are either of equal length, or
one string longer than the other by just one character.

Lets see some representative test cases we need to handle.

(“abc”, “bc”), (“abc”, “ab”), (“string”, “sxring”), (“algorithm”, “algoritm”) etc.

If the two strings are equal, we just count the number of mismatches at each index in the two strings.

Otherwise, we check if the shorter string is a sub-sequence of the longer string except one character. In this case we calculate the number matching characters which should be equal to the length of the shorter string.

Here is the Java implementation of the above approach. The time complexity would be linear O(n).

Maximum number of contiguous ones with K zeros

Given an array of size N, containing only 0’s and 1’s, and a number K, what is the maximum length of the sub-array with contiguous 1’s with at most K 0’s?

For example consider the array

A = [1, 1, 0, 1, 0, 0, 1], K = 2, the maximum length is 5. i.e the sub-array A[0:4]

This problem can be solved using sliding window algorithm. Take two indexes front and back which defines a window. We keep expanding the window by incrementing the back index as long as the window contains less than or equal to K zeros. That means, at any time, the window contains at most K 0’s. If it exceeds K, we increment the front index to reduce the number of zeros to K. Continue this procedure until the back index reaches the end of the array. We also keep track of the largest window during this process.

This algorithm takes O(n) time.

Here is the C++ code.

Problem Source: SPOJ REPROAD

Maximum elements of array

Given an array A of size N, We want to perform several iterations as described below.

Select any index i such that 1 <= i <= N, Mark A[i] = 0, move left by filling each element one greater than it’s right
Similarly move right, and fill each element which is one greater than it’s left.

For example consider an array of length 5, and we choose the index 3, the array would be

A = [2, 1, 0, 1, 2]

If we perform several iterations by choosing different indexes each time,
we have to output the maximum number, each element can get during all the iterations.

Consider that we repeat the procedure for the above array with Index 2
A = [1, 0, 1, 2, 3]

So after two iterations at indexes 2, and 3, maximum elements would be
MAX_A = [2, 1, 1, 2, 3]

To find MAX_A, at first, it looks like we need to repeat the procedure m times for m indexes,
which leads to O(m*n) complexity solution.

What will be the maximum number an element can get? N-1
How? Lets consider the same array as above, choose index 1, the array would be
A = [0, 1, 2, 3, 4]
Choose index 5, the array would be
A = [4, 3, 2, 1, 0]

So it is enough to perform the iteration with the left most and right most indexes,
the maximum element at each index i would be max( abs(i-left), abs(i-right))

So the time complexity will be O(n).

Here is the C++ code for the same.

Problem Source: The Army – Codechef

Partial sum queries

Given an array of numbers, we need to answer many queries of the form Sum(A[i]...A[j]),

For example, let the array be [15, 6, 1, 12, 7, 4, 10]

Sum(A[1:3]) = 15+6+1 = 22
Sum(A[4:6]) = 12+7+4 = 23
...

The simplest solution is to iterate through the elements from i to j and return the sum.
However this will be good enough if we have a small number of queries. What if we need to run many queries?
In worst case this is takes O(n2) time.

How can we reduce the time complexity?
If we pre-process the array by calculating the prefix array, we can answer each query in O(1) time.

For the above example calculate the prefix array by using the formula Prefix[i] = Prefix[i-1]+A[i]

Prefix = [15, 21, 22, 34, 41, 45, 55]

Now the partial sums can be calculated as follows

Sum(A[i:j]) = Prefix[j] - Prefix[i-1] if i > 1
= Prefix[j] if i=1

Here is the Java function which implements the above

long partialSum(int []prefixArr, int start, int end) {
long sum = arr[end];
if( start > 0)
sum -= arr[start-1];
return sum;
}

Counting pairs in array

Given an array A of distinct numbers, how to count the number of pairs (i,j) such that
A[i] < A[j]

For example, let us consider A = [2, 1, 3]
the pairs are (1,2), (1,3), (2,3). So there are 3 pairs.
Similarly for A = [10, 6, 9, 2], there are 6 pairs

This problem was originally appeared in Codechef.

One straight forward solution is to loop through all possible pairs and count them.
But this has O(n2) time complexity.
We actually don’t need to count all the pairs because the elements are distinct.
Suppose we arrange the elements in sorted order

A = [1, 2, 3]
then the pairs are (1, 2), (1,3), (2,3)
A = [2, 6, 9, 10]
the pairs are (2, 6), (2,9), (2,10), (6, 9), (6, 10), (9,10)

If there are n elements in an array, there will be n*(n-1) pairs. Since the all the elements are unique, half of them satisfies the given property.

So the answer will be n*(n-1)/2

Finding the number in a shuffled array

Given an array [1, 2, 3,…N], we apply a series of reversal operations on different range of indices [L,R].
How to find out the position of a number after these operations are applied?

For example consider an array of 5 numbers [1, 2, 3, 4, 5] and the number 2.

Reverse elements between 1, and 3, the array becomes [3, 2, 1, 4, 5]
Reverse elements between 3, and 5, the array becomes [3, 2, 5, 4, 1]
Reverse elements between 2, and 5, the array becomes [3, 1, 4, 5, 2]

So the final position of 2 is 5.

This problem was originally appeared in Codechef.

If we want to track just one number, we need not perform reversal operations everytime. This process takes O(n^2) time in worst case.

As we perform the reversal operations, we just need to track what is the new position of target number.

How do we track the position?
Consider the positions L = left, R= right, C = current and the distance between L and C is X,
After we reverse the elements between L, R, C will be placed x steps before R

C – L = R – X
X = R + L – C
The new position of C will be (R+L-C)
The position of C will not be altered if we are reversing the part which includes C.

Here is the C++ code for the same which runs in O(n) time.

Odd number out

Given an array of numbers which contains all even numbers except one, or all add numbers except one.
How do you find the different number?

For example consider the array [1, 2, 3, 5, 9], 2 is the different number.
Similarly in the array [10, 6, 7, 24, 36], 7 is the different number.

This problem was originally appeared on Codeforces.

This is a simple implementation problem, which can be solved in one iteration.
When we are reading numbers, just keep track of the following information.

  • first even index
  • first odd index
  • even number count

At the end, check if the even number count is 1, If it is, then print first even index, otherwise print first odd index.
Here is the C++ code for this.

Minimum number of squares formed from a rectangle

Given a rectangle of some length and width, How do you divide them into minimum number of squares? This is a problem from Codechef.

For example give a rectangle of size 2 x 4, we can make them into two squares of 2 x 2.
Similarly a rectangle of size 3 x 7, can only be divided into 21 squares each of size 1 x 1.

So what is the logic behind this?
The length and width should be divided in same equal parts, and that part should as greater as possible. So we have to find the GCD(Greatest Common Divisor) of the length and width of the rectangle. Then the minimum number of squares can be calculated by
l/g * w/g. where l = length, w = width, g = GCD(l,w)

Here is the C++ code which implements this.

XOR of all sub arrays

Given an array of elements, how do we find the XOR of each sub-array and XOR of those results?

For example let us consider the array [1, 2, 3], all possible sub-arrays are

XOR[1] = 1
XOR[1, 2] = 1 ^ 2 = 3
XOR[1, 2, 3] = 1 ^ 2 ^ 3 = 0
XOR[2] = 2
XOR[2, 3] = 2 ^ 3 = 1
XOR[3] = 3

And the result XOR[1, 3, 0, 2, 1, 3] = 2.

Brute force solution:
From the above example, you can see that an array of 3 elements has 6 sub-arrays. Similarly you can verify the count by listing the sub-arrays for N= 4 and N= 5. In general, for an array of N elements there will be N*(N+1)/2 sub-arrays. We have to calculate the XOR of each of these sub arrays. So an outline of algorithm can be as follows.

for i in range(1,N)
   for j in range(i,N)
      for k in range(i,j)
         x = XOR(x,A[k])

This is clearly not en efficient solution and take O(n3) time. We can also use dynamic programming to pre-calculate the XOR values so that time can be reduced to O(n2). But is there any better method?

Efficient Solution:
Observe how many times, each element appear in all the sub arrays. In the above example
1 – 3 times
2 – 4 times
3 – 3 times

Consider 0-index, in general A[i] appears (N-i)*(i+1) times. 

We also know that if an element is XOR’ed with itself even number of times, it is zeroed out. and if it is odd number of times, it remains the same. For example

V ^ V ^ V ^ V = 0
V ^ V ^ V = V

Consider the two cases when the number of elements N is Even or Odd
N is even, each element appear even number of times:

N= 2, 
A[0] – 2 times
A[1] – 2 times
N = 4,
A[0] – 4 times
A[1] – 6 times
A[2] – 6 times
A[3] – 4 times

This is because either (N-i) or (i+1) is always even for all values of i.
Hence, for an array of even length, the XOR of all sub-array becomes Zero.

N is odd, the elements at even index will only prevail in the final result.

The following C++ program implements the above approach. The time complexity of this algorithm is O(n).