## Friday, 11 August 2017

### The Full Counting Sort Hacker Rank Problem Solution.

Problem:

In this challenge you need to print the data that accompanies each integer in a list. In addition, if two strings have the same integers, you need to print the strings in their original order. Hence, your sorting algorithm should be stable, i.e. the original order should be maintained for equal elements.
Insertion Sort and the simple version of Quicksort were stable, but the faster in-place version of Quicksort was not (since it scrambled around elements while sorting).
In cases where you care about the original order, it is important to use a stable sorting algorithm. In this challenge, you will use counting sort to sort a list while keeping the order of the strings (with the accompanying integer) preserved.
Challenge
In the previous challenge, you created a "helper array" that contains information about the starting position of each element in a sorted array. Can you use this array to help you create a sorted array of the original list?
Hint: You can go through the original array to access the strings. You can then use your helper array to help determine where to place those strings in the sorted array. Be careful about being one off.
Details and a Twist
You will be given a list that contains both integers and strings. Can you print the strings in order of their accompanying integers? If the integers for two strings are equal, ensure that they are print in the order they appeared in the original list.
The Twist - Your clients just called with an update. They don't want you to print the first half of the original array. Instead, they want you to print a dash for any element from the first half.
Input Format
, the size of the list
lines follow, each containing an integer  and a string .
Output Format
Print the strings in their correct order.
Constraints

is even
length(s)

The characters in every string in lowercase.
Sample Input
20
0 ab
6 cd
0 ef
6 gh
4 ij
0 ab
6 cd
0 ef
6 gh
0 ij
4 that
3 be
0 to
1 be
5 question
1 or
2 not
4 is
2 to
4 the

Sample Output
- - - - - to be or not to be - that is the question - - - -

Explanation
Below is the list in the correct order. The strings of each number were printed above for the second half of the array. Elements from the first half of the original array were replaced with dashes.
0 ab
0 ef
0 ab
0 ef
0 ij
0 to
1 be
1 or
2 not
2 to
3 be
4 ij
4 that
4 is
4 the
5 question
6 cd
6 gh
6 cd
6 gh

Solution:

#include <bits/stdc++.h>
using namespace std;
/*
* Prosen Ghosh
* American International University - Bangladesh (AIUB)
*
*/
int main() {
int n, half,a;
cin >> n;
half = n/2;
vector<string> str(1000000,"");
string s;
for(int i = 0; i < n; i++){
cin >> a >> s;
if(i < half) str[a] += "- ";
else str[a] += s + " ";
}
for(int i = 0; i < n; i++)cout << str[i];
return 0;
}

### Counting Sort 2 Hacker Rank Problem Solution.

Problem:

Often, when a list is sorted, the elements being sorted are just keys to other values. For example, if you are sorting files by their size, the sizes need to stay connected to their respective files. You cannot just take the size numbers and output them in order, you need to output all the required file information.
However, if you are not concerned about any other information, then you can simply sort those numbers alone. This makes counting sort very simple. If you already counted the values in the list, you don't need to access the original list again. This challenge involves a simple counting sort where the elements being sorted are all that matter.
Challenge
Given an unsorted list of integers, output the integers in order.
Hint: You can use your previous code that counted the items to print out the actual values in order.
Input Format
There will be two lines of input:
•  - the size of the list
•  -  space separated numbers that belong to the list
Output Format
Output all the numbers of the list in order.
Constraints

Sample Input
100
63 25 73 1 98 73 56 84 86 57 16 83 8 25 81 56 9 53 98 67 99 12 83 89 80 91 39 86 76 85 74 39 25 90 59 10 94 32 44 3 89 30 27 79 46 96 27 32 18 21 92 69 81 40 40 34 68 78 24 87 42 69 23 41 78 22 6 90 99 89 50 30 20 1 43 3 70 95 33 46 44 9 69 48 33 60 65 16 82 67 61 32 21 79 75 75 13 87 70 33

Sample Output
1 1 3 3 6 8 9 9 10 12 13 16 16 18 20 21 21 22 23 24 25 25 25 27 27 30 30 32 32 32 33 33 33 34 39 39 40 40 41 42 43 44 44 46 46 48 50 53 56 56 57 59 60 61 63 65 67 67 68 69 69 69 70 70 73 73 74 75 75 76 78 78 79 79 80 81 81 82 83 83 84 85 86 86 87 87 89 89 89 90 90 91 92 94 95 96 98 98 99 99

Explanation In the output you can see the numbers sorted in ascending order. You can also see that numbers appearing multiple times are printed accordingly.

Solution:

#include <bits/stdc++.h>
using namespace std;
/*
* Prosen Ghosh
* American International University - Bangladesh (AIUB)
*
*/
int main() {
int n,a;
vector<int> ar;
cin >> n;
for(int i = 0; i < n; i++){
cin >> a;
ar.push_back(a);
}
sort(ar.begin(),ar.end());
for(int i = 0; i < n; i++)cout << ar[i] << " ";
return 0;
}

### Counting Sort 1 Hacker Rank Problem Solution.

Problem:
Comparison Sorting
Quicksort usually has a running time of , but is there an algorithm that can sort even faster? In general, this is not possible. Most sorting algorithms are comparison sorts, i.e. they sort a list just by comparing the elements to one another. A comparison sort algorithm cannot beat  (worst-case) running time, since  represents the minimum number of comparisons needed to know where to place each element. For more details, you can see these notes (PDF).
Alternative Sorting
However, for certain types of input, it is more efficient to use a non-comparison sorting algorithm. This will make it possible to sort lists even in linear time. These challenges will cover Counting Sort, a fast way to sort lists where the elements have a small number of possible values, such as integers within a certain range. We will start with an easy task - counting.

Challenge
Given a list of integers, can you count and output the number of times each value appears?
Hint: There is no need to sort the data, you just need to count it.
Input Format
There will be two lines of input:
•  - the size of the list
•  -  space-separated numbers that make up the list
Output Format
Output the number of times every number from  to  (inclusive) appears on the list.
Constraints

Sample Input
100
63 25 73 1 98 73 56 84 86 57 16 83 8 25 81 56 9 53 98 67 99 12 83 89 80 91 39 86 76 85 74 39 25 90 59 10 94 32 44 3 89 30 27 79 46 96 27 32 18 21 92 69 81 40 40 34 68 78 24 87 42 69 23 41 78 22 6 90 99 89 50 30 20 1 43 3 70 95 33 46 44 9 69 48 33 60 65 16 82 67 61 32 21 79 75 75 13 87 70 33

Sample Output
0 2 0 2 0 0 1 0 1 2 1 0 1 1 0 0 2 0 1 0 1 2 1 1 1 3 0 2 0 0 2 0 3 3 1 0 0 0 0 2 2 1 1 1 2 0 2 0 1 0 1 0 0 1 0 0 2 1 0 1 1 1 0 1 0 1 0 2 1 3 2 0 0 2 1 2 1 0 2 2 1 2 1 2 1 1 2 2 0 3 2 1 1 0 1 1 1 0 2 2

Explanation
The output states that 0 appears 0 times, 1 appears 2 times, 2 appears 0 times, and so on in the given input array.

Solution:

#include <bits/stdc++.h>
using namespace std;
/*
* Prosen Ghosh
* American International University - Bangladesh (AIUB)
*
*/
int main() {
int n,a,max = -INT_MAX;
vector<int> cnt(1000000,0);
cin >> n;
for(int i = 0; i < n; i++){
cin >> a;
cnt[a]++;
if(a > max)max = a;
}
for(int i = 0; i <= max; i++)cout << cnt[i] << " ";
return 0;
}