HACK WITH INFY

SAMPLE QUESTIONS
1. EASY
You’re given an array A of n integers and q queries.
for query 4 -> (2, 3, 4)
calculate sum of array from index 3 to 4 -> sum =
Each query can be one of the following two types: A[3]+A[4] = 28
• Type 1 Query: (1, l, r) - Replace A[i] with
(i-l+1)*A[l] for each index i, where l <= i <= r. for query 5 -> (2, 3, 3)
• Type 2 Query: (2, l, r) - Calculate the sum of the calculate sum of array from index 3 to 3 -> sum =
elements in A from index l to index r. A[3] = 12

Find the sum of answers to all type 2 queries. Since Hence, answer is 20+28+12 = 60
answer can be large, return it modulo 109+7.
Sample Input 2
Sample Input 1 7
7 3
1 7
4 4
5 2
1 5
6 3
7 7
8 5
5 104
116 201
115 136
255 233
234 205
233
Sample Output 2
Sample Output 1 111
60
Sample Output Description 2
Sample Output Description 1 Here, n = 7
Here, n = 7 A = [3, 7, 4, 2, 5, 3, 7]
A = [1, 4, 5, 1, 6, 7, 8] q=5
q=5 queries = [[1, 0, 4], [2, 0, 1], [1, 3, 6], [2, 3, 3], [2, 0, 5]]
queries = [[1, 1, 6], [1, 1, 5], [2, 5, 5], [2, 3, 4], [2, 3, 3]]
for query 1 -> (1, 0, 4)
for query 1 -> (1, 1, 6) Applying the operation on subarray from index 0 to
Applying the operation on subarray from index 1 to 4, A becomes, A = [3, 6, 9, 12, 15, 3, 7]
6, A becomes, A = [1, 4, 8, 12, 16, 20, 24]
for query 2 -> (2, 0, 1)
for query 2 -> (1, 1, 5) calculate sum of array from index 0 to 1 -> sum =
Applying the operation on subarray from index 1 to A[0]+A[1] = 9
5, A becomes, A = [1, 4, 8, 12, 16, 20, 24]
for query 3 -> (1, 3, 6)
for query 3 -> (2, 5, 5) Applying the operation on subarray from index 3 to
calculate sum of array from index 5 to 5 -> sum = 6, A becomes, A = [3, 6, 9, 12, 24, 36, 48]
A[5] = 20

External Document © 2025 Infosys Limited

for query 4 -> (2, 3, 3)
calculate sum of array from index 3 to 3 -> sum = for query 5 -> (2, 6, 6)
A[3] = 12 calculate sum of array from index 6 to 6 -> sum = 7

for query 5 -> (2, 0, 5) Hence, answer is 25+14+7 = 46

calculate sum of array from index 0 to 5 -> sum =
A[0]+A[1]+A[2]+A[3]+A[4]+A[5] = 90 Input Format
Hence, answer is 9+12+90 = 111 The first line contains an integer, n, denoting the
number of elements in A.
Sample Input 3 Each line i of the n subsequent lines (where 0 ≤ i <
7 n) contains an integer describing A[i].
1 The next line contains an integer, q, denoting the
8 number of rows in queries.
6 Each line i of the q subsequent lines (where 0 ≤
10 i < q) contains 3 space separated integers each
5 describing the row queries[i].
6 The 3 space separated integers denote the value of
9 either (1,l,r) or (2,l,r) for the i-th query.
5
203 Constraints
123 1 <= n <= 10^5
106 1 <= A[i] <= 10^5
214 1 <= q <= 10^5
266 0 <= queries[i][j] <= 10^5

Sample Output 3 Sample Test Cases

46
Case 1
Sample Output Description 3 Input:
Here, n = 7 7
A = [1, 8, 6, 10, 5, 6, 9] 1
q=5 4
queries = [[2, 0, 3], [1, 2, 3], [1, 0, 6], [2, 1, 4], [2, 6, 6]] 5
1
for query 1 -> (2, 0, 3) 6
calculate sum of array from index 0 to 3 -> sum = 7
A[0]+A[1]+A[2]+A[3] = 25 8
5
for query 2 -> (1, 2, 3) 116
Applying the operation on subarray from index 2 to 115
3, A becomes, A = [1, 8, 6, 12, 5, 6, 9] 255
234
for query 3 -> (1, 0, 6) 233
Applying the operation on subarray from index 0 to
6, A becomes, A = [1, 2, 3, 4, 5, 6, 7] Output:
60
for query 4 -> (2, 1, 4) Explanation:
calculate sum of array from index 1 to 4 -> sum = 14 Here, n = 7

External Document © 2025 Infosys Limited

A = [1, 4, 5, 1, 6, 7, 8] queries = [[1, 0, 4], [2, 0, 1], [1, 3, 6], [2, 3, 3], [2, 0, 5]]
q=5
queries = [[1, 1, 6], [1, 1, 5], [2, 5, 5], [2, 3, 4], [2, 3, 3]] for query 1 -> (1, 0, 4)
Applying the operation on subarray from index 0 to
for query 1 -> (1, 1, 6) 4, A becomes, A = [3, 6, 9, 12, 15, 3, 7]
Applying the operation on subarray from index 1 to
6, A becomes, A = [1, 4, 8, 12, 16, 20, 24] for query 2 -> (2, 0, 1)
calculate sum of array from index 0 to 1 -> sum =
for query 2 -> (1, 1, 5) A[0]+A[1] = 9
Applying the operation on subarray from index 1 to
5, A becomes, A = [1, 4, 8, 12, 16, 20, 24] for query 3 -> (1, 3, 6)
Applying the operation on subarray from index 3 to
for query 3 -> (2, 5, 5) 6, A becomes, A = [3, 6, 9, 12, 24, 36, 48]
calculate sum of array from index 5 to 5 -> sum =
A[5] = 20 for query 4 -> (2, 3, 3)
for query 4 -> (2, 3, 4) calculate sum of array from index 3 to 3 -> sum =
calculate sum of array from index 3 to 4 -> sum = A[3] = 12
A[3]+A[4] = 28
for query 5 -> (2, 0, 5)
for query 5 -> (2, 3, 3) calculate sum of array from index 0 to 5 -> sum =
calculate sum of array from index 3 to 3 -> sum = A[0]+A[1]+A[2]+A[3]+A[4]+A[5] = 90
A[3] = 12 Hence, answer is 9+12+90 = 111

