Latest Questions | Page 4

Village Voyage
A computer game "Village Voyage" has N villages (labeled 1 to N) at some distance from each other. The player starts from any village S and travels through all villages in a circular route, returning to the starting village S. Each village provides energy drinks, which are used to travel to the next village. One energy drink allows travel of one unit distance. The player loses if they run out of energy drinks at any point. Leftover energy accumulates.

At each village checkpoint, the player is given:
1) The number of energy drinks available in that village.
2) The distance from that village to the next village.

Write a program to help the player choose the starting village S such that they can complete the full circular tour. If multiple starting points are valid, return the one with the smallest label (1-indexed).

Assume a valid solution always exists.

Input Format
The first line contains an integer N, the number of villages.
The next N lines each contain two integers: the number of energy drinks and the distance to the next village.

Output Format
Print the smallest index of the village (1-based) from which the player can start and complete the tour.

Constraints
- N ≥ 0
- 1 ≤ energy drinks, distance ≤ 10^9 (assumed from context)

Sample Input 1
6
3 5
5 2
6 4
3 4
5 3
4 2

Sample Output 1
2

Explanation
Starting at village 2:
- Drinks: 5, distance: 2 → remaining: 3
- Next drinks: 6 → total: 9, distance: 4 → remaining: 5
- Next drinks: 3 → total: 8, distance: 4 → remaining: 4
- Next drinks: 5 → total: 9, distance: 3 → remaining: 6
- Next drinks: 4 → total: 10, distance: 2 → remaining: 8
- Next drinks: 3 → total: 11, distance: 5 → remaining: 6
The player successfully returns to starting point.

Sample Input 2
4
5 3
2 4
3 7
8 4

Sample Output 2
4 Show More

Academic Decathlon
Students are being selected for an academic decathlon team at a school. Each student has a skill level, and for a team to be uniform, the difference between any two consecutive skill levels (when arranged in increasing order) must be either 0 or 1.

Your task is to find the maximum possible team size.

Example
skills = [0, 12, 13, 9, 14]
Valid teams, when sorted, ar e (9, 10) and (12, 13, 14). These teams have sizes 2 and 3, respectively, so the maximum team size is 3.

Function Description
Complete the function findMaxTeamSize with the following parameter:
- int skills[n]: the skill levels of each student

Returns
- int: the maximum possible size of the team

Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ skills[i] ≤ 10^9

Input Format for Custom Testing

Sample Case 0

Sample Input
skills[] size n = 4
skills = [4, 13, 2, 3]

Sample Output
3

Explanation
There are two valid teams possible: (2, 3, 4) and (13). These have team sizes of 3 and 1, respectively. So the maximum possible team size is 3. Show More

Sum of Arrays
Given two arrays each of length n, arr1 and arr2, in one operation, any two elements of an array can be swapped. This can occur any number of times.

Find the maximum possible sum of i * (arr2[i] - arr1[i]) for all 1 ≤ i ≤ n after rearranging the arrays. Since the maximum possible sum can be large, return the value modulo (10^9 + 7).

Example
n = 4
arr1 = [2, 1, 3, 4]

arr2 = [2, 3, 2, 3]

Some of the possible rearrangements:
arr1: [2, 1, 3, 4], arr2: [2, 3, 2, 3] → sum = 0 + 4 + 0 - 4 = 0
arr1: [3, 1, 2, 4], arr2: [2, 3, 2, 3] → sum = -1 + 4 + 0 - 4 = -1
arr1: [3, 1, 2, 4], arr2: [3, 2, 2, 3] → sum = 0 + 2 + 0 - 4 = -2
The maximum sum possible is 7, and 7 modulo (10^9 + 7) = 7.

Function Description
Complete the function getMaxSumOfArray in the editor below.
getMaxSumOfArray has the following parameter(s):
- int arr1[n]: an array of integers
- int arr2[n]: an array of integers

Returns
- int: the maximum possible sum, modulo (10^9 + 7)

Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ arr1[i] ≤ 10^9
- 1 ≤ arr2[i] ≤ 10^9

Input Format for Custom Testing

Sample Case 0

Sample Input
arr1[] size n = 3
arr1 = [1, 2, 3]
arr2[] size n = 3
arr2 = [10, 10, 10]

