Category Archives: C++

Minimum coin change problem

Given a set of denominations and an amount, how do we minimize the number of coins to make up the given amount?
Let us consider the set of denominations {1,3,4}. Also assume that we have infinite supply of coins for each denomination. To make change for 6, we can have three combinations
{1,1,4}
{1,1,1,3}
{3,3}
The minimum number of coins to make change for 6 is ‘2‘.
This problem can be efficiently solved using dynamic programming approach. Let us formulate the problem in terms of it’s sub-problems.
Let the amount be T and the given denominations are {d1,d2,…dn}. Create an array of size (T+1) denoted by MC[].
MC[K] denotes the minimum number coins required for amount K. It can be defined as follows

Min{ MC[K-d1], MC[K-d2],…MC[K-dn] } + 1 
This means that we can find the solution of a problem from it’s sub-problems and it has optimal sub-structure property suggesting the dynamic programming solution. 

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

Valera and Plates – Code forces (Round #216) problem

In this post, we discuss a simple implementation problem from the recently concluded Code forces programming round. The problem description is given below.

Valera is a lazy student. He has m clean bowls and k clean plates.
Valera has made an eating plan for the next n days. As Valera is lazy, he will eat exactly one dish per day. At that, in order to eat a dish, he needs exactly one clean plate or bowl. We know that Valera can cook only two types of dishes. He can eat dishes of the first type from bowls and dishes of the second type from either bowls or plates.
When Valera finishes eating, he leaves a dirty plate/bowl behind. His life philosophy doesn’t let him eat from dirty kitchenware. So sometimes he needs to wash his plate/bowl before eating. Find the minimum number of times Valera will need to wash a plate/bowl, if he acts optimally.
Input

The first line of the input contains three integers n, m, k (1 ≤ n, m, k ≤ 1000) — the number of the planned days, the number of clean bowls and the number of clean plates.
The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 2). If ai equals one, then on day i Valera will eat a first type dish. If ai equals two, then on day i Valera will eat a second type dish.

Output

Print a single integer — the minimum number of times Valera will need to wash a plate/bowl.

Sample test(s)
Input
3 1 1
1 2 1
Output
1
Input
4 3 1
1 1 1 1
Output
1
Input
3 1 2
2 2 2
Output
0
Input
8 2 2
1 2 1 2 1 2 1 2
Output
4
Explanation:

In the first sample Valera will wash a bowl only on the third day, so the answer is one.

In the second sample, Valera will have the first type of the dish during all four days, and since there are only three bowls, he will wash a bowl exactly once.

In the third sample, Valera will have the second type of dish for all three days, and as they can be eaten from either a plate or a bowl, he will never need to wash a plate/bowl.

Solution:
We first count how many times he makes type-1 dish and type-2 dish. He eats type-1 dishes only in bowls. 

We first calculate how many cleanings to eat first dish. Let us denote cb as the number of clean bowls and cp as the number of clean plates. Let type1 be the number of first dish type2 be the number of second dish in his plan.

If type1 > cb, We need (type1-cb) cleanings and we are left with 0 clean bowls. Otherwise we need no cleanings , we are left with (cb-type1) bowls.

We add the clean bowls from the previous step to number of clean plates. 
cbp = cb + cp.
If type2 > cbp then we need typ2-cbp cleanings otherwise zero.

Here is the implementation in C++.


Maximum numbers in a sliding window

Given an array of N values and a value K, Write a program to print the maximum of all the sliding windows (sub-array) of size K.
For example let us consider the following array as input 
[4, 5, 3, 2, 6, 1, 2, 3, 8, 4]
Let as take the sliding window of size 3. The output will be as follows
Sliding Window           Maximum
———————————
[4, 5, 3]                  5
[5, 3, 2]                  5
[3, 2, 6]                  6
[2, 6, 1]                  6
[6, 1, 2]                  6
[1, 2, 3]                  3
[2, 3, 8]                  8
[3, 8, 4]                  8
The brute force solution can be to find the maximum of each sliding window when we move forward by one element. In an array of size n, there will be (n-k+1) sliding windows of size k. For each window, it takes O(k) time to find the maximum. So, it’s time complexity is O( (n-k+1)* k ) ~= O(n*k).

Can we do better than this?

Yes! this problem can be efficiently solved using the dequeue data structure. Dequeue data structure supports inserting and deleting the elements at both ends of the queue via push_back(), pop_back(), push_front() and pop_front(). Here is how the algorithm works. 

We maintain the indices of elements of the current window in a dequeue. We also make sure that the maximum element always appear in the front of the queue. The new element is added at the back of the queue by deleting all the smaller elements before it. We will also delete the element just went out of scope (previous window element). In each iteration we print the front of the queue which is maximum.

Here is the C++ implementation of this algorithm.


Inserting an element into sorted linked list

Given a sorted linked list write a program to insert data into it’s correct position. 
For example consider the following linked list

1 -> 3 -> 4 -> 5 

Inserting 2 should change the list to

