Latest Questions

There are 'N' coders standing in a line, where i denotes the ith position of a coder with a rating of Ri. All ratings are distinct.

You have to form a team of 3 from amongst them with the condition:
- Any three coders with positions (i, j, k) and ratings (Ri, Rj, Rk) can form a team when ("Ri < Rj < Rk" or "Ri > Rj > Rk") and (1 <= i < j < k <= N).

You have to find out how many such teams e xist (1 coder can be part of multiple teams).

Input:
N - 5
Ratings - 5 23 14

Output:
3
(5,2,1), (5,3,1), (2,3,4) Show More

A birthday party was attended by N number of kids, and each kid was given a unique ID ranging from 1 to N. As a return gift, there are T toys that must be distributed to the kids.

The host decided the best way to do this is by sitting the kids down in a circle (ordered by ascending ID), and then, starting with a random number D (between 1 and N), distribute one toy at a time to each sequentiall y numbered kid until all toys are distributed.

For example, if the host picks a random number D = 2, the gift distribution order would be: (2, 3, 4, 5, ... N-1, N, 1, 2, 3, 4, ...) until all T toys are distributed. The very last toy is damaged.

Your task is to determine which kid will receive the last (damaged) toy, so they can be informed and asked to exchange it at the shop.

Input:
- N (number of kids)
- T (number of toys)
- D (starting ID where distribution begins)

Output:
Print the ID of the last kid who will receive the damaged toy.

Constraints:
- 1 ≤ N ≤ 1000
- 1 ≤ T ≤ 1000
- 1 ≤ D ≤ N

Sample Input:
5
2
1

Sample Output:
2

Explanation:
There are N=5 kids and T=2 toys. Distribution starts at kid ID 1 (D=1). The distribution follows this pattern:
- Kid 1 receives the first toy.
- Kid 2 receives the second (and last) toy.

Thus, we must inform Kid 2 about the damaged toy, so we print `2` on a new line. Show More

Given a matrix of size m * n, where m denotes the number of rows (starting with index 0) and n denotes the number of columns (starting with index 0), the matrix will hold distinct integers as elements.

We need to find the distinct number of positional elements that are either the minimum or maximum in their corresponding row or column. If any row or any column has multiple minimum or maximum el ements, return -1.

Example:

Matrix of size 3 * 3:
1 3 5
8 2 7
4 9 6

The expected output is 7.

In this example, we identified the output as 7 based on the following:

- 1: Minimum in both its row and column.
- 4: Maximum in its row.
- 2: Minimum in both its row and column.
- 9: Maximum in both its row and column.
- 8: Maximum in both its row and column.
- 7: Maximum in its column.
- 6: Minimum in its row.

Thus, the total number of distinct elements that are either the minimum or maximum in their respective row or column is 7.

Input:
- m: Integer representing the number of rows.
- n: Integer representing the number of columns.
- matrix: m x n matrix of integers.

Output:
- r: Integer representing the total number of distinct elements which are either the minimum or maximum in their corresponding row or column.

Constraints:
- 0 < m, n < 100
- Elements in the matrix are positive integers. Show More

A traveler is traveling from the city of Zeta to Omega. He starts with X amount of money. Every day he spends some money and may also work on certain days to earn money. On some days, he may earn more than he spends, and on other days, he may spend more than he earns.

You are given an array of integers, which represents his net savings (earnings - expenses) on any day. Your task is to find out the minimum amount the traveler should begin with to ensure that he always has some money (> 0) at the end of any day.

Constraints:
- -200 <= a <= 200, where `a` are the elements of the array.
- 0 < i <= 100, where `i` is the array length.
- X >= 0

Example:
Input:
3 // Array length
4 // Array elements start
2
-3

Output:
0

Explanation:
Traveler saves $4 on the first day, $2 on the second day, and $-3 on the third day (expenses are more on the third day than earnings).

- End of the first day, he has X + $4.
- End of the second day, he has X + $(4 + 2).
- End of the third day, he has X + $(4 + 2 - 3).

So, effectively, the traveler can start with X = $0 to always ensure he has some money at the end of each day. Show More