Sample Output
50

Explanation
Given n = 3, arr1 = [1, 2, 3] and arr2 = [10, 10, 10].
If arr1 is changed to [3, 2, 1] and arr2 remains unchanged, the value of i * (arr2[i] - arr1[i]) = [7, 16, 27], and the total sum is 50.

Sample Case 1

Sample Input
arr1[] size n = 4
arr1 = [3, 1, 2, 6]
arr2[] size n = 4
arr2 = [2, 8, 4, 9]

Sample Output
48

Explanation
Original calculation: i * (arr2[i] - arr1[i]) = [-1, 14, 6, 12] → sum = 31
Rearranging arr1 to [6, 1, 2, 3] → new sum = 40
Rearranging arr1 to [6, 3, 2, 1] and arr2 to [2, 4, 8, 9] → i * (arr2[i] - arr1[i]) = [-4, 2, 18, 32] → sum = 48 Show More

Count Swaps During Custom Sorting
Analyze the efficiency of the following sorting algorithm by counting the number of swaps it performs:
For an array arr of size n:
1. Find the smallest pair of indices 0 ≤ i < j ≤ n-1 such that arr[i] > arr[j], where "smallest" means lexicographical ordering of pairs (i1, j1) < (i2, j2) if i1 < i2 or (i1 = i2 and j1 < j2).
2. If no such pair exists, th e algorithm stops.
3. Otherwise, swap arr[i] and arr[j] and search for the next pair.
Your task is to determine how many swaps this algorithm performs to sort a given array.

Example
n = 4, the size of arr
arr = [5, 1, 4, 2]

The algorithm performs these swaps:
[5, 1, 4, 2] → [1, 5, 4, 2] (swap indices 0 and 1)
[1, 5, 4, 2] → [1, 4, 5, 2] (swap indices 1 and 2)
[1, 4, 5, 2] → [1, 4, 2, 5] (swap indices 2 and 3)
[1, 4, 2, 5] → [1, 2, 4, 5] (swap indices 1 and 2)
The total number of swaps is 4.

Function Description
Complete the function howManySwaps in the editor with the following parameter(s):
int arr[]: the array to sort

Returns
int: the number of swaps

Constraints
1 ≤ n ≤ 10^5
1 ≤ arr[i] ≤ 10^9
All elements of arr are distinct.

Input Format for Custom Testing

Sample Case 0

Sample Input
arr[] size n = 3
arr = [7, 1, 2]

Sample Output
2

Explanation
[7, 1, 2] → [1, 7, 2] → [1, 2, 7] Show More

Stacey is coordinating a beach clean-up event with her university's Women in STEM Charity branch. The beach is covered with tin cans of varying weights arranged in a single line, indexed from 0 to n-1.

Stacey uses a scooper that can pick up three adjacent cans at a time. For each selection:

1. She identifies the lightest remaining can, with weight w
2. She uses the scooper to pick up that can along with its two adjacent cans (or fewer if at the edge)
3. She continues this process until there are no cans left on the beach

If multiple cans have the lightest weight, Stacey selects the one with the smallest index. If a can has fewer than two adjacent cans, she removes the available adjacent cans.

Determine the sum of the weights of the lightest cans she picks in each selection.

Example
Let there be n = 5 cans on the beach with weights represented by cans = [5, 4, 1, 3, 2].

- First, choose the minimum weight, i.e., 1, and add that weight to the total. The cans with weights 4, 1, and 3 are removed. The array of cans is now [5, 2].
- Then, choose the minimum weight, i.e., 2, and add that weight to the total. The cans with weights 2 and 5 are removed. There are no more cans left.

Hence, the total is 1 + 2 = 3.

Function Description
Complete the function findTotalWeight in the editor with the following parameter:
int cans[n]: the weights of the cans on the beach

Returns
int: the sum of the minimum-weight cans at each selection

Constraints
· 3 ≤ length of cans ≤ 2000
· 1 ≤ cans[i] ≤ 10^5

Sample Case 0
Input
cans = [6, 4, 9, 10, 34, 56, 54]

Output
68