Hence, answer is 20+28+12 = 60 Case 3

Case 2 Input:
Input: 7
7 1
3 8
7 6
4 10
2 5
5 6
3 9
7 5
5 203
104 123
201 106
136 214
233 266
205
Output:
Output: 46
111
Explanation:
Explanation: Here, n = 7
Here, n = 7 A = [1, 8, 6, 10, 5, 6, 9]
A = [3, 7, 4, 2, 5, 3, 7] q=5
q=5 queries = [[2, 0, 3], [1, 2, 3], [1, 0, 6], [2, 1, 4], [2, 6, 6]]

External Document © 2025 Infosys Limited

 2. EASY
You are given an array A of length N and an
integer k.

It is given that a subarray from l to r is considered

good, if the number of distinct elements in that
subarray doesn’t exceed k. Additionally, an empty
subarray is also a good subarray and its sum is
considered to be zero.

Find the maximum sum of a good subarray.

Sample Input 1
11
2
1
2
2
3
2
3
5
1
2
1
1
for query 1 -> (2, 0, 3)
calculate sum of array from index 0 to 3 -> sum = Sample Output 1
A[0]+A[1]+A[2]+A[3] = 25 12

for query 2 -> (1, 2, 3) Sample Output Description 1

Applying the operation on subarray from index 2 to Here, N = 11, k = 2
3, A becomes, A = [1, 8, 6, 12, 5, 6, 9] A = [1, 2, 2, 3, 2, 3, 5, 1, 2, 1, 1]

for query 3 -> (1, 0, 6) We can select the subarray = [2, 2, 3, 2, 3]

Applying the operation on subarray from index 0 to It is a good subarray because it contains at most k
6, A becomes, A = [1, 2, 3, 4, 5, 6, 7] distinct elements.
Its sum = 2+2+3+2+3 = 12
for query 4 -> (2, 1, 4)
calculate sum of array from index 1 to 4 -> sum = 14 So, our answer is 12.

for query 5 -> (2, 6, 6) Sample Input 2

calculate sum of array from index 6 to 6 -> sum = 7 3
1
Hence, answer is 25+14+7 = 46 -1
-2
-3

External Document © 2025 Infosys Limited

Sample Output 2 Input Format
0 The first line contains an integer, N, denoting the
Sample Output Description 2 number of elements in A.
Here, N = 3, k = 1 The next line contains an integer, k, denoting the
A = [-1, -2, -3] limit on the distinct elements.
Each line i of the N subsequent lines (where 0 ≤ i <
It is optimal to choose empty subarray. N) contains an integer describing A[i].

So, our answer is 0. Constraints

1 <= N <= 10^5
Sample Input 3 1 <= k <= n
5 -10^5 <= A[i] <= 10^5
5
-1 Sample Test Cases
1
3 Case 1
2 Input:
-1 11
2
Sample Output 3 1
6 2
2
Sample Output Description 3 3
Here, N = 5, k = 5 2
A = [-1, 1, 3, 2, -1] 3
5
It is optimal to choose the subarray = [1, 3, 2]. 1
Its sum = 1+3+2 = 6. 2
Hence, our answer is 6. 1
1
External Document © 2025 Infosys Limited
Output:
12 3. EASY
Explanation: You have an oil tank with a capacity of C litres that
Here, N = 11, k = 2 can be bought and sold by N people. The people
A = [1, 2, 2, 3, 2, 3, 5, 1, 2, 1, 1] are standing in a queue are served sequentially in
We can select the subarray = [2, 2, 3, 2, 3] the order of array A.
It is a good subarray because it contains at most k
distinct elements. Some of them want to sell a litre of oil and some of
Its sum = 2+2+3+2+3 = 12 them want to buy a litre of oil and A describes this.
So, our answer is 12. Here, A[i] = 1 denotes that the person wants to sell
a litre of oil and A[i] = -1 denotes that the person
Case 2 wants to buy a litre of oil.
Input:
3 When a person wants to sell a litre of oil but the
1 tank is full, they cannot sell it and become upset.
-1 Similarly, when a person wants to buy a litre of
-2 oil but the tank is empty, they cannot buy it and
-3 become upset. Both these cases cause disturbances.
Output:
0 You can minimize the disturbance by filling the tank
Explanation: initially with a certain X litres of oil.
Here, N = 3, k = 1
A = [-1, -2, -3] Find the minimum initial amount of oil X that results
in the least number of disturbances.
It is optimal to choose empty subarray.
So, our answer is 0. Input Format
The first line contains an integer, N, denoting the
Case 3 number of elements in A.
Input: The next line contains an integer, C, denoting the
5 capacity of the tank.
5 Each line i of the N subsequent lines (where 0 ≤ i <
-1 N) contains an integer describing A[i].
1
3 Constraints
2 1 <= N <= 10^5
-1 1 <= C <= 10^5
Output: -1 <= A[i] <= 1
6
Explanation: Sample Test Cases
Here, N = 5, k = 5
A = [-1, 1, 3, 2, -1] Case 1
Input:
It is optimal to choose the subarray = [1, 3, 2]. 3
Its sum = 1+3+2 = 6. 3
Hence, our answer is 6. -1
1
1