As an operations engineer at Amazon, you are responsible for organizing the distribution of n different items in the warehouse. The size of each product is provided in an array `productSize`, where productSize[i] represents the size of the i-th product.

You construct a new array called `variation`, where each element `variation[i]` is the difference between the largest and smallest product size s among the first i products. Mathematically, this is defined as:

variation[i] = max(productSize[0], productSize[1], ..., productSize[i]) - min(productSize[0], productSize[1], ..., productSize[i])

Your goal is to arrange the products in a way that minimizes the total variation, i.e., the sum of variation[0] + variation[1] + ... + variation[n-1]. Determine the minimum possible value of this sum after you have reordered the products.

Example:
n = 3
productSize = [3, 1, 2]

By reordering the products as productSize = [2, 3, 1]:

- variation[0] = max(2) - min(2) = 2 - 2 = 0.
- variation[1] = max(2, 3) - min(2, 3) = 3 - 2 = 1.
- variation[2] = max(2, 3, 1) - min(2, 3, 1) = 3 - 1 = 2.

The sum is variation[0] + variation[1] + variation[2] = 0 + 1 + 2 = 3. This is the minimum possible total variation after rearranging.

Function Description:
Complete the function `minimizeVariation` in the editor below.

`minimizeVariation` has the following parameter(s):
- int productSize[n]: The size of each product.

Returns:
- int: The minimum possible total variation after rearranging the array productSize.

Constraints:
- 1 ≤ n ≤ 2000
- 1 ≤ productSize[i] ≤ 10^9

Sample Input 0:
productSize = [4, 5, 4, 6, 2, 6, 1, 1]

Sample Output 0:
16

Explanation:
By reordering the products as productSize = [1, 1, 2, 4, 4, 5, 6]:

- variation[0] = max(1) - min(1) = 1 - 1 = 0.
- variation[1] = max(1, 1) - min(1, 1) = 1 - 1 = 0.
- variation[2] = max(1, 1, 2) - min(1, 1, 2) = 2 - 1 = 1.
- variation[3] = max(1, 1, 2, 4) - min(1, 1, 2, 4) = 4 - 1 = 3.
- variation[4] = max(1, 1, 2, 4, 4) - min(1, 1, 2, 4, 4) = 4 - 1 = 3.
- variation[5] = max(1, 1, 2, 4, 4, 5) - min(1, 1, 2, 4, 4, 5) = 5 - 1 = 4.
- variation[6] = max(1, 1, 2, 4, 4, 5, 6) - min(1, 1, 2, 4, 4, 5, 6) = 6 - 1 = 5.

The minimum total variation is variation[0] + variation[1] + variation[2] + variation[3] + variation[4] + variation[5] + variation[6] = 0 + 0 + 1 + 3 + 3 + 4 + 5 = 16. Show More

Given a matrix of size m * n, where m denotes the number of rows (starting with index 0) and n denotes the number of columns (starting with index 0). The elements in the matrix are populated with values either 1 or 0. A 1 indicates the matrix position is available for establishing the connection, and a 0 indicates the matrix position is not available for establishing the connection.

We need to connect the available adjacent positions vertically, horizontally, and diagonally, and count the number of distinct connections established.

For example, given a matrix of size 3 * 4, the elements are stored as follows:

The expected output is 8.

In the above example, the positions are connected as follows, and hence 8 connections are possible:
1. (0,0) -> (1,1)
2. (2,0) -> (1,1)
3. (1,1) -> (1,2)
4. (1,2) -> (0,3)
5. (1,2) -> (1,3)
6. (1,2) -> (2,3)
7. (0,3) -> (1,3)
8. (1,3) -> (2,3)

Input:
- m: integer representing the number of rows
- n: integer representing the number of columns
- matrix: m * n matrix

Output:
- r: integer representing the total number of connections

Constraints:
- 0 < m, n < 100
- Connection is always between two adjacent cells (horizontally, vertically, or diagonally). Show More

Amazon is launching a revolutionary security feature that incorporates an advanced antivirus program, adept at identifying and halting potential threats. This framework manages n active programs, each with a unique Program Identifier (PID). The antivirus program evaluates the overall security risk of the system using a specialized algorithm.

