#Manifold

Warning: HackerRank has recently changed the constraints of the problem by allowing duplicates. This change invalidated a couple of our solutions. This is discussed in the post. Solutions We found many solutions to this challenge. Naive solution 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 bool isBeautiful(int i, int j, int k, int d, const vector<int>& arr) { int a = arr[j] - arr[i]; int b = arr[k] - arr[j]; return a == b && a == d; } int beautifulTriplets(int d, vector<int> arr) { int n = arr. [Read More]

Given an unsorted array of \( n-1 \) elements, it is missing exactly one element from the sequence of \( 1 \) to \( n\). Find the missing element. Input Format An integer \( n \) followed by \( n-1 \) space separated numeric values. Constraints \( 1<n<10^6 \) Output Format The missing value. Solutions This is an example of problems that we call manifold at Coding Gym, since they give us room to find several alternative solutions. [Read More]

Solutions This problem looks like a classical puzzle: merging overlapping intervals. A naive approach is \(O(N^2)\) and consists in checking each route with the others. In case they overlap, remove the other route from the array and merge both into the first one. The crucial condition to check if two routes overlap is (assuming route1 precedes route2): 1 route1.end >= route2.begin For example: 1 2 3 1 5 3 6 10 32 1 5 overlaps with 3 6, indeed 5 >= 3. [Read More]

Warning: HackerRank has recently changed the constraints of this problem but it did not update the challenge itself. Now they allow zeros to be part of the input. In particular this can cause empty sub-arrays to be a valid solution. For example this was not valid input before the update: 1 2 0 0 0 Now it is. A solution is the position 0 since the left sub-array is empty. [Read More]

Solutions This problem can be solved in several ways, each carrying its own pros, cons and tradeoffs. All the solutions are based on this observation: the answer is always \(max(6-n,4-d)\) where \(n\) is string length and \(d\) is the number of different type of characters that are already present in the input password. Preamble We call character family the group of characters belonging to the same requirement. The problem requires to check against 4: digits, lowercase letters, uppercase letters, special chars. [Read More]

The school term starts soon, and the students need to be sorted into their respective sections. There are \( n \) students numbered \( 1 \) to \( n \), and \( m \) sections numbered \( 1 \) to \( m \). Section needs to have exactly \( a_i \) students. To simplify the process, the school has decided to assign students to sections in increasing student number, which means the first \( a_1 \) students will be assigned section \( 1 \), the next \( a_2 \) students will be assigned section \( 2 \), and so on. [Read More]

A professor calls out student IDs of students one by one while marking attendance. He notices that the number of students recorded in the attendance sheet is far more than the number of students who are actually present in the classes. Hence, he decides to use a robot which can record the students’ voices and keep track of which students have responded to attendance calls. At the end of each session, the robot outputs the student IDs of the students who have responded to attendance calls. [Read More]