External Document © 2025 Infosys Limited

Output: Output:
1 0
Explanation: Explanation:
Given N = 3, C = 3, A = [-1, 1, 1]. Given N = 4, C = 3, A = [1, 1, 1, 1].

To avoid disturbance for Person 1, we need at least 1. Person 1 wants to sell 1 liter of oil (A[1] =1).
1 liter in the tank initially. Initially, the tank is empty, so Person 1 can sell 1
liter. The tank now has 1 liter of oil.
After Person 1 buys 1 liter, the tank will be empty. 2. Person 2 wants to sell 1 liter of oil (A[2]=1).
The tank now has 1 liter, so Person 2 can sell 1
Person 2 sells 1 liter, so the tank will have 1 liter. liter. The tank now has 2 liters of oil.
3. Person 3 wants to sell 1 liter of oil (A[3]=1).
Person 3 sells another liter, so the tank will have 2 The tank now has 2 liters, so Person 3 can sell 1
liters. liter. The tank now has 3 liters of oil, which is its
full capacity.
The minimum initial amount X needed to achieve 4. Person 4 wants to sell 1 liter of oil (A[4]=1).
the least number of disturbances is 1 liter. The tank is now full (3 liters), so Person 4 cannot
sell 1 liter and will be upset.
Case 2
Input: Given that the tank capacity C is 3 liters and all
3 actions are selling oil, the only disturbance occurs
2 when Person 4 tries to sell oil to a full tank.
-1
-1 Therefore, no initial amount of oil X will change the
1 disturbance for Person 4, as the tank’s capacity is
Output: already limiting.
2
Explanation: Hence, the minimum initial amount of oil X required
Given N = 3, C = 2, A = [-1, -1, 1]. to achieve the least number of disturbances
remains 0.
To ensure that there are no disturbances:

We need at least 1 liter for Person 1.

We need an additional 1 liter for Person 2, making

the total initial amount of oil X = 2.

Thus, the minimum initial amount of oil X required

to achieve the least number of disturbances is 2.

Case 3
Input:
4
3
1
1
1
1

External Document © 2025 Infosys Limited

4. EASY
General Ali has devised a strategic game to reduce
Output:
0
Explanation:
an enemy army of N soldiers to just 1 soldier using a Given N = 1.
minimal number of moves.
There is only 1 soldier already, so no moves are
The game allows the following three types of required to reduce the enemy soldiers to 1.
moves:
1. Reduce the enemy army by 1 soldier. Therefore, the minimum number of moves needed
2. Reduce the enemy army by half of its current is 0.
soldiers, rounding down to the nearest integer.
3. Reduce the enemy army by two-thirds of its Case 3
current soldiers, rounding down to the nearest Input:
integer. 6
Output:
Each move must ensure that the resulting number 2
of soldiers is an integer. Explanation:
Given N = 6.
Find the minimum number of moves required to
reduce enemy army to just 1 soldier. Move 1: Reduce by half (6 -> 3)
Move 2: Reduce by half (3 -> 1)
Input Format
The first line contains an integer, N, denoting the Hence, the answer for this case is equal to 2.
number of enemy soldiers.

Constraints
1 <= N <= 10^9

Sample Test Cases

Case 1
Input:
5
Output:
3
Explanation:
Given N = 5.

Move 1: Reduce by 1 soldier (5 -> 4)

Move 2: Reduce by half (4 -> 2)
Move 3: Reduce by half (2 -> 1)

Hence, the answer for this case is equal to 3.

Case 2
Input:
1

External Document © 2025 Infosys Limited

5. EASY
General Ali has initiated an invasion in the shape
After 1 second the enemy’s country will be like Q =
[[“AA”], [“AE”]].

of an N×M grid behind enemy lines given by a 2D After 2 seconds the enemy’s country will be like Q =
array Q. [[“AA”], [“AA”]].

The grid consists of cells represented by the Hence, the answer for this case is equal to 2.
following characters:
1. ‘*’: Represents a block cell that cannot be visited. Case 2
2. ‘A’: Represents a cell that has been invaded by Input:
General Ali’s army. 3
3. ‘E’: Represents a cell that contains the enemy’s 2
army. AE
*E
General Ali’s invasion progresses as follows: At each EE
second, any cell marked ‘E’ that shares a side with a Output:
cell marked ‘A’ is invaded by General Ali’s army. 4 Explanation:
Given N = 3, M = 2, Q = [[“AE”], [“*E”], [“EE”]].
Find the minimum time it will take for General Ali’s
army to invade all enemy cells (‘E’) in the grid. If it’s After 1 second the enemy’s country will be like Q =
not possible to invade all enemy cells, return −1. [[“AA”], [“AE”], [“EE”]].

Input Format After 2 seconds the enemy’s country will be like Q =

The first line contains an integer, N, denoting the [[“AA”], [“AA”], [“AE”]].
number of elements in Q.
The next line contains an integer, M, denoting the After 3 seconds the enemy’s country will be like Q =
given integer. [[“AA”], [“AA”], [“AA”]]
Each line i of the N subsequent lines (where 0 ≤ i <
N) contains a string describing Q[i]. Hence, the answer for this case is equal to 4.
Case 3
Constraints Input:
1 <= N <= 10^3 3
1 <= M <= 10^3 2
1 <= len(Q[i]) <= 10^5 AE
**
EE
Sample Test Cases Output:
-1
Case 1 Explanation:
Input: Given N = 3, M = 2, Q = [[“AE”], [“**”], [“EE”]].
2
2 After 1 second the enemy’s country will be like Q =
AE [[“AA”], [“**”], [“AA”]].
EE
Output: After that General Ali’s army can’t continue the
2 invasion because of the block cells so the answer is
Explanation: -1.
Given N = 2, M = 2, Q = [[“AE”], [“EE”]].

