A-Division Game

If x%y=0 (x is divisible by y), just print 0. Otherwise, we need exactly y−x%y moves to make zero remainder of x modulo y.
% is modulo operation.

Complexity: O(1).

Sample Code : Link to Submission

B-Trekking Trips

In this problem, store the count of trips for each person in an array. Then,traverse the array, and simply add k to each array element. This gives you the count of trips each person would have if they did go for the next k trips. Out of these, only those people can be part of a group, whose count is less than or equal to 5. Divide this number by 3 to get the maximum number of groups that can be formed.

Complexity: O(n)

Sample Code : Link to Submission

C-Percy and his string

Let sort(s) be s sorted alphabetically. The answer to the problem is the number m of mismatches between s and sort(s) (i.e., the positions with different characters in the two strings).

Choosing k=m characters is sufficient. Let us choose the mismatched characters between s and sort(s), and permute them so that they are sorted alphabetically. It is not hard to prove that the resulting string will coincide with sort(s).

Choosing strictly less than m characters is not sufficient. If k < m, by the Pigeonhole Principle at least one of the mismatched characters will be left out, and thus it will prevent the final string from being ordered alphabetically.

Complexity: O(nlogn).

Sample Code : Link to Submission

D-Prepare The Troops

Write down n and keep dividing it by 2. If the number appeared is an odd number is greater than zero, we assign one soldier into this troop on the monday of (x+1-i)th week. Then at the monday of the xth week, the troop will be assigned with n soldiers.

We can simply say that, if we divide the number by 2 and if it is not equal to zero then we will check if it is an odd number then we will increase our counter by 1. Then simply print our counter+1.

Time Complexity for each test case would be: O(n).

Sample Code : Link to Submission

E-Square or not

The squares can be formed by combinations of either type of 2 squares:

If n can be written as 2x or 4x, where x is a square number, then the answer is YES. Otherwise it is NO.

To visualize this construction, we start by first building a smaller square using exactly 2 or 4 pieces. We can just use x of those smaller squares to build a larger square. Let's prove that there are no other answers (although this isn't necessary to solve the problem). Let's define each triangle piece to have a short side of length 1 and a longer side of length √2. Consider one side of the square, and suppose that it has a triangles on the short side and b triangles on the longer side. The side length will be a+√2b. The area of the square is a rational number because the area of each triangle piece is rational. So, (a+√2b)^2 has to be rational, which means either a is 0, or b is 0. If either is 0, we can use the construction in the previous paragraph.

Time complexity for each test case: O(√n) or O(logn) (depends on how you check for square numbers)

Sample Code : Link to Submission

F-Square within Square

We will check if there exists any 2*2 square such that three characters of the square are equal and one of them is odd one. If there exists any one square, we print "YES" , else "NO".

Sample Code : Link to Submission

G-Vaccination

Iterate the sequence using loop and for every position i (1 ≤ i ≤ N) of the sequence, take the sum from both left (P[1]+P[2]+....P[i]) and right (P[N]+P[N-1]+....P[i+1]) side of the sequence.

After that find the rightmost position where difference between those two sum will be minimum and that will be the no of houses vaccinated by Divya.

Then print that position and N-position.

This will work in O(N) time.

Sample Code : Link to Submission

H-Rakesh and his love with Factorials

Conclusion first: First, we transform each digit of the original number as follows:

0, 1 -> empty

2 -> 2

3 -> 3

4 -> 322

5 -> 5

6 -> 53

7 -> 7

8 -> 7222

9 -> 7332

Then, sort all digits in decreasing order as a new number, then it will be the answer.

Sample Code : Link to Submission

For any queries, you can write a comment below this blog or you can head over to ourForum.

Posted by: Varandeep01 on Feb. 26, 2022, 3:40 p.m. Last updated on Feb. 26, 2022, 4:30 p.m.