Latest Questions | Page 7

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

Prince was playing games on his computer all day, so his father decided to give him the task of arranging the books kept on the bookshelf. Prince can arrange the books on the bookshelf according to the book type, where an English alphabet denotes each book type. He is required to arrange the books in such a way that the book type having the lowest number of copies is kept first, and the book type having the maximum number of copies is kept last. If two or more book types have the same number of books, arrange them in lexicographically ascending order.

You are given two numbers, L and R. Return the total number of books of type A E I O U between [L, R], which are present on the bookshelf.

Input Format: The first line contains an integer n denoting the number of books. The second line contains n space-separated uppercase English alphabets that denote the type of book. The third line contains two space-separated integers denoting L and R.

Output Format: Return the total number of books of type A E I O U between [L, R] on the bookshelf.

Constraints: 1 <= N <= 100. The book type is uppercase English alphabet only.

Sample Testcase 1
Input:
7
BBAABCC
1 2

Output:
2

Explanation: In this case, 2 books are of type A, 2 books are of type C, and 3 books are of type B. Hence, after arranging them according to the given condition, the shelf looks like this: AACCBBB (let's say string y). Here, the frequency of A and C are the same, so they are sorted in lexicographically ascending order. The distinct types of book that is kept on the shelf after arrangement is ACB (let's say string x). The value of L=1 and R=2. Therefore, the number of books of type A E I O U in the range [1,2] in string x is 1, i.e., the type A. The number of books of type A in string y is 2; hence, the answer is 2.

Sample Testcase 2
Input:
7
CABCABB
1 3

Output:
[Output not provided] Show More

You are given an NxN matrix 'mat' where each cell contains one of the two characters 'a' or 'z'. A man stands at the bottom-right corner of the matrix (mat[N-1][N-1]) and wants to reach the top-left corner of the matrix (mat[0][0]). The man can only move up or left at each step. Your task is to find the lexicographically smallest string that can be formed by following any valid path from mat[N-1][ N-1] to mat[0][0]. Additionally, determine the number of distinct paths that yield this lexicographically smallest string.

Input Format: First line of input takes integer 'N' denoting the dimensions of the matrix 'mat'. The next 'N' lines take 'N' space-separated characters either 'a' or 'z' representing the values in the matrix 'mat'.

Output Format: The first line of output shows the lexicographically smallest string that can be formed by any valid path from mat[N-1][N-1] to mat[0][0]. The last line of the output shows the number of distinct paths that yield this lexicographically smallest string.

Constraints: 2 <= N <= 40

Sample Testcase 1
Input:
3
z a z
a a a
z z z

Output:
zaaaz
2

Explanation: Starting from mat[2][2] = 'z', the next move can either be up or left. If we move up to mat[1][2] = 'a', then move left to mat[1][1] = 'a', then move either up or left to mat[1][0] or mat[0][1] = 'a', and finally move up to mat[0][0] = 'z', the path forms the string "zaaaz", the lexicographically smallest string. Therefore, the number of possible paths = 2.

Sample Testcase 2
Input:
4
z z a z
z z a a
z z a z
a a a a

Output:
aaaaazz
1

Explanation: Starting from mat[3][3] = 'a', the next move can either be up or left. Moving up to mat[2][3] = 'a', then up to mat[1][3] = 'a', then up to mat[0][3] = 'a', then left to mat[0][2] = 'a', then left to mat[0][1] = 'z', and finally left to mat[0][0] = 'z', the path forms the string "aaaaazz", which is the lexicographically smallest string. Therefore, the number of possible paths that form the string is 1. Show More

You want to transmit N packets over a network where each packet needs to be encrypted before being sent. Each packet has some integer data represented by the array data[]. To encrypt the data, you need to perform operations on the N packets. You are given 3 more arrays of length Q: 1. typeOfOperation[]: each element denotes the type of operation to be performed on data[i] (1 or 2), 2. numberOfPack ets[]: each element denotes the number of packets the operation applies to, 3. X[]: the value used in the operation.

There are two types of operations:
Type 1: Modify the first numberOfPackets[i] elements of data[] as (data[0] xor X[i], data[1] xor X[i], ..., data[a-1] xor X[i]).
Type 2: Modify the last numberOfPackets[i] elements of data[] as (data[N-1] xor X[i], data[N-2] xor X[i], ..., data[N-a] xor X[i]).

Your task is to return the encrypted data[] array after performing Q operations.

Input:
input1: Array of integers denoting data[]
input2: Integer N, the length of data[]
input3: Array of integers denoting typeOfOperation[]
input4: Array of integers denoting numberOfPackets[]
input5: Array of integers denoting X[]
input6: Integer Q, the length of the above 3 arrays

Output:
Return an array of N integers denoting the encrypted data[].

Example 1:
input1: [10, 9, 12, 3]
input2: 4
input3: [1, 2]
input4: [2, 1]
input5: [5, 10]
input6: 2
Output: [15, 12, 12, 9]

Explanation:
First operation is Type 1 on the first 2 packets: (10 xor 5) = 15, (9 xor 5) = 12 → data = [15, 12, 12, 3]
Second operation is Type 2 on the last 1 packet: (3 xor 10) = 9 → data = [15, 12, 12, 9]

Example 2:
input1: [30, 10, 3]
input2: 3
input3: [2, 1]
input4: [1, 2]
input5: [6, 18]
input6: 2
Output: [12, 24, 5]

Explanation:
First operation is Type 2 on the last 1 packet: (3 xor 6) = 5 → data = [30, 10, 5]
Second operation is Type 1 on the first 2 packets: (30 xor 18) = 12, (10 xor 18) = 24 → data = [12, 24, 5] Show More