External Document © 2025 Infosys Limited

6. MEDIUM
A company ABC has N employees.
expert value of team [0, 2, 1] = 3
expert value of team [1] = 0

For some reason, the company’s building is a bit So, expert number = 3+0 = 3
weird.
• It has one office on each floor and in each Please note that there is no other way to divide the
office works one employee. employees such that expert number is greater than
• Each employee i works on the ith floor and 3.
has skill Ai.
• Each employee can belong to at most one Hence, the maximum value of expert number is 3.
team.
• Each team should have employees working Sample Input 2
in consecutive floors from i to j. In other words, 5
the teams should be divided in such a way that no 0
employee of one team can walk into the project 1
space of another team. 2
1
ABC uses a metric which is called the expert 0
number which is calculated as the sum of all the
absent expert values from each team of employees. Sample Output 2
The absent expert value of each team is the first skill 5
starting from 0 which is not present in the team.
Sample Output Description 2
It is given that a bigger expert number is a better Here, N = 5
expert number. Hence, you need to divide the A = [0, 1, 2, 1, 0]
employees into teams such that the company’s
expert number is as large as possible. We can divide the employees in the following teams
-> [0, 1, 2], [1, 0]
Find the maximum expert number that can be
obtained. expert value of team [0, 1, 2] = 3
expert value of team [1, 0] = 2
Sample Input 1
4 So, expert number = 3+2 = 5
0
2 Please note that there is no other way to divide the
1 employees such that expert number is greater than
1 5.

Sample Output 1 Hence, the maximum value of expert number is 5.

3
Sample Input 3
Sample Output Description 1 10
Here, N = 4 0
A = [0, 2, 1, 1] 1
0
We can divide the employees in the following teams 1
-> [0, 2, 1], [1]

External Document © 2025 Infosys Limited

1 Here, N = 4
0 A = [0, 2, 1, 1]
3 We can divide the employees in the following teams
2 -> [0, 2, 1], [1]
1
0 expert value of team [0, 2, 1] = 3
expert value of team [1] = 0
Sample Output 3
10 So, expert number = 3+0 = 3

Sample Output Description 3 Please note that there is no other way to divide the
Here, N = 10 employees such that expert number is greater than
A = [0, 1, 0, 1, 1, 0, 3, 2, 1, 0] 3.

We can divide the employees in the following teams Hence, the maximum value of expert number is 3.
-> [0, 1], [0, 1], [1, 0, 3, 2], [1, 0]
Case 2
expert value of team [0, 1] = 2 Input:
expert value of team [1, 0, 3, 2] = 4 5
0
So, expert number = 2 + 2 + 4 + 2 = 10 1
2
Please note that there is no other way to divide the 1
employees such that expert number is greater than 0
10. Output:
5
Hence, the maximum value of expert number is 10. Explanation:
Here, N = 5
Input Format A = [0, 1, 2, 1, 0]
The first line contains an integer, N, denoting the
number of elements in A.
Each line i of the N subsequent lines (where 0 ≤ i <
N) contains an integer describing A[i].

Constraints
1 <= N <= 10^5
1 <= A[i] <= 10^3
Sample Test Cases

Case 1
Input:
4
0
2
1
1
Output:
3
Explanation:
External Document © 2025 Infosys Limited
We can divide the employees in the following teams
-> [0, 1, 2], [1, 0]
7. MEDIUM
You are given a graph with n nodes. Initially, the
graph is disconnected, meaning it contains zero
expert value of team [0, 1, 2] = 3 edges.
expert value of team [1, 0] = 2
Each node has a value written on it such that the ith
So, expert number = 3+2 = 5 node has a value i.

Please note that there is no other way to divide the We say that a range [l, r] is covered in a set s, if for
employees such that expert number is greater than each i from l to r, i appears in s.
5.
Now, let’s define beauty(s), as the minimum
Hence, the maximum value of expert number is 5. number of covered ranges, such that each element
of s belongs to at least one of these ranges. For
Case 3 example: beauty([1, 2, 4, 5, 8, 11]) = 4 (covered
Input: ranges are [1, 2], [4, 5], [8] and [11]).
10
0 You have to process q queries that are either of the
1 following types:
0 • Type 1 - (1, i, j): Add an edge between i and j.
1 • Type 2 - (2, u, 0): Find the number of covered
1 ranges in the connected component of u.
0 Find the sum of answers to all type 2 queries.
3 Sample Input 1
2 2
1 1
0 3
Output: 210
10
Explanation: Sample Output 1
Here, N = 10 1
A = [0, 1, 0, 1, 1, 0, 3, 2, 1, 0]
Sample Output Description 1
We can divide the employees in the following teams Here, n = 2, q = 1, t = 3
-> [0, 1], [0, 1], [1, 0, 3, 2], [1, 0] queries = [[2, 1, 0]]

expert value of team [0, 1] = 2 for query1 -> As there are no edges in the graph,
expert value of team [1, 0, 3, 2] = 4 the connected component of 1 contain only node 1.
only one covered range required i.e. [1, 1]
So, expert number = 2 + 2 + 4 + 2 = 10 Hence, answer for this query is 1.

