Category Archives: C++

Type casting in C++ – Part 1

Type casting frequently arises in real life programming. This post concentrates on type conversion of fundamental data types. Type casting is the process of converting from one data type to another. In C++, type casting is automatic in some situations. These are called implicit conversions.

For example
char c = ‘A’;
int ch_code = c;
short s_val = 1024;
int i_val = s_val;
Here the value of “c” is automatically promoted to an int as we are assigning a smaller type into a bigger type. The second case is also similar. This is also called a promotion. There is no truncation in these cases. Other examples of this type include int to float/double, float to double, boolean to int etc…
Implicit type conversion also happen when a bigger type is assigned to smaller type. This might result in truncation/data loss if the source data which cannot fit in the destination type. Some compilers gives a warning when we are using such a conversion. This can be avoided by explicit conversion.
int ch_code = 97;
char ch = ch_code; // no data loss as 97 is within the range of char type; represents the character ‘a’
float pi = 3.14159;
int i_pi = (int)pi; //decimal part is truncated; explicit type conversion
If the truncated integer value is bigger than the integer type, the behavior is undefined.

If a negative integer type is converted to a unsigned type, the resulting value would be 2’s compliment bit representation interpreted as a positive integer.

For example the following code
short x = -32768;
unsigned short y = x;
Assigns a value of 32768 to y. The least value has become the greatest value in this case.

If you are converting an integer to boolean type, all non-zero value will be converted to 1 including negative and positive values which are considered true. 0 is considered false.
int x = -10;
bool b = x; // b is assigned 1, i.e true
x = 10;
b = x; //b is 1 here also
x = 0;
b = x; //b is 0,i.e false

In the later posts, we will look at type conversions between non fundamental data types like pointers and classes.

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.

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.


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;
    names.push_back("Himalayas");
    names.push_back("Alphs");
    names.push_back("Vindhya");
    names.push_back("Aravali");

    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;

    }

    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);

    Generating a pascal triangle

    In this post, we will write a program to generate a pascal triangle of given height.
    For example, Pascal triangle of height 5 is shown below
    1
    1 1
    1 2 1
    1 3 3 1
    1 4 6 4 1
    The idea behind Pascal triangle is that each element in a row is the sum of left and right elements in the previous row. If the previous row does not contain left/right, they are considered as 0. The same idea is used to write simple program like the following.


    Removing all instances of a number in an array

    Given an array of arbitrary numbers and a given value, how do we write a program to delete all instances of the given value?
    For example, if the input array is [23, 9, 18, 9, 6, 47, 3, 6] and the element to be deleted is 9. The result array should be [23, 18, 6, 47, 3, 6]. Result array size is 6. We don’t care about the elements beyond this size.
    The restriction is to modify the input array itself (should not use extra memory – constant extra space) and return the new length of the result array.
    This problem can be solved as follows.
     
    We maintain two indices; one to track the elements of resultant array (result index), and another to iterate through all the elements. While iterating through each element using second index, if we see an element which is not equal to the target element, we can copy it to the same array from the beginning, and increment the result index.

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

    Here is the simple implementation in C++.

    Finding an element in a circularly sorted array

    Given a circularly sorted array, how to search for an element efficiently?

    For example let us consider the array [12, 15, 6, 8, 10], the element 8 is found at index 3.


    Since the array is sorted but rotated, we can expect it to be solved using the binary search technique.

    We can design an algorithm like this. We first check if the middle element equals the target element. If so, we return the mid.

    Otherwise we check to see if the left half is sorted or right half is sorted. In any case only one portion will be sorted. We have to narrow down our search based on the range of elements which the target belongs to .

               if( arr[low] <= arr[mid]) //left half is sorted
            {
                //If target lies in first half

                if( s >= arr[low] && s < arr[mid] )
                    high = mid – 1;
                else
                    low = mid + 1; // narrow down to right half
            }
            else // Right half is sorted
            {
                if( s > arr[mid] && s <= arr[high] )
                    low = mid + 1;
                else
                    high = mid – 1;
            }

    Here is the iterative implementation of the above algorithm. This algorithm runs in O( log n ) time complexity.

     

    Finding the magic index of the array

    Given a sorted array of distinct values, how do you find an index i such that array[i] = i? Let us call it a magic index.

    For example if the given array is [-23, -4, 2, 19, 56]. Element 2 is found at array[2]. So the output is 2.
    If there no such element in the array we can return -1.

    Very obvious approach is to do a linear search to find such an element. This will take O(n) in the worst case.

    Since the array is sorted, we can modify the binary search to solve this problem more efficiently.

    Using binary search we first visit the middle element of the array. 
    If array[mid] = mid, simply return mid.
    If mid > array[mid], there is no way to find magic index on the left half. Think of an example
    [-10, -3, 0, 2, 4, 8]. Here middle index = 3, array[3] = 2.   If we go back from index 3, we can only find elements less than 2 because the array is sorted and it has distinct elements. Hence we can safely skip the left half and proceed to search the right half effectively reducing your search space by half.

    In the same way, if mid < array[mid], we can ignore the right half and search only left half of the array.

    C++ implementation of the above algorithm is given below.

    Finding the number of pairs in array with given difference

    Given an array of N distinct values, how to find the number of pairs with a difference of K?
    For example, given an array [3, 1, 4, 2, 5] and K= 2, there are 3 pairs with a difference of 2. Namely {1,3}, {2,4}, {3,5}. 

    One obvious solution could be to examine each possible pair and count the number of pairs with the given difference. (This is similar to my previous post). But this algorithm runs in O(n2) time. If you are solving it in a competition, you most probably get a Time Limit Exceeded (TLE) error.

    Let us look at more efficient solutions.

    Solution 1:

    Sort the array first using any algorithm like Quick sort or Merge sort or Heap sort. This takes O( n log n ) time. The algorithm is as follows.

    1. Take two indices and point them to first and second elements.
    2. Repeat the following steps until any index reaches the end of the array
      1. If the difference matches, increment count and increment both the indices
      2. If the difference is less than required value,  increment second index
      3. Otherwise increment first index.

    The algorithm takes O(n) time. The overall time complexity is O(n log n). It does not take any extra space.

    Solution 2:

    Using additional data structure like a set or a map. 

    1. Store all the array elements into a set.
    2. For each element in the array do the following.
      1. If the set contains array[i]+diff or array[i]-diff, increment the diff count. 
      2. Remove array[i] from the set.
    This approach runs in O(n) time but takes O(n) additional space for the set.