Coding Challenge 1.0
Problem Level: Easy
Contest Link: https://www.hackerearth.com/msit-coding-challenge-10/
This note is a brief explanation of the problems in the contest. This is not the complete editorial for the problems.
By - Prateek Kumar (pratku123)

Problem 5: Prateek and the project groups
Explanation
The input contains a number of pairs (x,y), this means that person numbered x and y share the same interest. All these pairs are transitive and symmetric.
1) Your first task is group all the people with similar interest into a single group.
For example, for the test case,
6 4
1 2
2 3
4 5
2 6
The number of people (n)=6, and number of pairs (k)=4.
Now, 1-2-3-6 [(1,2),(2,3),(2,6)] are in one group and 4-5 [(4,5)] are in one group.
2) The next task is to find the number of ways to pick 2 students from groups with 2 or more students and pick 1 student from the group with one student. In the above case, the number of ways to pick 2 students from group 1 is ⁴C₂=6 and the number of ways to pick 1 student from group 2 is ¹C₁. The total number of ways is product of the answer for each of the group values: (6)*(1)=6
3) The problem can be solved using 2 methods:
-- Union/ find.
--DFS on an undirected graph: Using DFS, find the connected components and count of the nodes in each of the connected components. This can be done in O(V+E), where V is the number of nodes and E is the number of edges. Here, V is the total number of people(n).

Problem 1: Emma and the prime numbers
The problem Statement
The problem was to calculate the sum of all the primes in between x and y.
1<=x,y<=10⁶
You were supposed to do this for a number of test cases, 1<=t<=10⁵

Explanation
The time constraints were such that the following steps were inevitable:
1. Pre- compute and generate all the primes from 1 to 10⁶. This can be done using the sieve of eratosthenes.
Useful links: Sieve of eratosthenes , Time complexity of sieve
2. Declare an array ARR[] of size 10⁶, and mark ARR[i] as 1 if i is prime else mark it as 0. This is done in O(MAX). MAX=10⁶
3. The next step is to maintain an array SUM[n] that stores the SUM[n] is the sum of all prime numbers from 1 to n [1,n].
This can be done in O(MAX), MAX=10⁶.
4. The answer for each query of the type x,y can be answered in a time complexity of O(1) as ans=SUM[y]-SUM[x-1].


Problem 2: Prateek and the name list
Explanation
This problem contains a number of strings as input. You were supposed to count the frequency of all the distinct strings. After this, find the maximum frequency from all the frequency. Lastly, find the number of times this maximum frequency occurs and then multiply this count with the maximum frequency to get the final answer.
The use of STL map in C++, made this problem very easy to implement.

Problem 3: The string permutations
Explanation
You were required to print all the distinct permutations of the input string. This problem used backtracking to produce all the permutations of a given string. From all the permutations, just remove the redundant strings and sort the remaining strings in the dictionary order to get the required result. This link contains an explanation of generation of permutations of a string using backtracking

Problem 4: Prateek and the queries
Explanation You are given an integer array and a number of queries, q, of the type L, R. You are required to report the count of total number of integers greater than equal to L and less than equal to R present in the array.
1. The first step is to sort the array.
2. After that, find the lower bound LB in the array, using binary search where the number is greater than or equal to L.
3. Also, find the upper bound UB in the array, using binary search, where the number is less than or equal to R.
4. The required answer is UB-LB+1.