Please note that there is no other way to divide the So, the answer is 1.
employees such that expert number is greater than
10. Sample Input 2
2
Hence, the maximum value of expert number is 10. 3
3
210
External Document © 2025 Infosys Limited
112 Hence, answer for this query is 2.
210 So, the answer is 2 + 2 = 4.

Sample Output 2 Input Format

2 The first line contains an integer, n, denoting the
size of the graph.
Sample Output Description 2 The next line contains an integer, q, denoting the
Here, n = 2, q = 3, t = 3 number of rows in queries.
queries = [[2, 1, 0], [1, 1, 2], [2, 1, 0]] The next line contains an integer, t, denoting the
number of columns in queries.
for query1 -> (2, 1, 0) Each line i of the q subsequent lines (where 0 ≤
connected component of 1 = {1} i < q) contains t space separated integers each
only one covered range required i.e. [1, 1] describing the row queries[i].
Hence, answer for this query is 1.
Constraints
for query2 -> (1, 1, 2) 1 <= n <= 10^5
Add an edge between 1 and 2. 1 <= q <= 10^5
for query3 -> (2, 1, 0) 3 <= t <= 3
connected component of 1 = {1, 2} 0 <= queries[i][j] <= n
only one covered range required i.e. [1, 2]
Hence, answer for this query is 1. Sample Test Cases
So, the answer is 1 + 1 = 2.
Case 1
Sample Input 3 Input:
10 2
3 1
3 3
114 210
210 Output:
240 1
Explanation:
Sample Output 3 Here, n = 2, q = 1, t = 3
4 queries = [[2, 1, 0]]

Sample Output Description 3 for query1 -> As there are no edges in the graph,
Here, n = 10, q = 3, t = 3 the connected component of 1 contain only node 1.
queries = [[1, 1, 4], [2, 1, 0], [2, 4, 0]] only one covered range required i.e. [1, 1]
Hence, answer for this query is 1.
for query1 -> (1, 1, 4)
Add an edge between 1 and 4 So, the answer is 1.

for query2 -> (2, 1, 0) Case 2

connected component of 1 = {1, 4} Input:
two covered ranges are required i.e. [1, 1] and [4, 4] 2
Hence, answer for this query is 2. 3
3
for query3 -> (2, 4, 0) 210
connected component of 4 = {1, 4} 112
two covered ranges are required i.e. [1, 1] and [4, 4] 210
External Document © 2025 Infosys Limited
Output: 210
2 240
Explanation: Output:
Here, n = 2, q = 3, t = 3 4
queries = [[2, 1, 0], [1, 1, 2], [2, 1, 0]] Explanation:
Here, n = 10, q = 3, t = 3
for query1 -> (2, 1, 0) queries = [[1, 1, 4], [2, 1, 0], [2, 4, 0]]
connected component of 1 = {1}
only one covered range required i.e. [1, 1] for query1 -> (1, 1, 4)
Hence, answer for this query is 1. Add an edge between 1 and 4

for query2 -> (1, 1, 2) for query2 -> (2, 1, 0)

Add an edge between 1 and 2. connected component of 1 = {1, 4}
two covered ranges are required i.e. [1, 1] and [4, 4]
for query3 -> (2, 1, 0) Hence, answer for this query is 2.
connected component of 1 = {1, 2}
only one covered range required i.e. [1, 2] for query3 -> (2, 4, 0)
Hence, answer for this query is 1. connected component of 4 = {1, 4}
So, the answer is 1 + 1 = 2. two covered ranges are required i.e. [1, 1] and [4, 4]
Hence, answer for this query is 2.
Case 3 So, the answer is 2 + 2 = 4
Input:
10
3
3
114

External Document © 2025 Infosys Limited

8. MEDIUM
A group of N people are seated around a circular
1

Case 2
table to play a game. Input:
5
The game involves jumping from one chair to 2
another. Each person sitting on chair i can jump A[i] 4
chairs to either the right or left in one jump where 0 5
< i < N+1. 4
3
Bob, sitting on chair X, needs to reach chair Y, where 2
the escape door is located. 1

Find the minimum number of jumps required to Output:

reach chair Y from chair X. If this is impossible using 3
the given jump distances, then return -1.
Case 3
Input Format Input:
The first line contains an integer, N, denoting the 6
number of people playing the game. 2
The next line contains an integer, X, denoting the 3
chair on which Bob is seated. 2
The next line contains an integer, Y, denoting the 2
chair which Bob wants to reach. 2
Each line i of the N subsequent lines (where 1 ≤ i ≤ 2
N) contains an integer describing A[i] is the number 2
of chairs the person sitting in chair number i can 2
jump either right or left. Output:
-1
Constraints
1 <= N <= 10^5
1 <= X <= N
1 <= Y <= N
1 <= A[i] <= 10^5

Sample Test Cases

Case 1
Input:
5
5
1
1
2
3
2
4
Output:

External Document © 2025 Infosys Limited

 You are given two integers B and R. Let the
9. MEDIUM probability of choosing the box with the blue balls
be (B / 106) and (R / 106) be the probability of
You are given two boxes where one contains an choosing the box with red balls.
infinite number of blue balls and the other contains
an infinite number of red balls. We can construct Find the probability of creating a great chain of
a chain of balls by choosing one of the boxes and length N. Since the answer can be large, return it
taking out a ball from it and inserting it at the end modulo 109 + 7.
of the chain.
Input Format
A chain is called good if after each time we insert a The first line contains an integer, N, denoting the
new ball, the number of blue balls doesn’t exceed length of the chain.
the number of red balls by more than K. In other The next line contains an integer, K, denoting the
words, if after adding the ith ball we have B[i] blue value K in B[i] ≤ R[i] + K.
balls and R[i] red balls then it must satisfy B[i] ≤ R[i] The next line contains an integer, B, denoting the
+ K. probability of choosing the box with blue balls.
The next line contains an integer, R, denoting the
A chain is called great if it is a good chain and if we probability of choosing the box with red balls.
take the reversed chain the following conditions
satisfy: Constraints
• Every blue ball in the reversed chain is matched 1 <= N <= 10^9
with a red ball in the original chain. 1 <= K <= 100
• Every red ball in the reversed chain is matched 1 <= B <= 10^6
with a blue ball in the original chain. 1 <= R <= 10^6