The algorithm analyzes contiguous subarrays of Progr am Identifiers (PIDs) represented by the array pid. For each subarray, it calculates the sum of the PIDs and divides this sum by a constant k. The remainder obtained from this division is compared to the number of programs in the subarray. A subarray is flagged if the remainder equals the number of programs within it and is considered as malicious. The overall security risk is determined by the total count of such flagged subarrays.

Formally, given an array pid of size n, representing the PIDs of the programs running on the computer, and an integer k, with which remainder has to be checked. The task is to calculate the system's security risk level. Remainder is defined as the remaining part after performing the division. For example, the remainder of 13 with 5 is 3. A subarray is a continuous portion of an array. For example, in the array [5, 7, 9, 11] possible subarrays include [5,7], [7, 9, 11], [11] etc. Note that a subarray maintains the original order of elements and consists of consecutive elements.

Example: n = 4, pid = [1, 3, 2, 4], k = 4. There are 2 different malicious contiguous subarrays:

1. Subarray from index [0, 0] with pid given by: [1], the remainder of the sum of pid (sum = 1) of the subarray [1] with k = 4 is 1 (the remainder of 1 with 4 is 1), which is equal to the number of elements in the subarray, i.e., 1. Hence, this subarray is flagged.
2. Subarray from index [2, 3] with pid given by: [2, 4], the remainder of the sum of pid (sum = 2 + 4 = 6) of the subarray with k = 4 is 2, which is equal to the number of elements in the subarray, i.e., 2. Hence, this subarray is flagged.

An example of a contiguous subarray which is not flagged:
- Subarray from index [0, 1] with pid given by: [3, 2] is not flagged because the remainder of the sum of PIDs = 3 + 2 = 5, whose remainder with k = 4, is 1, while there are 2 elements in the subarray. Hence, the subarray is not malicious.

Hence, the overall security risk of the system is 2. Thus, return 2 from the function.

Function Description: Complete the function findSecurityLevel in the editor below.

findSecurityLevel has the following parameters:
int pid[n]: an array of integers denoting the PIDs of the programs
int k: an integer with which the remainder is checked

Returns: long: an integer denoting the overall security risk of the system

Constraints:
- 1 ≤ n ≤ 2 * 10^5
- 1 ≤ pid[i] ≤ 10^9
- 1 ≤ k ≤ 10^9 Show More

Amazon Games has recently launched a new game called Match the Column in which players are supposed to match the numbers from the left column to the right column like a traditional match the column game. Given an array of integers, match, the i-th index in the left column is matched with match[i] in the right column. There is a twist: Intersecting matches, illustrated below, are not allowed.

De termine the maximum number of matches possible without any intersections.

In the left illustration, match = [4, 3, 2, 3, 5].

More formally, two matches (i, match[i]) and (j, match[j]) intersect if i < j and match[i] > match[j] or i > j and match[i] ≤ match[j].

Example: Given n = 4, match = [2, 2, 1, 3]. There cannot be more than 2 valid matches, as shown above. Note that both illustrations are optimal. Return 2.

Function Description: Complete the function getMaxMatching in the editor below.

getMaxMatching has the following parameter: int match[n]: an array of integers

Returns: int: the maximum number of matchings possible

Constraints:
- 1 ≤ n ≤ 10^5
- 1 ≤ match[i] ≤ n

Input Format For Custom Testing:

Sample Case 0

Sample Input For Custom Testing:

STDIN
6
3
1
4
2
3
5

Function match[] size n = 6 match = [3, 1, 4, 2, 3, 5]

Sample Output:
4

Explanation: Given n = 6, match = [3, 1, 4, 2, 3, 5], the matchings are (1, 3), (2, 1), (3, 4), (4, 2), (5, 3), (6, 5). It is optimal to match (2, 1), (4, 2), (5, 3), (6, 5), none of which intersect. Show More

Todd has a grid sheet of paper measuring N by M units and plans to draw squares on it. Each cell in the grid contains an integer X, which represents the center of a square with dimensions (2X - 1) by (2X - 1). Given this grid, Todd wants to know how many squares enclose specific cells. You will be asked Q queries, each with two numbers A and B. Your task is to determine how many of Todd's squares enclose the cell (A, B).

