Friday, May 30, 2014

Problem of candies: SPOJ

This problem is from SPOJ (Sphere Online Judge - A site to practice your problem solving skills). If you want to solve this problem on your own, please follow the link.

The simplified problem description is as follows. 


A teacher has n packets of candies of varying sizes. The problem is to find the number of candies to be moved from one packet to others to get equal number of candies in all packets.

For example consider 5 packets of candies having {1, 2, 3, 4, 5}  candies. the number of candies to be moved are 3.
 

Explanation: Take out 1 candy from 4 and add it to 2, and  take out 2 from 5 and add it to 1. Now every packet contains 3 candies.

There are cases where we can not make candies in each packet equal by moving any number of candies. We have to output -1 in that case.

The approach to solve this problem is as follows. 


First check if we can equal the packets in any way. How can we do this?
Sum all numbers and see if it is properly divided by the number of candies (integer average is possible). If it is possible we can proceed to divide the candies to make them equal.
 

The next problem is to find out the number of candies to be moved. Find the sum of all excess candies in each packet by comparing them with average number of candies.

This algorithm runs in O(n) time and O(1) space complexity.

Here is the accepted C++ code for this problem.

Tuesday, May 27, 2014

Number of matching pairs

This problem is from Codeforces. If you want to solve this problem on your own. Follow the link.

Following is the abridged(simplified) problem statement for the above problem.

Given an array containing values in the range [-10,10], find out how many number of matching pairs are possible?

A pair of numbers is said to be matching if one value is negative of the other (two zeros are also considered matching pair).

Consider the following examples.
[-6, 0, 1, 6, 0, -1] contains 3 matching pairs. Indices are (0,3), (1,4), (2,5)
[0, 0, 0, -5 ,3, 5] contains 4 matching pairs. Indices are (0,1), (0,2), (1,2), (3,5)

Since the problem is to find the count of matching pairs, we can always iterate through each possible pair and get the required answer. But this solution has a time complexity of O(n2).
        long long result = 0;
 for( i = 0; i < n-1 ; i++ )
 {
  for( j = i+1; j < n; j++ )
  {
   if(input[i] == -input[j])
    result++;
  }
 }
 cout << result << endl; 

Let us look at more efficient solution. Since the given values are in specific range, we can store the frequencies of each number in an array of 21 values ( the size of the range [-10,10] ).

Count(-10) will be stored at index 0
Count(-9) will be stored at index 1
...
Count(0) will be stored at index 10
...
Count(10) will be stored at index 20

Now, the number of matching pairs is the sum of Count(-x) * Count(x) for 1<=x<=10

The number of possible pairs for n zeros is n*(n-1)/2

Below is the implementation of this algorithm in C++.


Tuesday, May 20, 2014

Counting the number of leaf nodes in a binary tree

Given a binary tree, write a program to count the number of leaf nodes. A leaf node is a node which does not have left and right children.

For example consider the following binary tree.
It has 3 leaf nodes namely 1, 4 and 7.

The solution is simple. The number of leaf nodes of a binary tree rooted at R is the sum of leaf nodes in the left and sub trees. Using this property we can devise a simple recursive solution.

This can also be solved using iterative solution by traversing the binary tree using BFS (Breadth First Search) traversal.

The following C++ program shows both recursive and iterative implementations.


Monday, May 19, 2014

Finding the longest common prefix from given strings

Given a list of strings, how do we find the longest common prefix of all the strings?

For example consider { "Anomaly", "Anatomy", "Analog", "Angry" } the longest common prefix is "An".

This is a simple algorithm. Assume the first string as the longest common prefix, and try to match with the other strings and modify the prefix accordingly.

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

Friday, May 16, 2014

Deleting duplicate elements from a sorted linked list

Given a sorted linked list, how do we delete duplicate nodes from it?

This question is simple and straightforward, we take two pointers, current and next which points the adjacent nodes. In each iteration we compare the values at these two nodes, if they are equal, we delete the node pointed by next and advance the two pointers. Take a look at the following diagram to get better understanding.



Here is the C++ implementation

Thursday, May 15, 2014

Check if a number is the mirror image of itself

Given an arbitrarily large number, how to check if it is same as it's mirror image.

For example 101 is a mirror image of itself, where as 1811 is not a mirror image of itself.

This problem is from Hacker earth (A website for competitive programming). If you want to solve this problem on your own, and execute it on different possible test cases for it's correctness, follow this link. If you just want to know the solution, read on...

The solution is simple; the number should only contain the digits from the set {0,1,8} because they look the same when read in a mirror and it should also be a palindrome.

Here is the simple program to do this.

Wednesday, May 14, 2014

Splitting the linked list into two halves

Given a single linked list, how do we split it into two halves.

For example the list 1->2->3->4 should be divided into 1->2 and 3->4
If the length of the list is odd, add the extra node to first half; so 1->2->3 should be split to 1->2 and 3.

This problem can be efficiently solved using fast pointer, slow pointer mechanism explained in this post.

In this approach, the fast pointer moves two steps at a time where as the slow pointer moves one step at a time. By the time the fast pointer reaches the end of the list, slow pointer will be pointing to the end node of the first half. So we need to iterate the list only once.

Here is the C++ implementation.

Tuesday, May 13, 2014

Sorting a linked list using insertion sort