External Document © 2025 Infosys Limited

Sample Test Cases

Case 1
10. MEDIUM
You are given an array A of size N.
Input:
1 You can partition A into multiple subarrays such
1 that each element belongs to exactly one subarray
199252 and each subarray has a length of at least K.
470888
Output: The beauty of a subarray is the maximum bitwise
542964004 XOR of the values of a subset in that subarray. The
Explanation: amazingness of a partitioned array is the sum of
Given N = 1, M = 1, B = 199252, R = 470888. beauties of its subarrays.

There is only one great chain: B. Find the maximum possible amazingness of A.

Hence, the output for this case is equal to Note:

542964004. • A subarray is a contiguous part of the array.

Case 2 Input Format

Input: The first line contains an integer, N, denoting the
2 number of elements in A.
1 The next line contains an integer, K, denoting the
748096 given integer.
475634 Each line i of the N subsequent lines (where 0 ≤ i <
Output: N) contains an integer describing A[i].
170882874
Explanation: Constraints
Given N = 2, M = 1, B = 748096, R = 475634. 1 <= N <= 10^5
1 <= K <= 10^5
There are two great chains: BR, BB. 1 <= A[i] <= 10^5
Hence, the output for this case is equal to
170882874.
Sample Test Cases
Case 3
Input: Case 1
4 Input:
3 2
813081 2
102149 2
Output: 1
6235092 Output:
Explanation: 3
Given N = 4, M = 3, B = 813081, R = 102149. Explanation:
Given N = 2, K = 2, A = [2, 1].
The output for this case is equal to 6235092.
We take the entire A as one subarray as [2, 1] with
maximum amazingness equal to 3.
Hence, the answer for this case is equal to 3.

External Document © 2025 Infosys Limited

Case 2
Input:
11. HARD
You are given a permutation p of length n and an
4 integer m. You now need to construct a directed
1 graph from the given permutation.
1
5 It is given that an edge exists between i and j if ai
3 < aj and abs(i - j) <= k, where abs(x) is the absolute
3 value of x.
Output:
12 Find the minimum value of k such that the longest
Explanation: path of the resulting graph is greater than or equal
Given N = 4, K = 1, A = [1, 5, 3, 3]. to m.

We can take 4 subarrays from A as [1], [5], [3], [3] Notes:

whose maximum amazingness is equal to 1 + 5 + 3 • The length of the path is equal to the number of
+ 3 = 12. nodes in that path.
Hence, the answer for this case is equal to 12.
Sample Input 1
Case 3 5
Input: 2
7 1
1 3
16 2
3 5
3 4
5
19 Sample Output 1
19 1
5
Output: Sample Output Description 1
70 Here, n = 5, m = 2
Explanation: p = [1, 3, 2, 5, 4]
Given N = 7, K = 1, A = [16, 3, 3, 5, 19, 19, 5].
If k >= 1 then, directed edge 1 -> 2 exists, so, we can
The maximum possible amazingness for this case is take the path 1 -> 2.
equal to 70. Hence, the minimum value of k required is 1.

So, answer is 1.

Sample Input 2
5
3
1
3
2
5
4

External Document © 2025 Infosys Limited

Sample Output 2 1, so the minimum value k is 0.
2 So, answer is 0.

Sample Output Description 2 Input Format

Here, n = 5, m = 3 The first line contains an integer, n, denoting the
p = [1 ,3, 2, 5, 4] number of elements in p.
The next line contains an integer, m, denoting the
If k >= 2, then we can take the path 1 -> 2 -> 3. length of the path.
Hence, the minimum value of k required is 2. Each line i of the n subsequent lines (where 0 ≤ i <
n) contains an integer describing p[i].
So, the answer is 2.
Constraints
Sample Input 3 1 <= n <= 10^5
5 1 <= m <= n
1 1 <= p[i] <= n
1
2 Sample Test Cases
3
4 Case 1
5 Input:
5
Sample Output 3 2
0 1
3
Sample Output Description 3 2
Here, n = 5, m = 1 5
p = [1, 2, 3, 4, 5] 4
Output:
Any node (without any edges) has a path of length 1

External Document © 2025 Infosys Limited

Explanation:
Here, n = 5, m = 2
p = [1, 3, 2, 5, 4]
12. HARD
Bob is playing a game called “Some Help”.

If k >= 1 then, directed edge 1 -> 2 exists, so, we can In this game, there are N soldiers, where N is an
take the path 1 -> 2. even number. There are also N treasure chests, each
Hence, the minimum value of k required is 1. with a bonus value given by the array Bonus. Here,
So, answer is 1. Bonus[i] denotes the bonus value for the ith chest.

Case 2 The power of each soldier is described by an array

