# 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.

# 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++.

# 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.

# 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.

# 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

# 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.

# 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.

# 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.

# 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.

# 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.