In one of my previous posts, we have seen how a linked list can be sorted using bubble sort approach. In this post we will see how we can sort a linked list using insertion sort algorithm. Like bubble sort this approach will also take O(n2) time.

Here is the strategy for linked list insertion sort. We maintain two lists; one sorted and another unsorted. Initially the sorted list is empty and the unsorted list will be the original list. In each iteration, we remove a node from the unsorted list and add it the sorted list in proper position. I re-used the procedure for inserting data into a sorted linked list from this post.

The following diagram should give you some understanding of the procedure.


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


Monday, May 12, 2014

Finding the right most occurence of an element in a sorted array

Given an array of sorted numbers, we have to find the right most occurrence of a number.

For example given an array {1,2,2,2,3}, the right most occurrence of 2 is at index 3 (0-based index).

This post is related to one of my previous posts ( Finding the left most occurrence in sorted array).

Similar to the above problem, we have to utilize binary search to solve this problem in O( log n ) time. Normal binary search returns any index which matches the given value. So, We have to customize binary search to find the right most instance.

In this modified approach, we have to check if we have already reached the end of the array or the middle is different from it's next element. If it's different, we return; otherwise we continue with right half of the array.

This function is similar C++ library implementation of upper_bound().

Here is the implementation in C++ which covers various test cases.


Friday, May 9, 2014

Separating the positive and negative integers

Given an array of integers which might contain both positive and negative integers, how do you modify the array such that all the positive and all the negative elements appear together.

For example consider the following array.

[36, -2, -18, 24, 42, -3, 6]

This should be transformed to some thing like

[-2, -18, -3, 24, 42, 36,6]

Here is the simple algorithm for this which runs in O(n) time and constant space.
  • Maintain an index for storing the negative elements (nIndex) and initialize it with zero.
  • Iterate through all the elements and if any of them is negative, swap it with the element at negative elements index (nIndex).
Here is the C++ implementation for this.


Thursday, May 8, 2014

Generating Gray codes

Gray code is a sequence of n-bit binary code where each pattern differs with the previous pattern by only one bit.

For example 2-bit gray code is shown below.

00
01
11
10

Now we have two write a program to generate such a sequence for the given value (n). One algorithm to generate gray code is explained below. An n-bit gray code can be generated from (n-1) bit gray code as follows.

1-bit gray code is obvious; it is 0,1.
2-bit gray code can be generated as follows. 
  • Expand the sequence by adding it's elements in reverse order (in this case 1, 0).
  • Prepend zeros to the first half and Ones to the second Half

 0  0
 0  1
 -----
 1  1
 1  0

3-bit gray code can be generated similarly.

0  00
0  01
0  11
0  10
------
1  10
1  11
1  01
1  00

Below is the implementation of this algorithm in C++.

Monday, May 5, 2014

Generating the counting sequence

Given an integer N, we have to generate the nth sequence of the following pattern.
  • "1"
  • "11" as the previous item contains one instance of 1.
  • "21" as the previous entry contains two 1's.
  • "1211" as the previous entry contains one 2 and one 1.
Following is the program which generates such a sequence. It runs in O(n*k) (where k is the length of the sequence) time and it utilizes only constant extra space.

Friday, May 2, 2014

Finding the integer square root of a number

How do we implement a function to find the integer square root of a number?

For example int_sqrt(4) = 2, int_sqrt(10) = 3. (We have to take floor of the actual square root)

A simple method is to iterate i from 1 to N/2 and keep checking until i2 < N, and whenever i2 >= N return i.

for( int i = 1; i <= N/2 ; i++ )
{
    if( i*i >= N )
        return i;
}


But this algorithm takes O(n) time. For large numbers this takes a lot of time. Any way to improve this further?

Binary search comes to our rescue. we start with the initial range [0, N]. In each iteration we check if mid2 <= N and (mid+1)2 >N. If this is satisfied, we return mid.

If mid2 > N, we confine our search to the left half; otherwise we search in the right half.



This implementation takes only O(log N) time.

Here is the C++ implementation. 


Thursday, May 1, 2014

Setting the matrix elements to zero

Given a matrix of size m * n, write a program to fill zero in ith row and jth column if matrix[i][j] is zero.

For example let us consider the following matrix.

  6 0 2
  1 3 4
  5 9 0
]

It should transform to the following.
  0 0 0
  1 0 0
  0 0 0
]

This problem looks simple at the first glance, but if we do not write the program carefully it results in the wrong output, typically marks all the elements in the matrix to zeros.

So a wrong solution can be iterate through all the elements of a matrix, and whenever we found a zero, set the corresponding rows and columns as zero.

This will have undesired effect. Since we are modifying the same matrix, it is possible that an unexplored element may be set to zero because of a zero in the same row or column. So it is not possible to solve this problem in just one iteration.

An inefficient, but correct solution could be to create a temporary matrix which is a copy of the original matrix, and mark the elements in temp instead of the original. This will take O(m*n) extra space.

Can we solve this more efficiently?

One possibility is to first go through all the elements in the matrix and store the zero containing row and column indices into two sets.

Then set all the elements in the corresponding rows and columns to zeros in the next step. This approach will only take O(m+n) space, an improvement over the previous. Any solution should take O(m*n) time because we have to iterate through all the elements of the matrix at least  once.

Here is the C++ function which takes the matrix as input and modify it.