Input: A of size N. For each i, the power of the ith soldier
5 is an integer between 1 and N/2, and each number
3 between 1 and N/2 occurs exactly twice in A.
1
3 The game has N rounds and each round proceeds
2 as follows:
5 1. For each ith player, Bob finds the first player
4 on their right whose power is a multiple of the
Output: power of the ith player. Let’s call this player R.
2 2. If no such player R is found, Bob does nothing.
Explanation: 3. If such a player R is found, Bob can choose a chest
Here, n = 5, m = 3 in the range [i, R] that gives the maximum bonus.
p = [1 ,3, 2, 5, 4] Let’s call the bonus of this chest as X.
4. The total XP is initially zero and for each round it
If k >= 2, then we can take the path 1 -> 2 -> 3. is increased by X.
Hence, the minimum value of k required is 2.
So, the answer is 2. Find the total XP that Bob can obtain from all N
Case 3 rounds.
Input:
5 Note:
1 • Each treasure chest can be used any number of
1 times.
2
3 Input Format
4 The first line contains an integer, N, denoting the
5 number of elements in A.
Output: Each line i of the N subsequent lines (where 1 ≤ i ≤
0 N) contains an integer describing A[i].
Explanation: Each line i of the N subsequent lines (where 1 ≤ i ≤
Here, n = 5, m = 1 N) contains an integer describing Bonus[i].
p = [1, 2, 3, 4, 5]
Constraints
Any node (without any edges) has a path of length 1 <= N <= 10^5
1, so the minimum value k is 0. 1 <= A[i] <= 10^5
So, answer is 0. 1 <= Bonus[i] <= 10^5

External Document © 2025 Infosys Limited

Sample Test Cases 1
2
Case 1 3
Input: 1
4 2
1 3
1 4
2 2
2 1
4 4
8 5
2 9
1 Output:
Output: 23
18 Explanation:
Explanation: Given N = 6, A = [1, 2, 3, 1, 2, 3], Bonus = [4, 2, 1, 4, 5,
Given N = 4, A = [1, 1, 2, 2], Bonus = [4, 8, 2, 1]. 9].

1. For the first soldier (power 1): 1. For soldier 1 (power 1):
The next soldier to the right with a power that is The first soldier to the right whose power is a
a multiple of 1 is the second soldier (power 1). multiple of 1 is soldier 2 (power 2).
The maximum bonus in the range [1st soldier, The maximum bonus in the range [1, 2] is
2nd soldier] is 8. max (4, 2) = 4. Add 4 to the total XP.
Add 8 to the total XP.
2. For the second soldier (power 1): 2. For soldier 2 (power 2):
The next soldier to the right with a power that is The first soldier to the right whose power is a
a multiple of 1 is the third soldier (power 2). multiple of 2 is soldier 5 (power 2).
The maximum bonus in the range [2nd soldier, The maximum bonus in the range [2, 5] is
3rd soldier] is 8. max (2, 1, 4, 5) = 5. Add 5 to the total XP.
Add 8 to the total XP.
3. For the third soldier (power 2): 3. For soldier 3 (power 3):
The next soldier to the right with a power that is The first soldier to the right whose power is a
a multiple of 2 is the fourth soldier (power 2). multiple of 3 is soldier 6 (power 3).
The maximum bonus in the range [3rd soldier, The maximum bonus in the range [3, 6] is
4th soldier] is 2. max(1, 4, 5, 9) = 9. Add 9 to the total XP.
Add 2 to the total XP.
4. The fourth soldier (power 2) has no subsequent 4. For soldier 4 (power 1):
soldiers to the right with a power that is a There are no soldiers to the right whose power is a
multiple of 2, so no bonus is added. multiple of 1. No bonus is added.
Total XP = 8 (from soldier 1) + 8 (from soldier 2) +
2 (from soldier 3) = 18 5. For soldier 5 (power 2):
Therefore, the total XP that Bob can get from N There are no soldiers to the right whose power is a
rounds is 18. multiple of 2. No bonus is added.

Case 2 6. For soldier 6 (power 3):

Input: There are no soldiers to the right whose power is a
6

External Document © 2025 Infosys Limited

multiple of 3. No bonus is added. multiple of 1 is the second soldier (power 1). The
maximum bonus in the range [1, 2] is max(16,8)=16.
Total XP = 4+5+9+5 = 23. Add 16 to the total XP.
Case 3
Input: 2. For soldier 2 (power 1):
4 The next soldier to the right whose power is a
1 multiple of 1 is the third soldier (power 2). The
1 maximum bonus in the range [2, 3] is max(8,4)=8.
2 Add 8 to the total XP.
2
16 3. For soldier 3 (power 2):
8 The next soldier to the right whose power is a
4 multiple of 2 is the fourth soldier (power 2). The
2 maximum bonus in the range [3, 4] is max(4,2)=4.
Add 4 to the total XP.
Output:
28 4. For soldier 4 (power 2):
Explanation: There are no soldiers to the right whose power is a
Given N = 4, A = [1, 1, 2, 2], Bonus = [16, 8, 4, 2]. multiple of 2. No bonus is added.

1. For soldier 1 (power 1): Total XP = 16 + 8 + 4 = 28.

The next soldier to the right whose power is a

External Document © 2025 Infosys Limited

13. HARD
You are given an array A of length N.
Explanation:
Given N = 5, A = [2, 2, 3, 1, 5].

We can select two pairs (1, 2) and (3,4) which satisfy

