Friday, April 25, 2014

Computing the power of a given number

Given a base and it's exponent, how do we efficiently evaluate it?
In other way, how do implement a pow() function which is typically provided by a library.

For example 210 = 1024.

The simplest method that comes to our mind is multiply the base with 1 in a loop for exponent times.

double result = 1;
for( i = 0; i < exp; i++ )
    result = result*base;

This method runs in O(n) time complexity where n is the exponent. 

We can make this efficient by using Divide and Conquer technique. Considering the above example, 210 can be calculated as follows.

210 = 25 * 25
25 = 22 * 22
22 = 21 * 21

In each step we avoid computing half of the product which can save us time.
Here is the C++ function to calculate the result. In this function I have handled negative exponents also. This method runs in O( log n) complexity.

  double pow(double x, int n) 
        int absn = abs(n);

        if( absn == 0 )
            return 1.0;

        else if( absn == 1)
            return (n < 0) ? (1/x) : x;
        double temp = pow(x, absn/2);
        double result;
        if( absn % 2 == 0 )
            result = temp*temp;
           result = temp*temp*x;
        return ( n < 0 )? (1/result) : result;

Monday, April 21, 2014

Counting the number of perfect squares in a given range

Given a range of numbers, how do we count the number of perfect squares?

This problem is posted on Hackerrank as part of 20/20 Hack March 2014.

If you do not want to read the solution and you want to solve the problem on your own, Click on the link. If you want to know the solution for the problem, read on...

For example, if the given range is [1,5] the number of perfect squares in this range is 2 (including the lower and upper bounds)
1= 12 and 4 = 22

Simple solution:
The obvious solution is to check if each number in the given range is a perfect square or not. This runs O(n) time. For a small range of numbers, this works fine. But for a big range, this takes a lot of time.

Can we improve this solution further?

We can improve this as follows.

First we find the square roots of lower bound and and upper bounds. The difference between them gives the required number.

For example consider the range [2,11]

sqrt(2) = 1.414
sqrt(11) = 3.316

If you round them off, and take the difference (3-1), it is 2 which is the required answer.

However we have to handle two special cases.

Case 1: Lower and upper bounds are same.
For example [4, 4]. In this case we have to check if the given number is a perfect square. If it is,  output 1, otherwise output 0.

Case 2: If the lower bound is a perfect square.
In this case, we have to add 1 to the diff of square roots. 

For example consider [4, 20]; rounded square roots are [2, 4]; the diff is 2. But there are 3 perfect squares in the given range (4, 9, 16).

In all the remaining cases, the number of perfect squares is the difference of the square roots.

Here is the C++ implementation for this problem.

Tuesday, April 15, 2014

Deleting duplicate numbers from a sorted array

Given a sorted array of numbers, how to delete the duplicate numbers in it?

We have to write a function to modify the existing array without using any extra space and return the new length.

The solution to this problem is similar to that of "Deleting all instances of a particular number from a given array".

We have two indices, one which keeps track of the unique elements and the other iterates through all the elements. Each time we visit an element, we check if it matches with the recently added unique elements. If does not match, we add it to the unique elements, otherwise we ignore that element and move on to the next.

This approach runs in O(n) time and O(1) space. Moreover it iterates over the array only once.

Here is the C++ program which implements this.

Monday, April 14, 2014

Google codejam 2014 - Qualification Round Problem - Magic trick

The following problem is from the Google code jam 2014 qualification round.  Head-over there to read the complete problem description.

The problem description is as follows.

A magician starts by arranging 16 cards in a square grid: 4 rows of cards, with 4 cards in each row. Each card has a different number from 1 to 16 written on the side that is showing. Next, the magician asks a volunteer to choose a card, and to tell him which row that card is in.
Finally, the magician arranges the 16 cards in a square grid again, possibly in a different order. Once again, he asks the volunteer which row her card is in. With only the answers to these two questions, the magician then correctly determines which card the volunteer chose.

We have to write a program to help you understand the magician's technique. The program will be given the two arrangements of the cards, and the volunteer's answers to the two questions: the row number of the selected card in the first arrangement, and the row number of the selected card in the second arrangement. The rows are numbered 1 to 4 from top to bottom.
Your program should determine which card the volunteer chose; or if there is more than one card the volunteer might have chosen (the magician did a bad job); or if there's no card consistent with the volunteer's answers (the volunteer cheated). 

