Latest Questions | Page 3

Number in a range

You are given three integers L, R, and K. A number X represents a lucky number if the binary representation of X contains the pattern 101 as a substring. Determine the Kth lucky number between L and R. If the Kth lucky number does not exist, then print -1.

Function description

Complete the solve function. This function takes the following 3 parameters and returns the Kth lucky number in between L and R.

Parameters:
- L: Represents an integer denoting the value of L
- R: Represents an integer denoting the value of R
- K: Represents an integer denoting the Kth lucky number to be found

Input format for custom testing

Note: Use this input format if you are testing against custom input or writing code in a language where we don't provide boilerplate code.

- The first line contains T, which represents the number of test cases.
- For each test case:
- The first line contains three space-separated integers L, R, and K.

Output format

For each test case, print the Kth lucky number in the range [L, R] on a new line. If the Kth lucky number does not exist, then print -1.

Constraints

1 ≤ T ≤ 200
1 < L ≤ R ≤ 10^18
1 ≤ K ≤ 10^18

Sample input

6
5 40 6
5 12 4
9 20 5
7 7 1
14 37 4
13 25 4

Sample output

21
-1
-1
-1
23
22

Explanation:

For test case 1: All lucky numbers between 5 and 40 are 5, 10, 11, 13, 20, 21, 22, 23, 26, 27, 29, 37, and 40. The sixth lucky number is 21.
For test case 2: All lucky numbers between 5 and 12 are 5, 10, and 11. There are less than 4 lucky numbers, so print -1.
For test case 3: All lucky numbers between 9 and 20 are 10, 11, and 13. There are less than 5 lucky numbers, so print -1.
For test case 4: There are 0 lucky numbers between [7, 7], so print -1.
For test case 5: All lucky numbers between 14 and 37 are 20, 21, 22, 23, 26, 27, 29, and 37. The fourth lucky number is 23.
For test case 6: All lucky numbers between 13 and 25 are 13, 20, 21, 22, and 23. The fourth lucky number is 22.

Note:

Your code must be able to print the sample output from the provided sample input. However, your code is run against multiple hidden test cases. Therefore, your code must pass these hidden test cases to solve the problem statement.

Limits

Time Limit: 1.0 sec(s) for each input file
Memory Limit: 256 MB
Source Limit: 1024 KB

Allowed Languages: Bash, C, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java 8, Java 14, JavaScript(Node.js), Julia, Kotlin, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, Racket, Ruby, Rust, Scala, Swift, TypeScript, Visual Basic Show More

You are given a board of size M × N where each cell can be either empty ('O') or a wall ('X').
A robot is initially placed at the top-left cell (0,0) and can move in four directions: up, down, left, and right — but not diagonally.
The robot can only move through empty cells and cannot pass through or land on walls.

Your task is to print the maximum number of empty cells the robot can vi sit starting from the top-left cell, including the starting cell.

Input Format:
- First line: Two integers M and N — the number of rows and columns of the board.
- Next M lines: Each contains a string of length N, consisting of characters 'O' and 'X'.

Output Format:
- A single integer — the number of empty cells the robot can visit.

Constraints:
- 1 ≤ M, N ≤ 100

Sample Input 1:
4 3
OXO
OOX
XOO
OOO

Sample Output 1:
8

Explanation:
Starting at (0,0), the robot can move through a connected component of 8 'O' cells. One cell ('O' at (0,2)) is isolated and cannot be reached.

Sample Input 2:
4 3
000
00X
OXO
X00

Sample Output 2:
6

Explanation:
Starting at (0,0), the robot can visit 6 cells before being blocked by walls. Show More

Undirected Coloured Graph Shortest Path

You are given an undirected weighted graph G(V, E) where each vertex is assigned a colour. Vertices form pairs of the same colour. Thus, total pairs = V/2 (if V is even) or (V/2)+1 (if V is odd). Each pair is assigned a unique colour.

A query Q specifies a colour, and your task is to find the shortest path (in terms of weight) between the two vertice s sharing this colour.

Input Format:
- The first line contains two integers V and E separated by a space (number of vertices and edges).
- The next E lines each contain three integers u, v, and w: an edge between vertex u and vertex v with weight w.
- The next V/2 (or V/2+1 if V is odd) lines specify the vertex pairs for each colour (each line has two vertex indices). If V is odd, the last line contains a single vertex with no pair.
- The final line contains a single integer Q, representing the colour number to query.

Output Format:
- Print the shortest path (by weight) between the vertex pair corresponding to colour Q.
- Each vertex in the path should be printed in order, separated by a single space.

Constraints:
- 2 ≤ V ≤ 100
- 1 ≤ E ≤ 100

Sample Input 1:
7 8
0 6 10
0 2 11
2 4 9
6 4 2
5 2 7
5 1 8
1 4 4
3 4 3
0 1
2 3
5 6
4
3

Sample Output 1:
5 1 4 6

Explanation:
There are 7 vertices and 8 edges.
Colour 1 → nodes 0, 1
Colour 2 → nodes 2, 3
Colour 3 → nodes 5, 6
Colour 4 → node 4 (no pair)

Query = 3 → Find shortest path between 5 and 6.
Shortest weighted path: 5 → 1 → 4 → 6 Show More

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