You have two functions defined as follows: the given conditions.
• frequency(left, right, value): Returns the number
of elements in the range [left, right] that are Hence, the answer for this case is equal to 2.
equal to value.
• distinct(left, right): Returns the number of distinct Case 2
elements in the range [left, right]. Input:
5
Find the number of pairs (i, j) that satisfy the 5
following condition: 5
• frequency(1 , i , A[i]) + frequency(j , N , A[j]) ≤ 5
.[distinct(1 , i) / 2] + [distinct(j , N) / 2]. 5
5
Since the answer can be very large, return it modulo Output:
109+7. 0
Explanation:
Note: Given N = 5, A = [2, 2, 3, 1, 5].
• Here ⌊X⌋ represents the greatest integer less
than or equal to X. There exists no pair which satisfy the given
• 1≤i<j≤N conditions.
Hence, the answer for this case is equal to 0.
Input Format
The first line contains an integer, N, denoting the Case 3
number of elements in A. Input:
Each line i of the N subsequent lines (where 0 ≤ i < 5
N) contains an integer describing A[i]. 1
2
Constraints 3
1 <= N <= 10^5 4
1 <= A[i] <= 10^9 5
Output:
5
Sample Test Cases Explanation:
Given N = 5, A = [1, 2, 3, 4, 5].
Case 1
Input: There are 5 pairs which satisfy the following
5 conditions are (1, 2), (1, 3), (1, 4), (1, 5), (2, 3).
2
2 Hence, the answer for this case is equal to 5.
3
1
5
Output:
2

External Document © 2025 Infosys Limited

14. HARD
You are given a tree which consists of N nodes. You
0 <= P[i] <= N
1 <= Q <= 10^5
2 <= Col <= 2
also will be given two distinct nodes A and B. 1 <= Queries[i][j] <= N

You are also given an array P where the parent of

node U is given by P[U]. Sample Test Cases
We define beauty of a node (U, V) as the number of Case 1
nodes that belong to both: Input:
• The subtree of U when the tree is rooted at A. 2
• The subtree of U when the tree is rooted at B. 1
2
You are given a 2D array Queries which consists of 0
Q queries. For each query you are given two nodes 1
U and V (U can be equal to V) and the answer to the 1
query is the beauty of (U, V). 2
12
Let K be equal to the answer to the last query Output:
(initially 0), then U and V changes as follows after 0
each query: Explanation:
• U = (U + K) mod N + 1. Given N = 2, A = 1, B = 2, P = [0, 1], Q = 1, Col = 2, Q
• V = (V + K) mod N + 1. = [[1, 2]].

Find the sum of answer to all queries. Since the Initialize K = 0.

answer can be large, return it modulo 109+7.
For the query (1, 2), calculate new values of U and V:
Input Format U = (1 + K) % N + 1 = (1 + 0) % 2 + 1 = 2
The first line contains an integer, N, denoting the V = (2 + K) % N + 1 = (2 + 0) % 2 + 1 = 1
number of elements in P.
The next line contains an integer, A, denoting the The transformed query becomes (2, 1).
given distinct node
The next line contains an integer, B, denoting the For the transformed query (2, 1), which in 0-based
given distinct node. indexing is (1, 0):
Each line i of the N subsequent lines (where 1 ≤ i ≤
N) contains an integer describing P[i]. The subtree of node 1 (when rooted at node 0)
The next line contains an integer, Q, denoting the includes node 1.
number of rows in Queries.
The next line contains an integer, Col, denoting the The subtree of node 0 (when rooted at node 1)
number of columns in Queries. includes node 0.
Each line i of the Q subsequent lines (where 0 ≤ i
< Q) contains Col space separated integers each There is no intersection between the subtrees of
describing the row Queries[i]. node 1 (rooted at node 0) and node 0 (rooted at
node 1).
Constraints
1 <= N <= 10^5 Therefore, the sum of answers to all queries is 0.
1 <= A <= N
1 <= B <= N

External Document © 2025 Infosys Limited

Case 2 Subtree of node 1 (when rooted at node 1) includes
Input: only node 1.
2
1 Intersection of subtrees rooted at nodes 0 and 1 is
2 just node 1.
0
1 Therefore, the beauty is 2.
2
2 Hence, the sum of answers to all queries is equal to
11 3.
12
Output: Case 3
3 Input:
Explanation: 4
Given N = 2, A = 1, B = 2, P = [0, 1], Q = 2, Col = 2, Q 1
= [[1, 1], [1, 2]]. 2
0
1. First Query (1, 1): 1
Calculate new values of U and V: 1
3
U = (1 + K) % N + 1 = (1 + 0) % 2 + 1 = 2 4
V = (1 + K) % N + 1 = (1 + 0) % 2 + 1 = 2 2
33
The transformed query becomes (2, 2). 13
44
Calculate the beauty of (2, 2): 12
Since U and V are the same, the beauty is the size of Output:
the subtree of node 2 when rooted at node 0 (A): 6
Explanation:
Subtree size of node 1 (0-based index of node 2) Given N = 2, A = 1, B = 2, P = [0, 1], Q = 2, Col = 2, Q
when rooted at 0: 1 (only node 1). = [[1, 1], [1, 2]].

Update K as: The answers for the 1st, 2nd, 3rd, and 4th query’s
K = Result = 1. are equal to 1, 2, 2, and 1 respectively.

Second Query (1, 2): Hence, the sum of answers to all queries is equal to
Calculate new values of U and V: 6.

U = (1 + K) % N + 1 = (1 + 1) % 2 + 1 = 1
V = (2 + K) % N + 1 = (2 + 1) % 2 + 1 = 2

The transformed query becomes (1, 2).

Calculate the beauty of (1, 2):

Subtree of node 0 (when rooted at node 0) includes
nodes 0 and 1.

External Document © 2025 Infosys Limited

For more information, contact [email protected]

© 2025 Infosys Limited, Bengaluru, India. All Rights Reserved. Infosys believes the information in this document is accurate as of its publication date; such information is subject to change without notice. Infosys
acknowledges the proprietary rights of other companies to the trademarks, product names and such other intellectual property rights mentioned in this document. Except as expressly permitted, neither this
documentation nor any part of it may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, printing, photocopying, recording or otherwise, without the
prior permission of Infosys Limited and/ or any named intellectual property rights holders under this document.

Infosys.com | NYSE: INFY Stay Connected