Note: Todd's squares can intersect and form additional shapes, but you only need to consider the original squares he draws, not any new shapes formed by intersections. Even if one square entirely overlaps another, both should be considered separately. The coordinates (A, B) are 0-based. grid[i][j] will contain integer values such that Todd's squares are always contained inside the grid.

Input Format:
The first line contains three integers N, denoting the number of rows in the grid, M, the number of columns in the grid, and Q, the number of queries. The next N lines each contain M integers, representing the grid. The next Q lines each contain two integers: A and B, representing the cell coordinates for the queries.

Output Format:
For each query, print a single integer representing the number of squares that enclose the given cell (A, B).

Constraints:
1 <= N, M <= 10^3
0 <= grid[i][j] <= min(N/2, M/2)
1 <= Q <= 10^5
0 <= A <= N-1
0 <= B <= M-1

Sample Testcase 1:
Input:
5 5 1
0 0 0 0 0
0 0 0 0 0
0 0 2 0 0
0 0 0 2 0
0 1 0 0 0
2 2

Output:
2

Explanation:
Todd's art will look like this: For the query (2, 2), the number of squares enclosing the point is 2 — the red square and the green square.

Sample Testcase 2:
Input:
3 3 2
0 1 0
0 2 1
0 0 0
0 1
1 1

Output:
2
1

Explanation:
Todd's art will look like this: The first query (0, 1) is enclosed by 2 squares, and the second query (1, 1) is enclosed by 1 square. Show More

You are given an 8x8 chess board. The board has your rook denoted by 'R' and the rest of the cells are either blank, denoted by 'B' or they have some piece upon them denoted by 'P'. You can move over the blank cells only. A rook can move along its entire row or column in 1 move, up to the point where blank spaces are available.

If current coordinates of a rook are (x, y) then rook can move in t he following ways in 1 move: Move from (x, y) to (x-1, y), (x-2, y), (x-3, y) and so on; Move from (x, y) to (x+1, y), (x+2, y), (x+3, y) and so on; Move from (x, y) to (x, y-1), (x, y-2), (x, y-3) and so on; Move from (x, y) to (x, y+1), (x, y+2), (x, y+3) and so on. The rook can't move outside the board. As soon as the rook encounters a 'P' cell in its path it stops and can't move further.

The rook needs to reach cell (8,8) in order to prove its worth. Find the minimum number of moves the rook would take to reach cell (8,8) or print -1 if it is impossible to do so. The board follows 1 based indexing. The board contains a single cell with value 'R'. Each string consists of only 3 types of characters: 'P', 'B', or 'R'.

Input Format: The first line contains a single integer T, the number of testcases. Lines from 1 to 8 of each test case take input of a string of size 8 denoting the arrangement on the chess board.

Output Format: Print the minimum number of moves required to reach cell (8,8) or print -1 if it is impossible to do so.

Constraints: 1 <= T <= 10^8, length of each string = 8.

Sample Testcase 1:
Input:
1
BBBBBBBB
BRPPPPPP
PBPPPPPP
PBPPPPPP
PBBBBPPP
PPBBBBBB
PPPPPPPB
PPPPPPPB

Output:
5

Explanation:
In the first move the rook can move from cell (2,2) to (5,2) as all cells in between are blank, i.e. cells (3,2), (4,2), (5,2) are blank. In the second move the rook can move from cell (5,2) to (5,4) as all cells in between are blank, i.e. cells (5,3), (5,4) are blank. In the third move the rook can move from cell (5,4) to (6,4). In the fourth move the rook can move from cell (6,4) to (6,8). In the fifth move the rook can move from cell (6,8) to (8,8). Path: (2,2) > (5,2) > (5,4) > (6,4) > (6,8) > (8,8). Thus, it took 5 moves for the rook to reach cell (8,8). There might be other possible paths too but none of them would take less than 5 moves.

Sample Testcase 2:
Input:
BBBBBBBB
BBBBBBBB
RBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBPP
BBBBBBPB

Output:
-1

Explanation:
Since cell (8,8) is blocked by pieces ('P') from all directions, it is impossible for the rook to reach cell (8,8) regardless of the path taken. Show More