This problem is simply finding the intersection elements of the rows chosen by the volunteer in the first, and second arrangements. If the intersection contains a single element, then magician can correctly guess the element. If the intersection contains zero elements, volunteer has cheated. If it contains more than one element, then the magician is bad at arranging the cards.

Here is the C++ code to solve this problem.

Friday, April 11, 2014

C++ STL Algorithms - Sort - Part-2

In the last post, the basic use of STL sort() method is explained. In this post, I will discuss some more options available with this method.

We have seen in the previous post that sort takes the beginning and ending of the array as arguments.

sort( array.begin(), array.end() );

In addition to those parameters, it can also take a third parameter (predicate) which decides the ordering of the elements. If we do not pass the third parameter, the default ordering is assumed. For integer data types such as int,  float, char etc, ascending order is followed. For strings alphabetical order is followed. To sort an array of integers in descending order, simply call the sort routine like this.

sort( array.begin(), array.end(), greater<int>() );

std::greater is a built in comparator object provided by STL. we have to pass the type of objects to be sorted. similarly we have std::less, std::less_equal, std::greater_equal etc...

So far we are sorting only built in data types such as int, double and library class string. We can also sort objects of user defined classes also.

For example in the following program I have defined a class called Pair, which contains two fields. To sort user defined/custom data types we also have to write the comparison functions to decide the ordering. We can sort Pairs either according to the first value or the second value. I have written two comparator functions and passed these while sorting. 

Here is the code which explains these concepts.

Thursday, April 10, 2014

C++ STL Algorithms - Sort- Part-1

Sorting is one of the most widely used algorithmic primitive in programming. 

C++ Standard Template Library (STL) provides an efficient implementation of the sort algorithm. It is always better to use this algorithm instead of writing our own implementation because of the following benefits.
  • It's performance would surely be better than your own implementation. It's implementation conforms to the C++ standard bench marks and tested by a lot of people. The library version takes advantage of the combination of multiple sorting algorithms to achieve the maximum performance.
  • Writing our own version is error prone and bugs can easily be overlooked.
Here is a simple program which demonstrates the use of library sort() routine to sort an array as well as a vector. 

The sort() method at the minimum requires two parameters; the start of the list and the end of the list. Note that the end should always point to one element beyond the last element. It sorts the element ranging between [begin, end) i.e starting from the first element till the end excluding the last.

For arrays, we know that the array name indicates the address of the first element. If we add the size of the array to the starting address, we get the address of next to last element.

For vectors, there are built-in methods begin() and end() to indicate the starting and ending elements.

    #include <iostream>
    #include <algorithm> //included for using sort
    #include <vector> 
    #include <string>
    using namespace std;
    int main()
     int arr[5] = {9, 6, 36, 24, 42};
     int arrSize = sizeof(arr)/sizeof(arr[0]);
     sort(arr, arr+arrSize); //sorts the given numbers in ascending order
     for( int i=0; i < arrSize; i++ )
      cout << arr[i] << " ";
     cout << endl;
     vector<string> names;
     sort( names.begin(), names.end());//sorts the names in alphabetical order
     for( int i = 0; i < names.size(); i++ )
      cout << names[i] << " ";
     cout << endl;
     return 0;

    Monday, April 7, 2014

    Size of an empty object in C++

    What is the size of an empty object in C++?
    This is one of the most frequently asked questions on forums.

    For example consider the following code snippet.

    class A

    A aOb;
    cout << sizeof(aOb);

    The size of an empty object is not zero to ensure that the addresses of two different objects will be different. For the same reason, "new" always returns pointers to distinct objects.

    On most of the compilers, it would return 1 byte. Even if the class contains only member functions and no data members, this is applicable.

    However if the class contains at least one virtual method, the sizeof() operator returns 4 bytes on a typical compiler. This is so because every class with at least one virtual function has a pointer to vtable stored which is helpful in dynamic binding.

    class B
       virtual void func()

    B b;
    cout << sizeof(b);

    Friday, April 4, 2014

    Check if two binary trees are identical

    Given two binary tress, how do we check if they are identical in structure, and  contents?

    For example the following two binary trees are identical.
    We can solve this problem using recursion effectively. The function checks if the root element is equal and use the same function to check if it's left and right sub-trees are also identical. If it is we return true. 

    Here is the C++ function.

    bool isSameTree(TreeNode *p, TreeNode *q) {
            if( p && q )
                if( p->val != q->val )
                    return false;
                return ( isSameTree(p->left,q->left) && isSameTree(p->right,q->right) );
            else if( !p && !q)
                return true;
                return false;