1 -> 2 -> 3 -> 4 -> 5
Inserting 0 should change it to
0 -> 1 -> 2 -> 3 -> 4 ->5
Inserting 6 should change it to
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6. 
The three examples indicate three different cases to be considered while inserting into a sorted linked list.
Case 1: List can be empty or new element is added as the first element
Case 2: New element can be inserted anywhere in the middle of the linked list
Case 3: New element is added as the last element.

The following diagram illustrates the insert process.



In the following C++ program case 1 is handled in one block and case 2 and 3 are handled in the last block.


Finding K-size sub array with minimum sum

Given an array of size N and a number K. We have to find the sub-array of size K such that the sum of it’s elements is minimum among all K-size sub arrays.
For example Let us consider the following array of size 10. 
{1, 2, 1, 3, 1, 1, 1, 4, 2, 3}
The smallest sub-array of size 3 is {1, 1, 1} which starts at the index 4 (0-based index).

We can use the following algorithm.

We calculate the sum of first K numbers initially and assume that this is the minimum sum and the index is 0. We maintain a variable to track the running sum of K values.

When we move the sliding window by one element, we subtract the previous element add the current element to the running sum. Then we update the minimum sum if the latest sum is less than minimum sum.

This procedure is repeated till the sliding window reaches the end of the array.

Here is the C++ implementation.


Number of bits to change from one number to other

Given two numbers, calculate the number of bits required to change from one number to the other.
For example 12 in binary can be represented as 1100. 15 is represented as 1111. We need to change two bits to convert one number from the other as the last two bits are different.
We can find out the difference bits as follows. We first find out the XOR of two numbers. This gives us a bit pattern in which there is a set bit, if two bits differ. Then we can calculate the number of set bits in the XOR which gives the required answer.
Here is C++ code for this.

Pair swapping in a linked list

Given a singly linked list, we have to swap the adjacent nodes in it.
For example some input/output samples are given below
Input                              output
————————————————-
1->2->3->4->X                      2->1->4->3->X
1->2->3->4->5->X                   2->1->4->3->5->X
1->X                               1->X
The algorithm is very simple. We have to move pair by pair and swap the data part of each pair. 

Here is the C++ code for this.

Printing the prime factorization of a given number

How do we write a program to find the prime factorization of a given number?
For example prime factorization for 18 can written as 2 * 3 * 3 or 2 * 3 ^ 2.
For any number there is only one possible prime factorization. 
An efficient algorithm can be given as follows. we run a loop with i ranging from 2 to sqrt(n). In each iteration, we try to reduce the number by dividing it with i as many times as possible. As we examined in the last post, we can find all the factors of a number by checking the divisibility of it from 1 to square root of n itself.
Here is the C++ code to do this.

constant pointers and pointer to constant

In this post we talk a little bit about the constant pointers and pointer to a constant and the difference between them.
In C programming, pointer is a crucial concept and it is always good to have a clear understanding of the fundamentals.
Constant pointers:
Constant pointer as the name indicates is a pointer whose value can not be changed. In another way, once a pointer is initialized with an address of a variable, it can not point to any other variable further. We can also say it is a read-only pointer. For example, take a look the following code snippet.
int var1 = 1, var2 = 2;
int * const pVar = &var1; //constant pointer to an integer
pVar = &var2; //Incorrect, gives a compilation error
We have declared two variables var1, and var2. A constant pointer pVar is initialized to point to var1. In the next statement we are trying to point pVar to var2 which is incorrect and gives a compilation error as follows.
[Error] assignment of read-only variable ‘pVar1’
A constant pointer is useless if we don’t initialize it with any address. The compiler gives no error in this case, but that pointer is useless because it can not point to any object further.
int count = 10;
int * const pCount;//Valid code;no compiler error
pCount = &count; //Invalid; compiler error
Pointer to constant:
A pointer to a constant object. This means that we can not modify the object addressed by this pointer. But we can always read the object via this pointer and also we can make this pointer to address another object. To understand this, let us look at the following code snippet.
int var = 1, other = 2;
const int *pVar =&var; //pointer to a constant
*pVar = 10;//error:assignment of read-only location’*pVar1′

printf(“%d”, *pVar); // Valid; we can always read the value

pVar = &other; //valid

We can also create a constant pointer to a constant with the following code. Through this pointer we can not change the value, and we can not make it point to any other object. 

int var = 100, other = 200;
const int * const pVar = &var;//constant pointer to a constant
*pVar = 10;//Error:assignment of read-only location’*pVar1′
pVar = &other; //Invalid; compiler error
other = var / 10; //valid; we can read the value

Reverse a single linked list

Given a singly linked list, how do we reverse it by re-arranging the links?

For example if the given linked list is  1 -> 2 -> 3 -> NULL. The output of reverse method should be 3 -> 2 -> 1 -> NULL.

The following diagram shows the simple steps to perform the reversal.


And here is the C++ code which includes both recursive and iterative versions of reversal method.