Explanation
- First, select the minimum weight, 4. Its adjacent cans (6 and 9) are also removed → [10, 34, 56, 54]
- Next, select 10. Its adjacent (34) is also removed → [56, 54]
- Finally, select 54. Its adjacent (56) is removed → []
Sum = 4 + 10 + 54 = 68

Sample Case 1
Input
cans = [132, 45, 65, 765, 345, 243, 75, 67]

Output
1120

Explanation
- Select 45 → remove 132, 45, 65 → [765, 345, 243, 75, 67]
- Select 67 → remove 75, 67 → [765, 345, 243]
- Select 243 → remove 345, 243 → [765]
- Select 765 → remove 765 → []
Sum = 45 + 67 + 243 + 765 = 1120 Show More

Perform a series of operations on a given array of integers. Each operation consists of two indices that define a subarray to reverse, inclusive of those indices.

Return the resulting array after all operations have been applied in the specified order.

Example
arr = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
operations = [[0, 9], [4, 5], [3, 6], [2, 7], [1, 8], [0, 9]]

In the first operation, all elements are reversed. There are no elements to the right or left.
In the second operation, only the elements in the subarray defined by indices 4 to 5 are reversed. Those to the left and right remain unchanged.
Similar logic is applied for further operations.

Function Description
Complete the function performOperations in the editor with the following parameters:
int arr[n]: an array of integers
int operations[q][2]: a 2-dimensional array of starting and ending indices

Returns
int[n]: the final array after all operations have been performed

Constraints
· 1 ≤ n, q ≤ 10^3
· 0 ≤ arr[i] ≤ 10^3
· 0 ≤ operations[i][0] ≤ operations[i][1] < n

Sample Case 0

Input
arr = [1, 2, 3]
operations = [[0, 2], [1, 2], [0, 2]]

Output
[2, 1, 3]

Explanation
Step 1: Reverse arr[0:2] → [3, 2, 1]
Step 2: Reverse arr[1:2] → [3, 1, 2]
Step 3: Reverse arr[0:2] → [2, 1, 3] Show More

Data scientists at Amazon are working on a utility for detecting similar passwords in their security systems. The utility finds anagram patterns in pairs of passwords. A pair of passwords is considered similar if they are anagrams after removing any number of occurrences of at most one character from each password.

Given n pairs of passwords, for each pair, attempt to make them anagrams. Return a list of boolean values, one for each pair, where True means a pair is similar.

Example
Given n = 1, and the strings password1 = "safddadfs" and password2 = "famafmss". The strings are anagrams after removing all the occurrences of character 'd' from the first password and character 'm' from the second password. Return [True].

Note: It is not required that all instances of a character be removed. For example, given 'aab' and 'ba', one 'a' can be removed from 'aab' to leave 'ab'.

Function Description
Complete the function findSimilarPasswords in the editor below.

findSimilarPasswords has the following parameter(s):
string password[n][2]: the pairs of passwords.

Returns
bool[n]: "true" if the pair is special, and "false" otherwise

Constraints
· 1 ≤ n ≤ 10
· 1 ≤ |password[i][0]|, |password[i][1]| ≤ 10,000
· The strings in password1 and password2 consist of lowercase English letters only.

Sample Case 0
Input
n = 2
password1 = "abcee", password2 = "acdeedb"
password1 = "sljffsaje", password2 = "sljsje"

Output
[True, False]

Explanation
For pair 1, remove 'd' from the second string and leave the first string untouched.
For pair 2, password1 contains 'f' and 'a' which are not in password2. They cannot be anagrams after removing only 1 character from password1.

Sample Case 1
Input
n = 1
password1 = "abcdee", password2 = "abcde"

Output
[True]

Explanation
Remove one occurrence of 'e' from password1. Show More

To be efficient, Amazon must optimally distribute parcels among their delivery agents. Initially, there are n agents, and the number of parcels assigned to the i-th agent is initialParcels[i]. There are additionalParcels parcels that also need to be shipped. The additional parcels should be assigned such that the maximum number of parcels assigned to any one agent is minimized.

Given an integer array, initialParcels, and an integer, additionalParcels, find the minimum possible value of the maximum number of parcels any agent must deliver.

Example
Suppose n = 5, initialParcels = [7, 5, 1, 9, 1], and additionalParcels = 25.
An optimal assignment is shown:

Initial Parcels | Additional Parcels | Total Parcels
7 | 3 | 10
5 | 5 | 10
1 | 9 | 10
9 | 1 | 10
1 | 7 | 8

There are other possible optimal assignments, but the minimum value of the maximum number of parcels any agent will deliver is 10.

Function Description
Complete the function minimizeMaxParcelLoad in the editor below.

minimizeMaxParcelLoad takes the following arguments:
int initialParcels[n]: the initial number of parcels assigned to the agents
long int additionalParcels: the additional parcels to be assigned

Returns
long int: the minimum possible value of the maximum number of parcels an agent must deliver

Constraints
· 1 ≤ n ≤ 10^5
· 1 ≤ additionalParcels ≤ 10^15
· 1 ≤ initialParcels[i] ≤ 10^9

Sample Input
initialParcels = [1, 2, 3]
additionalParcels = 3

Sample Output
3

Explanation
It is optimal to assign 2 additional parcels to the first agent and 1 additional parcel to the second agent. Finally, each agent will have to deliver 3 parcels. Show More

The Amazon warehouse receives a multitude of packages every day, each assigned a unique identifier from 1 to n. The warehouse manager must sort the packages, not by their identifiers, but rather through a specific process defined by a permutation packageSequence that ensures optimal processing.

Initially, the number of sorted packages, sortedCount, is zero. In each operation, the manager sifts through the packages from left to right. If the current package's identifier aligns with the next one to be sorted (i.e., packageSequence[i] = sortedCount + 1), the manager sorts it and increments sortedCount by one. If the current package is not next in the sorting sequence, the manager overlooks it.

Determine the number of operations required by the manager to sort all the packages. One operation indicates a complete check from the first package to the last.

Note: A permutation is a sequence consisting of integers from 1 to n, of length n, containing each integer exactly once. For example, [1, 3, 2] is a permutation, while [1, 2, 1] is not.

Example 1
n = 5
packageSequence = [5, 3, 4, 1, 2]
Initially sortedCount = 0. In the first operation, the manager does the following:
At the end of the third operation, sortedCount is 5, and all packages are sorted.
Thus, 3 operations are required to handle all the packages. Hence, the answer is 3.

Example 2
n = 5
packageSequence = [3, 1, 4, 2, 5]
In the first operation, the manager:
1. Overlooks packageSequence[0] = 3.
2. Sorts packageSequence[1] = 1 as packageSequence[1] = sortedCount + 1 = 1 (now sortedCount becomes 1).
3. Overlooks packageSequence[2] = 4.
4. Sorts packageSequence[3] = 2 as packageSequence[3] = sortedCount + 1 = 2 (now sortedCount becomes 2).
5. Overlooks packageSequence[4] = 5.
At the end of the first operation, sortedCount is 2.

In the second operation, the manager:
1. Sorts packageSequence[0] = 3 as packageSequence[0] = sortedCount + 1 = 3 (now sortedCount becomes 3).
2. Overlooks packageSequence[1] = 1.
3. Sorts packageSequence[2] = 4 as packageSequence[2] = sortedCount + 1 = 4 (now sortedCount becomes 4).
4. Overlooks packageSequence[3] = 2.
5. Sorts packageSequence[4] = 5 as packageSequence[4] = sortedCount + 1 = 5 (now sortedCount becomes 5).
At the end of the second operation, sortedCount is 5, and all packages are sorted.
Thus, 2 operations are required to handle all the packages. Hence, the answer is 2.

Function Description
Complete the function getNumberOperations in the editor below.

getNumberOperations has the following parameters:
int packageSequence[n]: an array of integers symbolizing the sequence of packages.

Returns
int: the number of operations the warehouse manager has to perform to sort all packages.

Constraints
· 1 ≤ n ≤ 10^6
· 1 ≤ packageSequence[i] ≤ n
· packageSequence is a permutation of length n. 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 sizes amon g the first i products. Mathematically, this is defined as:

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

Your goal is to arrange the products in a way that minimizes the total variation, i.e., the sum of variation[1] + variation[2] + ... + variation[n]. 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^6

Input Format for Custom Testing:
The first line contains an integer, n, the number of elements in productSize.
Each of the next n lines contains an integer describing productSize[i].

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

Sample Output:
4 Show More