DSA PROBLEMS

PROBLEM LEVEL -> EASY

1.Problem name
Rotate Array Equals

Problem statement

Two arrays of integers are “Equal” if rotating one of them with some number of steps makes it
identical to the other array. A single rotation of an array shifts each element at index at i to i+1, except
for the last element, which is moved to the first position.

For example, if arr = [2, 4, 2, 5] becomes [5, 2, 4, 2] after one rotation.

Given two arrays arr1 and arr2, print “true” if they are “Equal”, and “false” otherwise.

Input format:

The first line has an integer n, the size of both arrays arr1 and arr2.

The second line has n integers of arr1 separated by spaces.

The second line has n integers of arr2 separated by spaces.

Output format:

true, if arr1 Equals arr2.

false, otherwise

2. MODE OF AN ARRAY

You are given an array of \(N\) numbers \(A_1, A_2,\ldots, A_N\). In one operation, you can pick any
index \(i\) and change \(A_i \) to \(x (1 \leq x \leq 10^9)\). Given an integer \(K\), find the minimum
number of operations required to make \(K\) the mode of the array.

Note: A number is called the mode of the array if it is more frequent than any other number in the
array.

Example: The mode of array \([1, 1, 3]\) is \(1\). The array \([1, 1, 3, 3]\) does not have any mode.

Input format

 The first line contains the number of test cases \(T (1 \leq T \leq 1000)\).
 The first line of each test case contains two integers, \(N\) and \(K (1 \leq K \leq
10^9)\) where N denotes the number of elements in the array.
 The second line contains \(N\) integers \(A_1,A_2, \ldots, A_N (1 \leq A_i \leq
10^9)\) denoting the contents of the array.
 DSA PROBLEMS
Note: Sum of \(N\) over all test cases does not exceed \(2 \times 10^5\).

Output format

For each test case output a line containing the minimum number of operations required to make \(K\)
the mode of array \(A\).

3.Likeable arrays
Problem statement
Bob and Alice are two friends, they have an array A consisting of N integers, A1,A2,A3 ..., AN. Alice
likes the arrays in which if element X is present it must have exactly X or zero occurrences. So, Bob
has decided to convert this array to an array which Alice likes. To do that, he can perform the
following two operations:

 Add an element of any value to array A.

 Remove an element from array A.

Find the minimum number of operations Bob has to perform so that array is liked by Alice.

Input format

 The first line contains an integer T denoting the number of test cases.
 The first line of each test case contains an integer N denoting the number of elements in
array A.
 The second line of each test case contains N space-separated integers of array A.

Output format

Print T lines. For each test case:

 Print a single line indicating the minimum number of operations to be performed.

4. Double inversions

Problem statement
Consider a certain permutation of integers from 1 to n as A={a1,a2,...,an} and reverse of array A as R,
that is, R={an,an−1,...,a1}. You are given the inversions at each position of array A and R as
{IA1,IA2,…..,IAn} and {IR1,IR2,…..,IRn} respectively.
Find the original array A. If, there are multiple solutions, print any of them. If there is no solution,
then print -1.
Note: The inversion of array arr for position i is defined as the count of positions j satisfying the
following condition arrj>arri and 1≤j<i.

Input format

 The first line contains T denoting the number of test cases.

 For each test case:
o The first line contains n denoting the number of elements.
o The second line contains the elements {IA1,IA2,…..,IAn}.
o The third line contains the elements {IR1,IR2,…..,IRn}.

Output format
 DSA PROBLEMS
For each test case, print the array A in the space-separated format or -1 if no solution exists. Each test
case should be answered in a new line.

5, Bob's empire

Problem statement
Bob built an empire with five cities (C1,C2,C3,C4,C5). The only mode of transport in this empire is
the train.

1. One can travel from C1to C2 in one minute. This train can occupy at most A people.
2. One can travel from C2to C3 in one minute. This train can occupy at most B people.
3. One can travel from C3to C4 in one minute. This train can occupy at most C people.
4. One can travel from C4to C5 in one minute. This train can occupy at most D people.

For each of them, a train leaves the city at each integer time (0,1,2,...).
There is a group of N people at C1, and they all want to go to C5.

At least how long does it take for all of them to reach there? You can ignore the time needed to
transfer.

Input format

 The first line contains an integer T denoting the number of test cases.
 The first line of each test case contains a single integer N.
 The second line of each test case contains four space-separated integers A,B,C,
and D respectively.

Output format

For each test case, print the minimum time required for all of the people to reach C5 (in minutes) in a
new line.

6. Mode of an array

Problem statement
You are given an array of N numbers A1,A2,…,AN. In one operation, you can pick any index i and
change Ai to x(1≤x≤109). Given an integer K, find the minimum number of operations required to
make K the mode of the array.

Note: A number is called the mode of the array if it is more frequent than any other number in the
array.

Example: The mode of array [1,1,3] is 1. The array [1,1,3,3] does not have any mode.

Input format

 The first line contains the number of test cases T(1≤T≤1000).

 The first line of each test case contains two integers, N and K(1≤K≤109) where N denotes the
number of elements in the array.
 The second line contains N integers A1,A2,…,AN(1≤Ai≤109) denoting the contents of the
array.

Note: Sum of N over all test cases does not exceed 2×105.
 DSA PROBLEMS
Output format

For each test case output a line containing the minimum number of operations required to make K the
mode of array A.

7. Lexicographic Smallest Array

Problem statement
Given an array A consisting of integers, find the lexicographically smallest array possible, if we can
swap the elements of the array with a distance greater than or equal to K.Note: We can swap array ai
and aj, if |i−j|>K−1.
Input:The first line contains two positive integers N and K.The next line contains an array consisting
of N integers.

Output:The output should be the lexicographic smallest array possible after applying the operations.

8. Sort String

Problem statement
You are given a binary string S of length N. You can apply the following operation to the string S :

 Choose two distinct indices i,j(1≤i,j≤N,i≠j) and flip the characters Si,Sj.

Find the minimum number of operations required to sort the given string S. It is always possible to
sort any string under the given constraints.

Input format

 The first line contains T denoting the number of test cases. The description of T test cases is
as follows:
 For each test case:
o The first line contains N denoting the length of string S.
o The second line contains the binary string S.

Output format

For each test case, print the minimum number of operations required to sort the given string S.

9. Swaps

Problem statement
You are given an array A of size N. You can apply the following operation any number of times
(possibly zero) on A.

 Choose any two distinct indices X (0<=X<N) and Y (0<=Y<N) such that Bitwise Xor
of A[X] and A[Y] is odd and swap A[X] and A[Y].

Find the lexicographically smallest array that can be obtained after performing the operation any
number of times (possibly zero) on A.
An array P is lexicographically smaller than its permutation Q if and only if, for the earliest index at
which P and Q differ, the element of P at that index is smaller than the element of Q at that index.
Example, P = [1, 12, 4, 7, 8] is lexicographically smaller than Q = [1, 12, 8, 4, 7].

Input Format:
 DSA PROBLEMS
The first line contains an integer T, which denotes the number of test cases.
The first line of each test case contains an integer N, denoting the number of elements in the array A.
The second line of each test case contains N space-separated integers, denoting the elements of the
array A.

Output Format:

For each test case, print the lexicographically smallest array.

10. Product Game

Problem statement
Bob Plays an exciting game known as "Product Game" In the Game, Bob has been provided an array
of numbers of size N along with Qqueries. For each query, he is provided with integers L and R and
he has to find the product of all elements in the array between this range inclusively. Bob's task is to
find the difference between the maximum and minimum solutions among all the queries.

Note:

 Since the value of product can be large, print the answer modulo 1000000007.
 Compute the answer to each query as PQ−1 modulo 1000000007, where Q−1 denotes the
multiplicative inverse of Q modulo 1000000007
 Compute overall answer modulo 1000000007.

Task:

Find the difference between the maximum and minimum solutions among all the queries.

Function Description:

Complete the function solve provided in the editor. This function takes the following two parameters
and returns the required answer:

T: Test Cases
N:Size of Array
A: Array of Numbers
Q: Number of queries
queries: 2-D Array of queries containing [L,R]
L:LowerIndex
R:UpperIndex

Input Format:

The first line contains an Integer T which is the number of the test cases.

Each Test Case will have the following :

The first line contain an integer N

the second line contains the array A
The third line contain an Integer Q
Next, Q lines contain two integers L and R in each lin

Output Format:

For each test case, print answer in a new line

 DSA PROBLEMS
11. Smallest number

Problem statement
You are given a string S that represents a number. This string consists of the following
characters only:

 1
 2
 3

You can perform the following operation:

 Swap any two adjacent characters only if the absolute difference between the characters is 1

Your task is to determine the smallest number that can be formed by using the provided operation.
You can perform this operation any number of times (possibly zero).

Note: Assume 1 based indexing.

Input format

 The first line contains an integer T that denotes the number of test cases.
 For each test case:
o The first line contains an integer that denotes the length of string S.
o The second line contains a string that denotes the string S.

Output format

For each test case, print a string representing the smallest number that can be formed in a new line.

12. Dropping bars

Problem statement
You are given a grid of size N×M where the top left square has coordinate (1,1) and bottom right
square has coordinate (N,M).You are given a coordinate (X,Y) and you have rectangular bars of size
L×B. You are dropping these bars randomly at any place on the grid (the bar should be inside the
boundaries of the grid) one after the other, until one falls on (X,Y).Calculate the expected number of
bars required to do so.

Input format First line: T (number of test cases)For each test case: Six space-separated integers N, M,
L, B, X, and Y

Output formatPrint the expected number of bars correctly up to exactly 6 places after decimal.

13. Multiple conditions

Problem statement
You are given an array A of integers of size N.
A triplet (i, j, k) is said to be amazing if these two conditions hold:
1. i<j<k
2. Ai<Aj<Ak
The value of an amazing triplet (i, j, k)=Ai+(Aj×Ak).
 DSA PROBLEMS
Find the maximum value among all possible values of amazing triplets.

If there are no amazing triplets, then print -1.

Input format

 The first line contains T denoting the number of test cases.

 The first line of each test case contains an integer N denoting the number of elements in the
array.
 The second line of each test case contains N space-separated integers A1, A2, A3, ..., AN.

Output format

For each test case, print the maximum value among all possible values of amazing triplets. If there are
no amazing triplets, then print -1.

14. Min Length Subarray

Problem statement

You are given two integers N, K, and an array arr of size N.

Task

You have to tell the minimum length subarray whose sum is divisible by K. If there is no
such subarray, output -1.

Notes:

 Consider 1-based indexing.

 A subarray is a slice from a contiguous array (i.e., occupy consecutive positions) and
inherently maintains the order of elements. For example, the subarrays of array {1, 2, 3} are
{1}, {1, 2}, {1, 2, 3}, {2}, {2, 3}, and {3}.

Example

Assumption

 N=3
 K=6
 arr = [1, 3, 3]

Approach

Subarray [1]: Sum = 1 Subarray [3]: Sum = 3 Subarray [3]: Sum = 3 Subarray [1, 3]: Sum = 4
Subarray [3, 3]: Sum = 6 (divisible by K) Subarray [1, 3, 3]: Sum = 7

There only exists one subarray with sum divisible by K.

Therefore, the answer is 2.

Function Description
 DSA PROBLEMS
Complete the Solution function provided in the editor. The function takes the following three
parameters and returns the minimum length subarray whose sum is divisible by K. If there is no
such subarray, it returns -1.

 N: Represents the integer N

 K: Represents the integer K
 arr: Represents the array of size N

Input Format

Note: This is the input format that you must use to provide custom input (available above
the Compile and Test button).

 The first line contains an integer T denoting the number of test cases. T also denotes the
number of times you have to run the Solution function on a different set of inputs.
 For each test case:
o The first line of each test case contains two space-separated integers N and K.
o The second line of each test case contains N space-separated integers denoting the
array arr.

Output Format

For each test case, print the minimum length subarray whose sum is divisible by K (If there is no
such subarray, print -1) in a new line.

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.

15. Cells in a matrix

Problem statement
You are given an integer N denoting an N×N matrix. Initially, each cell of the matrix is empty. You
are given K tasks. In each task, you are given a cell (i,j) where cell (i,j) represents the ith row and jth
column of the given matrix.
You have to perform each task sequentially in the given order. Each task is described in cell (i,j). For
each task, you have to place X in each cell of row i and each cell column j. After you complete each
task, you are required to print the number of empty cells in the matrix.

Input format

 The first line contains two space-separated integers N and K where N is the number of rows
and columns in the given matrix and K is the number of tasks respectively.
 Next K lines contain two space-separated integers i and j.

Output format

Print K space-separated integers denoting the number of empty cells in the matrix.

16. Find the minimum value

Problem statement

You are given the following:

 DSA PROBLEMS
 N: An integer
 A: An array of integers of length N
 B: An array of integers of length N

You can perform the following operation any number of times. Pick any two elements of array B and
swap them.

Task

You are required to find the minimum value of |A1-B1| + |A2-B2| + ... + |AN-BN|.

Notes

 |a-b| represents the absolute difference between a and b.

 Ai and Bi represent the i-th element of arrays A and B respectively.
 0 based indexing is followed.

Example

Assumption

 N=2
 A = [1, 4]
 B = [4, 2]

Approach

 Swapping B[0] and B[1].

 Now array B becomes B = [2, 4].
 Calculating the answer, |1-2| + |4-4| equals 1.

Therefore, the answer is 1.

Function description

Complete the solve function provided in the editor. This function takes the following 3 parameters and
returns the answer.

 N: Represents the size of the arrays.

 A: Represents the first input array.
 B: Represents the second input array.

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile
and Test button).

 The first line contains a single integer T that denotes the number of test cases. T also denotes
the number of times you have to run the solve function on a different set of inputs.
 For each test case :
o The first line contains an integer denoting N the size of arrays.
o The next line contains N space separated integers denoting array A.
o The next line contains N space separated integers denoting array B.
 DSA PROBLEMS
Output format

For each test case, print an integer denoting the minimum answer in a new line.

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.

17. Alphabet game

Problem statement

You are given the following:

 Given a string S of N lower case alphabets.

Two players A and B play a game turn by turn in which one player can have either of the following
moves in his turn:

1. Remove a consonant from the string.

2. If it is a vowel, then you may convert it to any other alphabet.

The player unable to make a move loses the game.

Task

Predict the winner of the game if both play optimally and A to start's the game. The game may end in
a draw if the game may go on forever.

Note

 'a', 'e', 'i', 'o' ,'u' are vowels and others are consonants in lowercase alphabets.

Example

Assumptions

 N=2
 String S = "bc"

Approach

In 1st turn A will remove a consonant either 'b' or 'c'. In the 2nd turn, B will remove the
remaining consonant left. In 3rd turn, nothing is left so A loses the game.

Function description

Complete the solve function provided in the editor. This function takes the following 2 parameters and
returns the winner of the game if both play optimally:

 N: Represents the length of string S

 S: Represents the string S of length N

Input:
 DSA PROBLEMS
Note: This is the input format that you must use to provide custom input (available above the Compile
and Test button).

 The first line contains an integer T denoting the number of test cases. T also denotes the
number of times you have to run the solve function on a different set of inputs.
 For each test case:
o The first line consists of a single integer denoting the value of N.
o The second line consists of the string S.

Output

For each test case, print a single character A or B denoting the winner of the game. If there is a draw
print D in a new line.

Note: String consists of only lower case alphabets.

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.

18. Minimize to its end

Problem statement

We're given an array of n integers. We can choose any subarray and perform the following operation:

Reduce an element a[i] by 1 which will cost us 1.

We can perform this operation any number of times.

We have to find the longest subarray we can make elements equal to and also the cost of the subarray
should be less than or equal to k.

Input Format:

 First-line contains T, the number of test cases.

o Each test case contains two space-separated integer n and k.
o The next line of each test case contains n space-separated integers.

Output Format:

For each test case, in a single line, print an integer of maximum length of subarray whose elements
can be made equal in the given cost.

19. Pair Count

Problem statement
Given an array A of N positive integers. For each array element A[i] (1≤i≤N), find the number of
A[j] (i<j) such that gcd(A[i],A[j])=G.
Input format The first line consists of a single integer denoting T - the number of test cases. For each
test case: The first line consists of two single space-separated integers denoting the value of N, G.
The second line consists of N single space-separated positive integers denoting the array A.
 DSA PROBLEMS
Output format Print N single space-separated integers where the ith integer denotes the number of
elements A[j](i<j), such that gcd(A[i],A[j])=G

20. String Concatenation

Problem statement

For a string S and an array of characters P of size N. A string S' is generated by removing all
characters from S that is in the given array P without changing the order of characters.

A string T is generated by concatenating S with S'. (T = S + S')

Task

You are given a string T and a set of characters P. You have to find the string S for which T can be
generated. If no such string is possible, print -1.

Note:

1. String Concatenation is the operation of joining character strings end-to-end. For example, the
concatenation of "Hacker" and "Earth" is "HackerEarth".

Example

Assumption

 T = "abcdab"
 N=2
 P = {c, d}

Approach

If you consider S = "abcd".

You will remove all the characters from the array P = {c, d} from S to generate S'.

S' = "ab"

T = S + S' T = "abcd" + "ab" T = "abcdab"

Therefore, the answer is "abcd".

Function description

Complete the solve function provided in the editor. This function takes the following three parameters
and returns the answer.

 T: Represents a string.
 N: Represents an integer denoting the size of array P.
 P: Represents an array of characters of size N.

Input format
 DSA PROBLEMS
Note: This is the input format that you must use to provide custom input (available above the Compile
and Test button).

 The first line contains a string T.

 The second line contains an integer N denoting the size of array P.
 The third line contains N space-separated characters representing the array P.

Output format

If a string S exists, print S. else print -1.

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.

21. XOR Subsequences

Problem statement

You are given the following:

 N: An integer
 K: An integer
 A: An array of non-negative integers

Task

You need to determine the maximum length of subsequence such that the bitwise xor of every
consecutive element is equal to K.

If there exists no such subsequence of length greater than or equal to 2, you should output 0.

Note:

 A subsequence is a sequence that can be derived from the given sequence by deleting zero or
more elements without changing the order of the remaining elements.

Example

Assumption

 N=3
 K=1
 A = [1, 0, 1]

Approach

The maximum length subsequence having xor of consecutive elements as 1 is [1, 0, 1].

Therefore, the maximum length of the subsequence is 3.

Function description

Complete the solve function provided in the editor. This function takes the following 2 parameters and
returns the answer.
 DSA PROBLEMS
 N: Represents the size of array A.
 K: Represents the given integer.
 A: Represents the array of a given integers

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile
and Test button).

 The first line contains a single integer T that denotes the number of test cases. T also denotes
the number of times you have to run the solve function on a different set of inputs.
 For each test cases:
o The first line contains 2 space-separated integers N and K denoting the length of array
A and the required value of bitwise xor of every consecutive element in the
subsequence respectively.
o The next line contains N space-separated integers denoting the input array A.

Output format

For each test case, print the maximum length of the subsequence of A in a new line.

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.

22. Gully Cricket

Problem statement

You are given an integer N and a two-dimensional String array info of size N. Each row of 2D
array info is of size 2. info array represents the scoreboard of a Gully Cricket Match. The first element
contains the bowler's name who bowled and the second element represents the event (runs, wicket, or
wide) that took place on that ball.

The rules of Gully Cricket are:

1. There is no such thing as a "No Ball". Only a Wicket (W), runs (0,1,2,3,4,6), or a Wide (WD)
can take place in one ball.
2. There are only 5 players playing, so total number of distinct bowlers cannot exceed 5.
3. Each over is of 6 valid balls (note that Wide ball is not valid), and if and only if a bowler
complete 6 valid balls, any other player comes to bowl.
4. The game is infinte. After one player gets out, any other player who does not have to bowl
next ball comes out to bat in sequence.

You have to print "YES" or "NO" depending on whether the information in the info scoreboard is
according to the rules above or not.Note: The match could still be in progress while you were given
this information, so it is possible that the last over can have less than 6 balls.

Example

Assumption

 T=1
 N=2
 info = {{"bob", "1"}, {"bob", "2"}}
 DSA PROBLEMS
Approach

Rule 1:Runs "1" and "2" are scored on the balls.

Rule 2:There is only one bowler.

Rule 3:The first over is not yet complete.

The scoreboard follows all the rules.

Hence, the answer is "YES".

Function description

Complete the solve function provided in the editor. This function takes the following two parameters
and returns the answer.

 N: Represents an integer denoting the size of array info.

 info: Represents a 2D array of integers with N rows and 2 columns.

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile
and Test button).

 The first line contains a single integer T which denotes the number of test cases. T also
specifies the number of times you have to run the solve function on a different set of inputs.
 The first line contains an integer N denoting the size of array info.
 The next N lines contain two space-separated strings denoting the array info.

Output format

For each test case, print the answer ("YES" or "NO" in a new line)

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.

23. Speakers and pointers

Problem statement

You are given a new speaker. The speaker contains three circular knobs and they are used to adjust
the following:

 Volume
 Bass
 Treble

Initially, the pointers on the knobs are in random angles and they are measured from the
positive x axis. You want to rotate these knobs in any direction in such a way that all three pointers
are in the same direction. In other words, the pointers of the knobs must make the same angle from the
positive x axis.

Note: The knobs can be rotated either in the clockwise or anticlockwise direction.
 DSA PROBLEMS
Your task is to determine the minimum sum of the degrees that the pointers must be rotated such that
all the pointers are pointing in the same direction.

Input format

 The first line contains an integer T denoting the number of test cases.
 The next line contains three space-separated integral angles measured in degrees.

Output format

For each test case, print the minimum sum of the degrees that the pointers must be rotated such that
all the pointers are pointing in the same direction. Note: The answer to each test case must be in a
new line.

24. James and the menus

Problem statement
James visits a restaurant, looks at the menu, and realizes that there is no price on it. Since he wanted
to know the prices before he orders, he looked up the restaurant online and found n different versions
of the menu. He knew from experience that usually the menu which has the maximum number of
items that have the maximum price on that item between the menus is the most updated one and if
there are multiple menus with that condition the one with the maximum average price is the most
updated one. Help him find the most updated menu.

In other words, a price on an item is good if it is the maximum price on that item among all menus,
and a menu is the most updated one if it has the maximum number of good prices on it. If there are
multiple menus with the maximum number of good prices, the menu with the higher price average is
the most updated one.

Input format

 The first line contains integers n and m that denote the number of menus and the number of
items on each menu respectively.
 The next n line each contains m integers represented as Aij, the jth price on the ith menu.

Output format

Print a single number denoting the number of the most updated menu.

It is guaranteed that the answer is unique.

25. XOR split

Problem statement
You are given a number N. Your task is to find if there exist two distinct natural numbers such that
their bitwise XOR is N and bitwise AND is 0. If such numbers exist, then print 1. Otherwise, print 0.

Input format

 The first line contains T denoting the number of test cases.

 The first line of each test case contains an integer N.

Output format
 DSA PROBLEMS
For each test case, print the answer.

26. Candy in the box

Problem statement

You have N boxes numbered 1 through N and K candies numbered 1 through K. You put the candies
in the boxes in the following order:

 first candy in the first box,

 second candy in the second box,
 .......
 ........
 so up to N-th candy in the Nth box,
 the next candy in (N - 1)-th box,
 the next candy in (N - 2)-th box
 ........
 .......
 and so on up to the first box,
 then the next candy in the second box
 ...... and so on until there is no candy left.

So you put the candies in the boxes in the following

order: 1,2,3,....,N,N−1,N−2,....,2,1,2,3,....,N,N−1,....

Find the index of the box where you put the K-th candy.

Input format

 The first line contains T denoting the number of test cases. The description of T test cases is
as follows:
 Each test case consists of a single line containing two integers N, and K.

Output format

For each test case, print the index of the box where you put the K-th candy.

Constraints

1≤T≤1052≤N≤1091≤K≤109

27. Equal Parity

Problem statement
You are given an array A containing 2⋅N inetegers. You want to obtain exactly N even integers in the
array. Is it possible to achieve the goal using the following operation any number of times(possibly
zero) ?

 Choose two distinct indices i,j(1≤i,j≤N,i≠j) such that Ai is an even integer, then
set Ai=Ai2,Aj=Aj⋅2

Input format

 The first line contains T denoting the number of test cases. The description of T test cases is
as follows:
 DSA PROBLEMS
 For each test case:
o The first line contains an integer N where 2⋅N denotes size of array A.
o The second line contains 2⋅N space-separated integers A1,A2,…,A2⋅N - denoting the
elements of A.

Output format

For each test case, print "YES" (without quotes) if it is possible to achieve the goal and "NO" (without
quotes) otherwise.

28. MAX AND

Problem statement
You are given array A, B each containing N inetegers. You have to create array C of N inetegers
where Ci=Ai&Bi (Here, & denotes the Bitwise AND operation). You can shuffle elements
of A, B however you want. Find maximum value of C1&C2&…&CN.

Input format

 The first line contains T denoting the number of test cases. The description of T test cases is
as follows:
 For each test case:
o The first line contains an integer N denotes size of array A, B.
o The next line contains N space-separated integers A1,A2,…,AN - denoting the
elements of A.
o The next line contains N space-separated integers B1,B2,…,BN - denoting the
elements of B.

Output format

For each test case, print maximum value of C1&C2&…&CN in a separate line.

29. Maximum string score

Problem statement
You are given a list S that contains strings. Note: Each string in the list consists of only lowercase
Latin letters.
The score of any string P is represented as follows:

 The sum of the number of strings in S in which P occurs as a substring and the number of
strings in S in which P occurs as a prefix.

Example

If S = ['abc', 'abab', 'aba'] and P = 'ab', then score of P = 3. This is because (P occurs in all the strings)
+ 3 (P occurs in 'abc', 'abab', and 'aba' as a prefix) = 6.
Note: If P occurs as a prefix in any of the strings, then it will also contribute to the substring.

Your task is to determine the maximum score possible of any string provided.

Input format

 The first line contains T denoting the number of test cases.

 For each test case:
 DSA PROBLEMS
o The first line contains N denoting the number of strings in the list.
o The next N lines contain the elements of the list.

Output format

For each test case, print the maximum score possible in a new line.

30. Alice and the Bags

Problem statement
You are given an array A of n integers. Alice has to put all the integers in some bags. The bags can
accommodate infinitely many integers. An integer Ai will go in the bag number x, where x is
the largest prime factor of Ai. After storing all the integers in the respective bags, the bags
automatically add up all the integers stored in it. You have to tell how many bags Alice has to use and
the number of the bag which has the highest valued integer stored in it. If more than one bags has the
same integer stored, print the bag with the minimum number.

Input Format

 First line: An integer T denoting the number of test cases.

 For each test case:
o First line: An integer n denoting the number of elements in array A.
o Next line: n space-separated integers denoting the elements of array A

Output Format

For each test case, print two space-separated integers, the total number of bags Alice has to use and
the number of the bag which has the highest valued integer stored in it.

31. A cricket tournament

Problem statement
In a cricket tournament, n matches are supposed to be played between Bob and James.
You are given two arrays A and B. Array A represents the energy levels of Bob and array B
represents the energy levels of James. The size of both the arrays is the same as n.
Now, n matches will be played between Bob and James, and for the ith match the energy level at ith
index is compared of both. The winner of the ith match will be the one whose energy level at that
index is higher.
If Bob wins in the ith match, then the energy level difference (between the ith level of both) will be
added to his score else his score remains the same i.e., on losing, Bob's points will not decrease.

Bob wants to maximize his score by changing his energy levels, that is, Bob can make a permutation
of his array.

Help Bob in knowing the maximum score he can get.

Input format

 The first line of each test case contains an integer n denoting the number of matches.
 Each of the next two lines contains n integers representing energy levels.

Output format

Print a single integer denoting the number of pentagons possible.

 DSA PROBLEMS

32. Empty arrays

Problem statement
You are given two arrays each of size n, a and b consisting of the first n positive integers each exactly
once, that is, they are permutations.

Your task is to find the minimum time required to make both the arrays empty. The following two
types of operations can be performed any number of times each taking 1 second:

 In the first operation, you are allowed to rotate the first array clockwise.
 In the second operation, when the first element of both the arrays is the same, they are
removed from both the arrays and the process continues.

Input format

 The first line contains an integer n, denoting the size of the array.
 The second line contains the elements of array a.
 The third line contains the elements of array b.

Output format

Print the total time taken required to empty both the array.

33. A good array

Problem statement
You are given an array A which consists of N elements. Each element of array is either zero or one.
Your task is to convert the given array into a good array with a minimum cost.
Good array: In a good array, select any subarray of even length M and the sum of elements in the
subarray will be M/2.

In order to transform an array to good array, you can perform the following two operations as many
times as you want:

1. Choose any index 1≤i≤N and if it is currently 0, then convert it to 1 for X coins.
2. Choose any index 1≤i≤N and if it is currently 1, then convert it to 0 for Y coins.

Your task is to minimize the cost of transformation of an array to good array.

Input format

 The first line contains T denoting the number of test cases.

 The first line of each test case contains three space-separated integers N, X, and Y.
 The second line of each test case consists of N space-separated integers of array A.

Output format

For each test case, print one line denoting the minimum cost to transform array A into a good array.

34. Update the array

Problem statement
 DSA PROBLEMS
Given an array A of N integers and an integer K. You can perform the following operation any number
of times on the given array :

 Choose an integer x such that 1≤x≤K

 Choose any index i such that 1≤i≤N
 Update A[i] = x

In different operations, different value of x and i can be chosen.

Task

Your task is to count minimum number of operations required such that following conditions are met:

 All elements in array A becomes pairwise distinct.

 Count of array elements with odd value is equal to count of array elements with even value.

If the above conditions cannot be met after any number of operations, return -1.

Note:

 Assume 1 Based Indexing is followed.

 Array A is said to have pairwise distinct elements if and only if the value of all the elements in
array A is distinct.

Example

Assumptions:

 N=4
 A = [1, 4, 4, 1]
 K=5

Approach:

 Initial array A is [1, 4, 4, 1]

 Update A[2] = 2, choose x = 2, i = 2.
 Update A[4] = 5, choose x = 5, i = 4.
 Updated array A is [1, 2, 4, 5]
 Now, array A have all distinct elements and count of array elements with odd value is equal to
count of array elements with even value.
 Therefore, minimum 2 operations are required.

Note, there can be other possible selections of x and i, at each step but the minimum number of
operations remains the same.

Function description

Complete the minUpdates function provided in the editor. This function takes the following
3 parameters and returns an integer.

 N: Represents the number of elements in array A

 A: Represents the elements of array A.
 K: Represents the value of K
 DSA PROBLEMS
Input Format

Note: This is the input format that you must use to provide custom input (available above the Compile
and Test button).

 The first line contains a single integer T, which denotes the number of test cases. T also
specifies the number of times you have to run the minUpdates function on a different set of
inputs.
 For each test case:-
o First line contains an integer N.
o Next line contains N space-separated integers denoting the elements of array A.
o Next line contains an integer K.

Output Format

For each test case in a new line, print an integer denoting the minimum number of operations required
or print -1, if the conditions cannot be met.

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.

35. Cannibal Characters

Problem statement

You are given an integer n and a string s of size n composed of lower case english letters.

You can perform the following operation on it:

 In one operation, you have to choose any character in the string s, then delete the first
character to the left of the chosen character that is equal to the chosen character (if there
exists) and delete the first character to the right of the chosen character that is equal to the
chosen character (if there exists).
 Note that in one operation, the length of the string s is reduced by a maximum of two
characters.

Task

You want to minimize the length of the string s.

Find the minimum number of operations that need to be performed to minimize the length of the
string s.

Note:

 Assume 1 based indexing.

Example

Assumptions :

 n=4
 s = "abaa" (without quotes)
 DSA PROBLEMS
Approach:

 Choose 3rd character in the string for 1st operation, this will delete the 1st character
and 4th character in string s, the string becomes "ba".
 The length of the string s can not be reduced further.
 Hence, minimum number of operations needed to reduce the length of the string s to a
minimum is 1.

Function Description

Complete the Minimum_Operations function provided in the editor. This function takes the following
2 parameters and returns the required answer:

 n: Represents the length of string s.

 s: Represents the string s.

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile
and Test button).

 The first line contains a single integer T, which denotes the number of test cases. T also
specifies the number of times you have to run the Minimum_Operations function on a
different set of inputs.
 For each test case:
o First line contains an integer n.
o Second line contains a string s.

Output format

For each test case in a new line, print the minimum number of operations required to minimize the
length of string s.

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.

36. String Challenge

Problem statement

Given a string S consisting of lower case English alphabets and an integer K.

You need to form a new string P that follows the following conditions:

 Length of P should be equal to K + length of string S.

 P should only be formed by using the prefixes of string S.
 P should be lexicographically smallest.

Task

Determine the string P that satisfies all the given conditions.

Example
 DSA PROBLEMS
Assumptions

 N=3
 K=4
 S = bca

Approach

 Prefixes of S are "b", "bc", "bca".

 String P will be "bbbbbbb" of length 7 (N + K i.e. 3 + 4).

Function Description

Complete the solve function provided in the editor. This function takes the following 3 parameters and
returns the valid string:

 N: Represents the size of string S.

 K: Represents the given integer.
 S: Represents the given string.

Input Format

Note: This is the input format you must use to provide custom input (available above the Compile and
Test button).

 The first line contains a single integer T denoting the number of test cases.
 For each test case:
o The first line contains a single integer N denoting the size of string S.
o The second line contains a single integer K denoting the number of new characters
added in string S.
o The third line contains the string S.

Output Format

For each test case in a separate line, output a string P that satisfies all the given conditions.

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.

37. K-Good Trees

Problem statement

Problem:

A tree is called K−Good(K≥1) if all the nodes of the tree have exactly K children except the leaves.
For given count of leaves M(M≥2), find the number of possible values of K.

Input Format:

 The first line of the input contains a single integer T - the number of test cases. The
description of T test cases follows.
 The first and only line of each test case contains a single integer M.
 DSA PROBLEMS
Output Format:

 For each test case, print the number of possible values of K for given count of leaves M.

38. Alternative moves

Problem statement

You are given three integers N, A, and B. You have another integer X = 0. You can apply the
following move (1-indexed) any number of times:

 During the odd-numbered moves(1, 3, 5,....), you have to set X = X + A.

 During the even-numbered moves(2, 4, 6,....), you have to set X = X - B.

Find the minimum number of moves required so that the value of X becomes greater than or equal to
N or print -1 if it is impossible to do so.

Input format

 The first line contains T denoting the number of test cases. The description of T test cases is
as follows:
 Each test case consists of a single line containing three integers N, A, and B.

Output format For each test case, print the minimum number of moves required so that the value of X
becomes greater than or equal to N or print -1 otherwise.

39. Max difference

Problem statement

The weight of an array is defined as the difference between the maximum and minimum element of
the array. For example, the weight of the array [3, 7, 1, 2] is (7 - 1) = 6, the weight of the array [2] is
(2 - 2) = 0, the weight of an empty array is 0. You are given an array A of length N. You have to
divide the elements of A into two subsequences S1, and S2 (one of S1, S2 can be empty) such that:

 Each element of A belongs to one of S1 and S2.

 The sum of weights of the two subsequences is maximum.

Find the maximum possible sum of weights of the two subsequences.

Input format

 The first line contains T denoting the number of test cases. The description of T test cases is
as follows:
 For each test case:
o The first line contains N denoting the size of array A.
o The second line contains N space-separated integers A[1], A[2], ....., A[N] - denoting
the elements of A.

Output format For each test case, print the maximum possible sum of weights of the two
subsequences.
 DSA PROBLEMS
40. Maximum Inequality

Problem statement

A function on a binary string T of length M is defined as follows:

F(T) = number of indices i (1≤i<M) such that Ti≠Ti+1.

You are given a binary string S of length N. You have to divide string S into two subsequences S1,S2
such that:

 Each character of string S belongs to one of S1 and S2.

 The characters of S1and S2.must occur in the order they appear in S.

Find the maximum possible value of F(S1)+F(S2).

NOTE: A binary string is a string that consists of characters `0` and `1`. One of the strings S1, S2 can
be empty.

Input format

 The first line contains T denoting the number of test cases. The description of T test cases is
as follows:
 For each test case:
o The first line contains N denoting the size of string S.
o The second line contains the string S.

Output formatFor each test case, print the maximum possible value of F(S1)+F(S2) in a separate line.
.

41. Costliest Data Plan

Problem statement
Pawan has a finite number of friends, each friend has a unique non-negative number associated with
him. (0, 1, 2..) Pawan plans to host a party and has to send notifications to his friends. A friend attends
the party if he receives at least 1 notification from Pawan. To send notifications, Pawan buys data
plans Pawan can send notifications using data plan X in the following way: Let's say Data plan X
costs Y. Then a friend associated with the number i will receive a notification if and only if the ith bit
in Y is set. Now Pawan wonders if he can cut costs. Let him know the maximum cost that he can cut
by removing at most 1 data plan and still being able to invite all the friends he could invite earlier

Input

Each test contains multiple test cases. The first line contains a single integer t (1≤t≤100) — the
number of test cases. Description of the test cases follows.

The first line of each test case contains one integer N - the number of data plans
The second line of each test case contains N integers a1,a2,…,an — the cost of data plans array.
It is guaranteed that the sum of N over all test cases does not exceed 105

Output

For each test case, print a line containing a single integer – the maximum possible money that Pawan
can save (print 0 if no data plan can be removed)
 DSA PROBLEMS

DIFFICULTY LEVEL -> MEDIUM

42. The largest number of vaccines

Problem statement

A disease has spread in your country that does not have any vaccines. The Health Department of your
country is working to create its vaccine. The limitation to create vaccines is the cost that is required to
create an effective vaccine.

The scientists of the department have created 9 samples that are numbered from 1 to 9. Each vaccine
is associated with a cost. The cost is denoted by an array X where Xi denotes the cost of the ith
sample. The Health Department has been assigned N units of money to spend. This amount of money
must be used to create stocks of vaccines that can be distributed among different hospitals that are
situated at different locations in your country.
You are required to find the largest number of stocks possible that can be formed by using the N units
of money. If it is not possible to form such a stock of vaccines, then print −1.

Example

If N = 10, (X1, X2, ... , X9) = [9,8,7,6,8,4,3,20,10] .

 Largest number of stocks that can be formed is 777. Altough, 9, 776 can also be formed
but 777 is largest.

Function Description

Complete the Largest_Number function provided in the editor. The function takes the following 2
parameters and returns the largest number of stocks.

 N : Represents the amount of money

 cost : Represents the cost of vaccines

Input format

 First line: T denoting the number of test cases

 For each test case:
o First line: N denoting the amount of money
o Second line: Nine space-separated integers X1,X2,X3, …,X9, denoting the cost of
each vaccine

Output format

Print the largest number of stocks that can be formed by using the N units of money. If it is not
possible to form such a stock, then print −1. For each test case, print the answer in a new line.

43. Special string

Problem statement
You are given an integer K and a string S that contains lowercase English alphabets of length N,
where N is always a multiple of K. You are required to convert the given string to a special string.
 DSA PROBLEMS
A special string is a string that follows a repeating pattern of K characters till the total length of
the string is N. For example, if S=abcdef and K=2, then the special string can be ababab or bcbcbc or
any other string which follows the given criteria.
In order to convert the string, you can perform an operation on the string. Considering lowercase
English alphabet set as circular, you can rotate the character of the string on either side in one
operation. For example, for a, you can rotate it to b or z. You can perform this operation any number
of times on any character of the string. Performing this operation once costs you 1 unit.

Your task is to convert the given string to special string in the minimum cost.

Input format

 First line: T denoting the number of test cases

 Next T lines: Two space separated integers K and S where K is an integer and S is a string

Output format

For each test case, print the minimum cost in a new line.

44. One Zero

Problem statement

Count all numbers from the range L to R (inclusive) that have exactly one zero in its binary
representation.

Input Format: The only line of the input contains two integers L and R.

Output Format: Print one integer, the count of such numbers.

45. Sums : Easy Version

Problem statement
You are given an integer array A of length N. For each K=1 to N, find the sum of all subarrays of
array A of length K. Since these sums can be very large, output the sums modulo 998244353.
An array B is a subarray of an array A if B can be obtained from A by deletion of several (possibly,
zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In
particular, an array is a subarray of itself.

Input format:

The first line consists of an integer T denoting number of test cases.

The first line of each test case contains an integer N denoting length of the array.
The second line contains N space separated integers A[1],A[2],...,A[N], denoting elements of the
array.

Output format:

For each test case(in a separate line), output N integers, where ith integer denotes the
sum(modulo 998244353) of all subarrays of array A of length i.

46. Customer and Discount

Problem statement
 DSA PROBLEMS
You are given an array arr of length N, representing money with N customers. The i-th customer has
arri rupees. There is another array cost of length M, representing the cost of M items in a store. The j-
th item costs costj rupees. The store offers some discount money d which any customer can use to buy
an item. Each customer can buy only one item and cannot use his money to buy an item for any other
customer.

Task

Determine the maximum number of customers who can buy an item and the minimum total sum of
customers’ money spent to achieve maximum customers with an item.

Notes

 Assume 1-Based Indexing.

 The discount money d is common for all the customers, i.e., if one customer spends r rupees
from d, then the discount money is reduced to (d-r) for all the customers.
 Multiple customers can spend money from the discount.

Example

Assumptions

 N=3
 M=2
 d = 100
 arr = [30, 40, 50]
 cost = [80, 110]

Approach

Initially, we have discount money equals 100.

 2nd customer buys 1st item worth 80 rupees using 40 rupees of discount money.
 Now the discount money left is 100 - 40 = 60.
 3rd customer buys 2nd item worth 110 rupees using 60 rupees of discount money.
 The total number of customers who can buy an item is 2 with their total sum of money spent
equals 90.

Therefore the answer is [2 90].

Function Description

Complete the function maxCustomers provided in the editor. The function takes the following
parameters and returns an array consisting of 2 integers, the maximum number of customers with
items, and the minimum total customers' money spent:

 N: Represents the size of array arr

 M: Represents the size of array cost
 d: Represents the value of discount money
 arr: Represents the elements of array arr
 cost: Represents the elements of array cost

Input format
 DSA PROBLEMS
Note: This is the input format you must use to provide custom input (available above the Compile and
Test button).

 The first line of the input contains three integers N, M, and d, denoting the number of
customers, the number of items, and the discount money.
 The second line of the input contains N integers arr1, arr2, …, arrN, where arri is the money
with the i-th customer.
 The third line of the input contains M integers cost1, cost2, …, costM, where costj is the price
of the j-th item.

Output format

Print two space-separated numbers, the maximum number of customers who can buy an item and the
minimum total customers' money needed for buying the maximum number of items.

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.

47. Sum Of All

Problem statement

You are given a number. You want to compute the sum of all possible resulting numbers after
applying the magic operation. In a magic operation, you pick a non-empty subsequence from this
number, then take these digits out of the number. The remaining digits then fill in the gap, and the
number after the magic operation is the integer that is left.

For eg: Let's say the number is 12345. One of the subsequences of this number is 24. So after
removing this subsequence, the resulting number is 135. Leading zeros are allowed in the resulting
number (number after applying the magic operation). When all digits are removed, the number is
considered to be 0.

Input Format:

 The first line contains one integer T − the number of test cases. Then T test cases follow.
 The first and only line of each test case contains a single integer N.

Output Format:

For each test case output in a seperate line: The sum of all possible resulting numbers after applying
the magic operation modulo (109+7).

48. Complete Knight Traversals Count

Problem statement

Given two positive integers m and n which are the height and width of a 0-indexed 2D-array board.
Find the number of Knight Traversals. A Knight Traversal includes a knight (of a chess game) starts
at (0,0) of the board and visits every cell of the board exactly once. The starting cell (0,0) is
considered visited and you shouldn't visit it again.
 DSA PROBLEMS
Note that a knight can move from cell (r1, c1) to cell (r2, c2) if 0 <= r2 <= m - 1 and 0 <= c2 <= n - 1
and min(abs(r1 - r2), abs(c1 - c2)) = 1 and max(abs(r1 - r2), abs(c1 - c2)) = 2.

Input constraints:

1 <= m, n <= 5

Input format:

The first line has two integers m and n separated by a space.

Output format:

A number indicating the number of distinct Knight Traversals.

49. Positive Square Grids Count

Problem statement

Find the number of square grids having only positive integers in an m * n grid of integers.

Input constraints:

1 <= m, n <= 300

-100 < grid[i][j] < 100

Input format:

The first line has two integers m and n separated by a space.

Each of the next m lines has n integers separated by spaces.

Output format:

A number indicating the number of square grids having only positive integers.

50. Min Bits

Problem statement

Your college professor has given you a task to pass the semester. The task is as follows:
 DSA PROBLEMS
You are given 2 integers L and R which denotes a range. Find a number in between(L and R
inclusive) which has the minimum number of set bits count. If there are multiple such numbers, print
the minimum number. Note: 14 can be written as 1110 in binary and its set bit count is 3.

Input

First line containing 1 integer T

Next T line containing 2 integers L and R.

Output

A single integer, denoting the number with minimum set bit count.

51. Two gold mines

Problem statement
You have given a n×n matrix containing empty spaces or walls. You have a team of 2 players where
the position of each player is given. There are 2 gold mines on the map. Your aim is to pick gold from
both these mines.

You are required to find the minimum time required to pick gold from both gold mines. In one
second, they all simultaneously can move in any of the four directions and any player can pick any
number of gold including 0.

Input format

 The first line contains t denoting the total number of test cases.
 The first line of each test case contains an integer n denoting the number of rows and columns
in the matrix.
 The next n lines of each test case contain n characters denoting the rows of the matrix.
o . denotes an empty cell
o # # denotes a wall
o ^ ^ denotes a player
o ∗ denotes a gold mine

Output format

The output contains the following two lines:

 The first line contains "Yes" (without quotes) if it is possible to collect both the mines or
"No" (without quotes) if you are unable to pick both the mines.
 The second line contains the minimum time required to pick both the gold mines.

In the case of "No", do not print the second line.

52.Problem statement
Bob sells burgers with three different combinations, B1, B2 and B3. There are total X, Y, and Z
burgers with combinations, B1, B2, and B3 respectively. Each burger has an integer value called
deliciousness as follows:

 The deliciousness of the burgers with the B1 combination are B11,B12,B13,....,B1X.

 The deliciousness of the burgers with the B2 combination are B21,B22,B23,....,B2Y.
 The deliciousness of the burgers with the B3 combination are B31,B32,B33,....,B3Z.
 DSA PROBLEMS
Alice decides to buy K boxes containing three burgers, one from each of the combinations. The
deliciousness of a box is the sum of the deliciousness of the burgers present inside it.
There are X∗Y∗Z such ways to select a box. Print the maximum total sum of deliciousness that Alice
can get by buying K boxes.

Input format

 The first line contains an integer T denoting the number of test cases.
 The first line of each test case contains three space-separated integers X, Y, and Z.
 The second line of each test case contains a single integer K.
 The third line of each test case contains X space-separated integers denoting array B1i.
 The fourth line of each test case contains Y space-separated integers denoting array B2j.
 The fifth line of each test case contains Z space-separated integers denoting array B3k.

Output format

For each test case, print the maximum total sum of deliciousness that Alice can get by buying K
boxes in a new line.

53. A grid

Problem statement
You are given a grid A that consists of N rows and M columns. Each number in the grid is either 0 or
1.
Calculate the number of such triples (i,j,h) where for all the pairs (x,y), both x and y belong to [1,h] if
y>=x and A[i+x−1][j+y−1] equals to 1. Of course, the square (i,j,i+h−1,j+h−1) should be inside of
this grid. In other words, calculate the count of square submatrices of the given grid A which have
their value equal to 1 for every element present on and above their main diagonal.

Input format

 The first line contains an integer T denoting the number of test cases.
 The first line of each testcase contains two space-separated integers N and M denoting the
size of the grid A.
 The following N lines describe the grid. Each line consists of M characters that are
either 0 or 1.

Output format

For each test case, print the count of square submatrices in a new line.

54. Group of Zeros

Problem statement

Mike and Bob were playing with binary numbers. Mike was quite confident with his problem-solving
skills, so he asks Bob to give him a challenge.

Bob gave him some Queries Q. For each query, Mike's task is to count the total numbers
distinct of sequences that contain 0's and 1's of each length in the range [L, R] inclusive.

To make these tasks more challenging, Bob wanted that 0's must be present in a group of
lengths divisible by K.
 DSA PROBLEMS
Mike needs your help to accomplish this challenge.

Note

 Two Sequences A and B are Distinct, if their lengths are not same or there exists an index i,
for which A[i]≠B[i].
 The count of sequences can be huge. So, Output the count mod 109+7.

Task

Find all the total numbers of unique sequences which follow the above conditions for each query.

Example

Assumptions

 Q = 2, K = 3
 L = 2, R = 4
 L = 1, R = 5

Approach

Here, Q = 2 and K = 3

 Possible sequence with length 1 are (1).

 Possible sequence with length 2 is (11).
 Possible sequences with length 3 are (000, 111). Note that 0's should appear in a group with a
length divisible by K = 3.
 Possible sequences with length 4 are (0001, 1000, 1111).
 Possible sequence with length 5 are (00011, 11000, 10001, 11111).
 For Query 1
o Mike can form 6 different sequences of length [2, 4] with groups of lengths divisible
by 3.
 For Query 2
o Mike can form 11 different sequences of length [1, 5] with groups of lengths divisible
by 3.

Function Description

Complete the max_count function provided in the editor. This function takes the following
3 parameters and returns the answer integer.

 K: Represents the length of a group of 0's.

 L: Represents the starting range of length of sequences.
 R: Represents the ending range of length of sequences.

Input Format

Note: This is the input format that you must use to provide custom input (available above the Compile
and Test button).

 The first line contains two integers Q and K denoting the number of Queries and length of
group of 0's.
 Q lines follow:
 DSA PROBLEMS
o For each Query, a single line contains two integers L and R denoting the range of
length of sequences.

Output Format

For each query(in a separate line), print the total numbers of unique/distinct sequences with length in
range [L, R] and 0′s must be present in a group of lengths divisible by K. Don't forget to take modulo
1000000007(109+7)

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.

55. Tree Control

Problem statement

You are given an undirected weighted tree, in which 1 is the root node. Control value of each node
denoted by ci.

Let's take two nodes (V,U ) such that V is the ancestor of U. V controls U if the distance between U
and V is less than or equal to the control value of U

Find the number of vertices controlled by each node.

Task:

Print N integers — the i-th of these numbers should be equal to the number of vertices that the i-th
vertex controls.

Note

 Assume 1-based indexing.

Example:

Assumptions

 N=3
 c = {2,7,5}
 p = {1,1}
 w = {5,4}

Approach

 Node 1 controls 2 because distance between 1 and 2 is 5 which less than control value of 2,
which is 7
 Node 1 controls 3 because distance between 1 and 3 is 4 which is less than control value of 3,
which is 5

Thus, answer is {2,0,0}

Function Description :
 DSA PROBLEMS
Complete the solve function provided in the editor. This function takes the following 4 parameters and
returns the required answer:-

 N: Integer denoting the number of nodes

 c: Integer array denoting control values of each node
 p: Parent array, where pi denotes the parent of the (i+1)-th node in the tree
 w: Integer array, where wi denotes weight of the edge between pi and (i+1)

The function must return -

 array of N integers — the i-th integer equal to number of nodes that the i-th node controls.

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile
and Test button).

 The first line contains single integer N

 The second line contains N integers ci — the control value of i-th node.
 The third line contains (N−1) integers. pi — the parent of the (i+1)-th node in the tree
 The fourth line contains (N−1) integers. wi — weight of the edge between pi and (i+1)

Output format

 Print N integers — the i-th of these integers equal to the number of nodes that the i-th node
controls.

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.

56. Memory Reader

Problem statement
There is a new AI in town. It reads through horizontal strips of memory. Let the strip of memory be
divided into blocks numbered 1,2,3... etc. There is good data at some integer points on the memory
given in an array memory. The AI can only read at these points. The AI aims to read the last point of
good memory. Also, the AI can only move in the forward direction.
To read a memory, it can move from one good point to another. It can move its reader pointer to
either L−1 or L or L+1 points if the length of its last jump was L. Initially, it is at point 0 (which is
always a good memory). The first move can only be to the first good memory point. Determine if it
can move to the last memory. It is ensured that the good memory points are given in sorted order.

Note: The AI doesn’t need to read all the good memory points.

Input format:

 The first line contains T, denoting the number of test cases.

 The first line of each test case contains one integer N, denoting the number of good memory
points.
 The second line of each test case contains an array memory of N space-separated integers,
denoting the position of the good memory points.

Output format:
 DSA PROBLEMS
For each test case, print the string YES if the AI can read the last memory point, else print the string
NO.

57. Tree Query

Problem statement
You are given a tree of N nodes rooted at node 1 and each node has a value where value of i′th node
is Ai.You're given Q queries, in each query two integers x,k given. Find if possible such that all nodes
in the subtree of node x (including x) has values greater than or equal to k by performing swapping of
two nodes any number of times. You can swap two nodes u and v such that u belongs to subtree of x
(including x) and v does not. If possible then find minimum number of swapping of nodes required
otherwise print −1.Note: Since the queries are independent, the initial tree is retained after each query.

Input format

 The first line contains T denoting the number of test cases. The description of each test case is
as follows.
o The first line contains an integer N denoting the number of nodes in tree.
o Next line contains space-separated integers denoting value of each node.
o Each of the following N−1 lines contain two integers u and v denoting edge between
nodes u and v.
o The next line contains a single integer Q - the number of queries.
o Next Q lines contain two space-separated integers x,k.

Output format

For query print the answer in a new line.

58. Light Up the Bulbs

Problem statement

Demon has a warehouse and he wants to light up the warehouse by lighting N bulbs on the ceiling.
Consider the ceiling as a coordinate axis and Demon knows the X - Y coordinates of the bulbs that
need to be put at the ceiling. Now the bulbs need to be connected with each other using wires. Demon
wants to know the minimum sum of the square of the length of wires required to connect the bulbs.

Note: If bulb A and B are connected, bulb B and bulb C are connected, then bulb A and C are also
connected.

Input Format: The first line contains an integer N - the number of bulbs needed to light up the
warehouse. The next N lines contain two space-separated integers x and y - representing the
coordinates of the bulb.

Output Format: Output the minimum length of wire required to connect the light bulbs.

59. Good strings

Problem statement
Given a string S of length N consisting of only lower case alphabets. Print the total count of good
strings. A string is called good if:- - its length is N and consists of only lower case alphabets. - it
mismatches with S at exactly K different indexes. - it is lexicographically smaller than S. Since the
answer could be large print it with modulo 109+7.

Input format
 DSA PROBLEMS
 The first line contains T denoting the number of test cases.
 The first line of each test case contains integers N and K, denoting the size of the length of
the S and mismatch count.
 The next line contains S.

Output format

Print the number of total possible good strings. Since the answer could be large print it with
modulo 109+7.

60. Weird Range Query

Problem statement
Given an array, A, containing n integers, a1,a2,a3,...an, you have to answer q queries.
For each query you will be given a one-indexed range [l,r], l≤r, and your answer to each query should
be: ∑i=lr(r−i+1).a[i]
For example, if A=[6,10,−9,11,12], for l=2, and r=5:
(5−2+1)∗10+(5−3+1)∗−9+(5−4+1)∗11+(5−5+1)∗12=
4∗10+3∗−9+2∗11+1∗12=47

NOTE: The answer to a query may not fit a 32-bit integer type.

Input format

 The first line contains two integers n, and q - denoting the number of integers in A, and the
number of queries respectively.
 The next line contains n integers, ai - denoting the values of the integers in A.
 The ith line among next q lines each contain two integers, li, and ri - denoting the indices to
be queried for the ith query.

Output formatYour program should output q lines, and the ithof these lines should be the answer to
the ith query.

61. Count Permutations

Problem statement
From a permutation P of length N, Alice constructs an array A of length N such that
Ai=max(P1,P2,…,Pi). For example, if P=[2,1,3,5,4], then Alice constructs the array A=[2,2,3,5,5].
You are given an array A containing N integers. Find the number of permutations of length N from
which Alice can construct the given array A. Since the answer can be very large, print it
modulo (109+7).

Input format

 The first line contains T denoting the number of test cases. The description of T test cases is
as follows:
 For each test case:
o The first line contains a single integer N denoting the size of array A.
o The second line contains N integers A1,A2,…,AN denoting the elements of A.
 DSA PROBLEMS
Output formatFor each test case, print the number of permutations, modulo (109+7) of length N from
which the given array A can be constructed.

DIFFICULTY LEVEL -> HARD

62. Modulus of Grid

Problem statement
You are given a grid of size N∗M. The rows are numbered from 0 to N−1, and the columns are
numbered from 0 to M−1.In a single move, you can go from (x,y) to ((x+A)modN,y) or
(x,(y+B)modM) where A and B are positive integers satisfying 1≤A≤N−1 and 1≤B≤M−1.You are also
given Q queries. You have to solve each query independently.In each query, you will be given two
positions (x1, y1) and (x2, y2). You have to find the number of possible pairs of (A, B) so that (x2,
y2) is reachable from (x1, y1) using any number of moves (possibly zero).

Input Format:The first line of the input contains two space-separated integers N and M representing
the size of the grid.The next line contains a single integer Q representing the number of queries.The
next Q lines contain 4 space-separated integers x1, y1, x2, y2.

Output Format:Output Q lines, where the ith line represents the answer to the ith query.

Constraints:2≤N,M≤1051≤Q≤1050≤x1,x2≤N−10≤y1,y2≤M−1

63. Collect Maximum Coins

Problem statement
There are N cities in a country, numbered 1 through N. They are connected with N−1 undirected roads
in such a way that one can move from one city to any other city through these roads. Each city
contains a box filled with coins. The ith city contains a box with Ai coins, and it requires
Bi consecutive seconds to open the box.
Alice is initially in city 1. While standing in city i(1≤i≤N), Alice can either:

 move to an adjacent city in 1 second, or

 spend Bi consecutive seconds to open the box in the ith city and collect Ai coins.

Find the maximum number of coins Alice can collect in K seconds.

Alice can visit a city any number of times but can collect the coins only once from a city.

Input format

 The first line of input contains two integers N denoting the number of cities and K denoting
total seconds available to collect the coins.
 The second line contains N integers A1,A2,…,AN, denoting the number of coins in the cities.
 The third line contains N integers B1,B2,…,BN, denoting the number of seconds to open the
boxes.
 N−1 lines follow. The ith line contains two integers Xi,Yi denoting a road between the
cities Xi,Yi. It is guaranteed that the roads and cities form a tree structure.
 DSA PROBLEMS
Output format For each query, print the maximum number of coins Alice can collect in K seconds.

64. LCM Range Queries

Problem statement
You are given Q queries. In each query, you are given two integers X and R, find the number of pairs
of integers (A,B) such that1≤A<B≤R, andLCM(A,A+1,...,B)=X.

Input format

 The first line of the input contains a single integer Q — the number of queries.
 The next Q lines contain two space-separated integers X and R for each query respectively.

Output formatOutput Q lines, each line containing a single integer — the answer to the corresponding
query.

65. Even Array

Problem statement

An array is called good if every element of the array is an even integer.You are given an array A of
length N. In one move, you can do one of the following operations:

 Choose an index i and set Ai=⌊Ai2⌋

 Choose an index 1≤i<∣A∣and replace Ai,Ai+1 with one occurrence of Ai⊕Ai+1.
Here ∣A∣ denotes the length of the array A and ⊕ denotes bitwise XOR operation.

Find the minimum number of moves needed to make array A good.

Input format

 The first line contains T denoting the number of test cases. The description of T test cases is
as follows:
 For each test case:
o The first line contains N denoting the size of array A.
o The second line contains N space-separated integers A1,A2,…,AN - denoting the
elements of A.

Output formatFor each test case, print the minimum number of moves needed to make array A good.

66. Counting Ways

Problem statement
The universe is a 2D array of dimensions N∗M. You are standing in cell (1,1) at the start.
You can make a move in three different directions:

 ↓
 →
 ↘

The biggest length of a move the man can make is K. If the current position of the man is (x,y), in a
one-step he can go to:

 (x+w,y) where w≤K and x+w≤N.

 DSA PROBLEMS
 (x,y+w) where w≤K and y+w≤M.
 (x+w,y+w) where w≤K and x+w≤N and y+w≤M.

In how many ways can you reach the cell (N,M)?

Since the solution can be very large, compute it modulo 109+7.

Input format

 The first line contains Q denoting the number of test cases.

 Each of the next Q lines contains three integers, N, M and K.

Output format

For each test case, output on a new line the count of ways to reach the cell (N,M) modulo 109+7.

67. Birthday Bash

Problem statement
Emma planned to buy a string S consisting of lowercase English characters of size N as a gift for her
friend Ava on her birthday. Ava had Q other friends who also wanted to contribute but were not
happy with the string. So all Q of her friends decide to do either of the two operations :

 1 x - Give an index x and ask Emma to reverse the string from index x to N−x−1.
 2 x - Give an index x and ask Emma to change the character at index x to the alphabetically
next character. For example, if the character was a, it would become b (assume that a is
alphabetically next to z).

All of this was too much for Emma to handle alone. So she asked you to help her find the final string
after doing all the operations.

Note : Assume 0-based indexing.

Input Format:

 The first line of input contains an integer T, denoting the number of test cases.
 The first line of each test case contains two integers, N and Q, denoting the size of the string
and the number of friends of Ava respectively.
 The following line contains a string of size N.
 The next Q line contains two integers and is one of two types :
o 1 x - denoting that Emma needs to reverse the string from index x to N−x−1 (it is
guaranteed that x will be less than N−x−1).
o 2 x - denoting that Emma needs to change the x'th character to alphabetically next
character.

Output Format:For each test case, print a string of size N denoting the final string.

68. Tree Intersection Query

Problem statement
You are given a tree consisting of N nodes. You have to answer Q queries. The qth query consists of a
node xq and a set of kq distinct nodes {v1,v2,…,vkq}. The answer to the qth query is the number of
pairs (i,j) such that 1≤i<j≤kq and the node xq lies on the path between the nodes vi and vj.

Input format
 DSA PROBLEMS
 The first line of input contains two integers N denoting the number of nodes in the tree
and Q denoting the number of queries.
 N−1 lines follow. The ith line contains two integers Xi,Yi denoting an edge between the
nodes Xi,Yi. It is guaranteed that the given nodes and edges form a tree.
 2⋅Q lines follow. The (2⋅q−1)-th of these lines contains two integers xq,kq, and the 2⋅q -th
line contains kq space-separated distinct integers {v1,v2,…,vkq}.

Output format

For each query, print the answer in a separate line.

69. Minimize nodes

Problem statement
You are given N strings. Each string is given in the form of an array cnt of size 26 where the ith
element in array denotes the count of the ith character of lowercase English alphabets in the string.

You have to select exactly 4 strings and insert the strings into a Trie. You are allowed to shuffle the
characters in each string.

Task

Determine the minimum number of nodes present in Trie if the strings are selected optimally.

Notes

 Trie will always have a root node. Include root node in the count of nodes present in Trie.
 Insertion proceeds by walking the Trie according to the string to be inserted, then appending
new nodes for the suffix of the string that is not contained in the Trie.

Input format

 The first line contains a single integer T which denotes the number of test cases.
 The first line of each test case contains an integer N.
 The next N lines of each test case contain 26 space-separated integers denoting the count of
each lowercase English alphabet in the string.

Output format

For each test case, print the minimum number of nodes present in Trie in a new line.

70. The longest subarray

Problem statement
You are given an array of N positive integers and Q queries. In each query, you are given two
integers l and r.
For each query, find the length of the longest subarray such that the bitwise AND of the subarray
is 2k where l≤k≤r and if no subarray exists, then the answer will be 0.

Input format

 The first line contains T denoting the number of test cases. The description of each test case is
as follows.
 DSA PROBLEMS
o The first line contains an integer N denoting the number of array elements.
o The next line contains N space-separated integers.
o The next line contains an integer Q denoting the number of queries that are required
to be performed.
o Each of the next Q lines contains two integers l and r.

Output format

For each test case, Q lines must be printed and the ith line should contain the output for the ith query.

71. Totient sum

Problem statement

Given a positive integer, N.

Euler phi function denoted by ϕ(n) counts the number of positive integers up to n that are co-
prime to n. Let us have a function F as: F(x)=∑i=1x∑j=1iϕ(i)×ϕ(j)
Task Your task is to calculate the value of F(N). Since the value can be large output it modulo 109+7.
Example

Assumptions

 N=4

Approach

 F(4) =
( ϕ(1).ϕ(1) + ϕ(2).ϕ(1) + ϕ(2).ϕ(2) + ϕ(3).ϕ(1) + ϕ(3).ϕ(2) + ϕ(3).ϕ(3) + ϕ(4).ϕ(1) + ϕ(4).ϕ(2)
+ ϕ(4).ϕ(3) + ϕ(4).ϕ(4) ) % ( 109+7 ).
 F(4) = 23.

Function description

Complete the solve function provided in the editor. This function takes the following
single parameter and returns the value of the function F:

 N: Represents the value of a number.

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile
and Test button).

 The first line contains a single integer T, which denotes the number of test cases. T also
specifies the number of times you have to run the solve function on a different set of inputs.
 For each test case:
o First line contains a single integer denoting the value of N.

Output format

For each test case, print in a new line, a single integer denoting the value of F(N) mod 109+7.

Code snippets (also called starter code/boilerplate code)

 DSA PROBLEMS
This question has code snippets for C, CPP, Java, and Python.

72. Absent?

Problem statement

John is attending a workshop for N days. He gets into trouble if he misses the workshop for
two consecutive days.

Task

Determine the probability of him getting into trouble if he misses the workshop organized on the last
day.

It can be shown that the probability can be represented as PQ where P and Q are coprime integers.
Print the value of P*Q-1 modulo 109+7.

Note: There is an equal probability of John getting absent or present on any day.

Example

Assumption

 N=2

Approach

 All possible combinations are (A,A) and (P,A) where P = Present , A = Absent.
 Out of these, only (A, A) gets john into trouble.
 The probability of this is 1/2. Thus the value of (1/2) modulo (109+7) is 500000004.

Therefore the answer is 500000004.

Function description

Complete the absent function provided in the editor. This function takes the following parameter and
returns the probability of John getting into trouble:

 N: Represents the number of days of the workshop

Input format

Note: This is the input format you must use to provide custom input (available above the Compile and
Test button).

 The first line contains T denoting the number of test cases. T also specifies the number of
times you have to run the absent function on a different set of inputs.
 For each test case:
o The first line contains N denoting the number of days of the workshop

Output format

For each test case in a new line, print the required probability.

Code snippets (also called starter code/boilerplate code)

 DSA PROBLEMS
This question has code snippets for C, CPP, Java, and Python.

73. Odd Xor Subsequences

Problem statement

Problem:

You are given a sequence A of size N and Q queries. For each query:

 You are given an integer K.

 Your task is to count the number of subsequences of A of size K such that Bitwise Xor
Sum of elements of the subsequence is odd. Since the answer can be large, compute it
modulo 998,244,353.

Note: Bitwise Xor Sum of a sequence is Bitwise XOR of its elements.

Input Format:

 The first line of the input contains a single integer N.

 The second line of the input contains N space-separated integers A1,A2,...,AN.
 The third line of the input contains a single integer Q.
 Q lines follow. Each of these lines contains a single integer K describing a query.

Output Format:

 For each query, print a single line containing one integer ― the count of subsequences
of A of size K having odd Bitwise Xor Sum modulo 998,244,353.

74. Path Queries

Problem statement
You are given an undirected tree with N nodes and the tree is rooted at node 1. Each node has an
integer value A[i] associated with it represented by an array A of size N.
Also, you are given Q queries of the following type:

 u v: Find the value of Minimum + Maximum + Median of all the values present on the simple
path between node u and node v.
 Suppose, K nodes are present on the simple path, then Median
is defined as ((K+1)/2)th smallest element present on the simple path.

Input format

 The first line contains two space-separated integers N, Q denoting the number of nodes and
queries respectively.
 The second line contains N space-separated integers denoting array A.
 Next N−1 lines contain two space-separated integers denoting the edges of the tree.
 Next Q lines contain two space-separated integers denoting the queries.

Output format

Print Q space-separated integers denoting the answer of queries.

 DSA PROBLEMS

75. Maximize Array Function

Problem statement
For array A[] of N integers we call a function fA=∑i=1Ni∗AiGiven array of N integers and in one
move you can select a position and delete the array element. Then all elements to the right are shifted
to the left by 1 position. For example, given array is [5,9,15,25,15,9], if you delete A2 then the array
will be [5,15,25,15,9] and then if you delete A2 the array will be [5,25,15,9]. Find the maximum value
of fA of modified array by performing the above move any number of times (possibly 0).

Input format

 The first line contains T denoting the number of test cases. The description of each test case is
as follows.
o The first line contains an integer N denoting the number of array elements.
o The next line contains N space-separated integers.

Output format

For each test case, print the answer in a new line.

76. Query In Hackland

Problem statement
There are N houses H1,H2,....,HN in 2D cardinal plane and given the coordinate of i′th house for
each 1≤i≤N. Now you're given Q queries. For each query you're given four integers l,r,x,k. Find the
smallest index i such that l≤i≤r and euclidean distance between the position of Hi and (x,0) is greater
than or equal to k. If no such index present then answer will be −1.Euclidean distance between two
point (xi,yi) and (xj,yj) is (xi−xj)2+(yi−yj)2

Input format

 The first line contains T denoting the number of test cases. The description of each test case is
as follows.
o The first line contains an integer N denoting the number of houeses.
o Next N lines contain two space-separated integers xi and yi denotes the coordinate
of Hi.
o The next line contains Q denoting number of queries to be performed.
o Next Q lines contain four space-separated integers l,r,x,k.

Output format

For each query, print the answer in a new line.

77. Avoid Maxima-Minima

Problem statement

You are given an array A consisting of N integers.

An index of the array i (1<i<N) is called :

 DSA PROBLEMS
 local maximum if the element on the ith index is strictly greater than the two adjacent
elements (that is, Ai>Ai−1,Ai>Ai+1 )
 local minimum if the element on the ith index is strictly less than the two adjacent elements
(that is,Ai<Ai−1,Ai<Ai+1).

You want to obtain an array such that it does not contain any local maximums and local minimums.
To do that, you can do the following operation any number of times:

 Choose an index i (1≤i≤∣A∣) and delete the element A[i] from the array. Here ∣A∣ denotes the
current length of array A. After each operation, the length of the array decreases by one.

Find the maximum length of the final array A which does not contain any local maximums and local
minimums.

Input format

 The first line contains T denoting the number of test cases. The description of T test cases is
as follows:
 For each test case:
o The first line contains N denoting the size of array A.
o The second line contains N space-separated integers A[1], A[2], ....., A[N] - denoting
the elements of A.

Output formatFor each test case, print the maximum length of the final array A which does not contain
any local maximums and local minimums.

78. Maximum component

Problem statement

You are given a graph consisting of N nodes. Initially, there is no edge in the graph. You have to
process Q queries of the following two types:

 1 X Y: connect nodes X and Y with an undirected edge.

 2 K: Print the size of the largest connected component if K extra undirected edges are added
between any pair of nodes of the graph.

Note that the edges connected in the type 2 query are not considered in further queries.

Note: Since the size of input-output is large, prefer using fast input-output methods.

Input format

 The first line of input contains N denoting the number of nodes and Q denoting the number of
queries respectively.
 Q lines follow. Each of these lines contains an integer type[i], denoting the type of the i-th
query. if type[i] is 1, it contains two more integers X, Y, if type[i] = 2, it contains an
integer K.

Output format
For each query of type 2, print the size of the largest connected component in a separate line.
 DSA PROBLEMS

79. Modulus of Grid

Problem statement
You are given a grid of size N∗M. The rows are numbered from 0 to N−1, and the columns are
numbered from 0 to M−1.
In a single move, you can go from (x,y) to ((x+A)modN,y) or (x,(y+B)modM) where A and B are
positive integers satisfying 1≤A≤N−1 and 1≤B≤M−1.
You are also given Q queries. You have to solve each query independently.
In each query, you will be given two positions (x1, y1) and (x2, y2). You have to find the number of
possible pairs of (A, B) so that (x2, y2) is reachable from (x1, y1) using any number of moves
(possibly zero).

Input Format:
The first line of the input contains two space-separated integers N and M representing the size of the
grid.
The next line contains a single integer Q representing the number of queries.
The next Q lines contain 4 space-separated integers x1, y1, x2, y2.

Output Format:
Output Q lines, where the ith line represents the answer to the ith query.

80. Collect Maximum Coins

Problem statement
There are N cities in a country, numbered 1 through N. They are connected with N−1 undirected roads
in such a way that one can move from one city to any other city through these roads. Each city
contains a box filled with coins. The ith city contains a box with Ai coins, and it requires
Bi consecutive seconds to open the box.
Alice is initially in city 1. While standing in city i(1≤i≤N), Alice can either:

 move to an adjacent city in 1 second, or

 spend Bi consecutive seconds to open the box in the ith city and collect Ai coins.

Find the maximum number of coins Alice can collect in K seconds.

Alice can visit a city any number of times but can collect the coins only once from a city.

Input format

 The first line of input contains two integers N denoting the number of cities and K denoting
total seconds available to collect the coins.
 The second line contains N integers A1,A2,…,AN, denoting the number of coins in the cities.
 The third line contains N integers B1,B2,…,BN, denoting the number of seconds to open the
boxes.
 N−1 lines follow. The ith line contains two integers Xi,Yi denoting a road between the
cities Xi,Yi. It is guaranteed that the roads and cities form a tree structure.

Output format For each query, print the maximum number of coins Alice can collect in K seconds.
 DSA PROBLEMS

81. LCM Range Queries

Problem statement
You are given Q queries. In each query, you are given two integers X and R, find the number of pairs
of integers (A,B) such that1≤A<B≤R, andLCM(A,A+1,...,B)=X.

Input format

 The first line of the input contains a single integer Q — the number of queries.
 The next Q lines contain two space-separated integers X and R for each query respectively.

Output format Output Q lines, each line containing a single integer — the answer to the corresponding
query.

82. Minimize nodes

Problem statement
You are given N strings. Each string is given in the form of an array cnt of size 26 where the ith
element in array denotes the count of the ith character of lowercase English alphabets in the string.

You have to select exactly 4 strings and insert the strings into a Trie. You are allowed to shuffle the
characters in each string.

Task

Determine the minimum number of nodes present in Trie if the strings are selected optimally.

Notes

 Trie will always have a root node. Include root node in the count of nodes present in Trie.
 Insertion proceeds by walking the Trie according to the string to be inserted, then appending
new nodes for the suffix of the string that is not contained in the Trie.

Input format

 The first line contains a single integer T which denotes the number of test cases.
 The first line of each test case contains an integer N.
 The next N lines of each test case contain 26 space-separated integers denoting the count of
each lowercase English alphabet in the string.

Output format

For each test case, print the minimum number of nodes present in Trie in a new line.

83. The longest subarray

Problem statement
You are given an array of N positive integers and Q queries. In each query, you are given two
integers l and r.
For each query, find the length of the longest subarray such that the bitwise AND of the subarray
is 2k where l≤k≤r and if no subarray exists, then the answer will be 0.
 DSA PROBLEMS
Input format

 The first line contains T denoting the number of test cases. The description of each test case is
as follows.
o The first line contains an integer N denoting the number of array elements.
o The next line contains N space-separated integers.
o The next line contains an integer Q denoting the number of queries that are required
to be performed.
o Each of the next Q lines contains two integers l and r.

Output format

For each test case, Q lines must be printed and the ith line should contain the output for the ith query.

84. Totient sum

Problem statement

Given a positive integer, N.

Euler phi function denoted by ϕ(n) counts the number of positive integers up to n that are co-
prime to n.Let us have a function F as:F(x)=∑i=1x∑j=1iϕ(i)×ϕ(j)
TaskYour task is to calculate the value of F(N). Since the value can be large output it
modulo 109+7.Example

Assumptions

 N=4

Approach

 F(4) =
( ϕ(1).ϕ(1) + ϕ(2).ϕ(1) + ϕ(2).ϕ(2) + ϕ(3).ϕ(1) + ϕ(3).ϕ(2) + ϕ(3).ϕ(3) + ϕ(4).ϕ(1) + ϕ(4).ϕ(2)
+ ϕ(4).ϕ(3) + ϕ(4).ϕ(4) ) % ( 109+7 ).
 F(4) = 23.

Function description

Complete the solve function provided in the editor. This function takes the following
single parameter and returns the value of the function F:

 N: Represents the value of a number.

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile
and Test button).

 The first line contains a single integer T, which denotes the number of test cases. T also
specifies the number of times you have to run the solve function on a different set of inputs.
 For each test case:
o First line contains a single integer denoting the value of N.

Output format
 DSA PROBLEMS
For each test case, print in a new line, a single integer denoting the value of F(N) mod 109+7.

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.

85. Absent?

Problem statement

John is attending a workshop for N days. He gets into trouble if he misses the workshop for
two consecutive days.

Task

Determine the probability of him getting into trouble if he misses the workshop organized on the last
day.

It can be shown that the probability can be represented as PQ where P and Q are coprime integers.
Print the value of P*Q-1 modulo 109+7.

Note: There is an equal probability of John getting absent or present on any day.

Example

Assumption

 N=2

Approach

 All possible combinations are (A,A) and (P,A) where P = Present , A = Absent.
 Out of these, only (A, A) gets john into trouble.
 The probability of this is 1/2. Thus the value of (1/2) modulo (109+7) is 500000004.

Therefore the answer is 500000004.

Function description

Complete the absent function provided in the editor. This function takes the following parameter and
returns the probability of John getting into trouble:

 N: Represents the number of days of the workshop

Input format

Note: This is the input format you must use to provide custom input (available above the Compile and
Test button).

 The first line contains T denoting the number of test cases. T also specifies the number of
times you have to run the absent function on a different set of inputs.
 For each test case:
o The first line contains N denoting the number of days of the workshop

Output format
 DSA PROBLEMS
For each test case in a new line, print the required probability.

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.

86. Odd Xor Subsequences

Problem statement

Problem:

You are given a sequence A of size N and Q queries. For each query:

 You are given an integer K.

 Your task is to count the number of subsequences of A of size K such that Bitwise Xor
Sum of elements of the subsequence is odd. Since the answer can be large, compute it
modulo 998,244,353.

Note: Bitwise Xor Sum of a sequence is Bitwise XOR of its elements.

Input Format:

 The first line of the input contains a single integer N.

 The second line of the input contains N space-separated integers A1,A2,...,AN.
 The third line of the input contains a single integer Q.
 Q lines follow. Each of these lines contains a single integer K describing a query.

Output Format:

 For each query, print a single line containing one integer ― the count of subsequences
of A of size K having odd Bitwise Xor Sum modulo 998,244,353.

87. Path Queries

Problem statement
You are given an undirected tree with N nodes and the tree is rooted at node 1. Each node has an
integer value A[i] associated with it represented by an array A of size N.
Also, you are given Q queries of the following type:

 u v: Find the value of Minimum + Maximum + Median of all the values present on the simple
path between node u and node v.
 Suppose, K nodes are present on the simple path, then Median
is defined as ((K+1)/2)th smallest element present on the simple path.

Input format

 The first line contains two space-separated integers N, Q denoting the number of nodes and
queries respectively.
 The second line contains N space-separated integers denoting array A.
 Next N−1 lines contain two space-separated integers denoting the edges of the tree.
 Next Q lines contain two space-separated integers denoting the queries.

Output format
 DSA PROBLEMS
Print Q space-separated integers denoting the answer of queries.

88. Maximize Array Function

Problem statement
For array A[] of N integers we call a function fA=∑i=1Ni∗AiGiven array of N integers and in one
move you can select a position and delete the array element. Then all elements to the right are shifted
to the left by 1 position. For example, given array is [5,9,15,25,15,9], if you delete A2 then the array
will be [5,15,25,15,9] and then if you delete A2 the array will be [5,25,15,9]. Find the maximum value
of fA of modified array by performing the above move any number of times (possibly 0).

Input format

 The first line contains T denoting the number of test cases. The description of each test case is
as follows.
o The first line contains an integer N denoting the number of array elements.
o The next line contains N space-separated integers.

Output format

For each test case, print the answer in a new line.

89. Query In Hackland

Problem statement
There are N houses H1,H2,....,HN in 2D cardinal plane and given the coordinate of i′th house for
each 1≤i≤N. Now you're given Q queries. For each query you're given four integers l,r,x,k. Find the
smallest index i such that l≤i≤r and euclidean distance between the position of Hi and (x,0) is greater
than or equal to k. If no such index present then answer will be −1.Euclidean distance between two
point (xi,yi) and (xj,yj) is (xi−xj)2+(yi−yj)2

Input format

 The first line contains T denoting the number of test cases. The description of each test case is
as follows.
o The first line contains an integer N denoting the number of houeses.
o Next N lines contain two space-separated integers xi and yi denotes the coordinate
of Hi.
o The next line contains Q denoting number of queries to be performed.
o Next Q lines contain four space-separated integers l,r,x,k.

Output format

For each query, print the answer in a new line.

90. Avoid Maxima-Minima

Problem statement

You are given an array A consisting of N integers.

An index of the array i (1<i<N) is called :

 DSA PROBLEMS
 local maximum if the element on the ith index is strictly greater than the two adjacent
elements (that is, Ai>Ai−1,Ai>Ai+1 )
 local minimum if the element on the ith index is strictly less than the two adjacent elements
(that is,Ai<Ai−1,Ai<Ai+1).

You want to obtain an array such that it does not contain any local maximums and local minimums.
To do that, you can do the following operation any number of times:

 Choose an index i (1≤i≤∣A∣) and delete the element A[i] from the array. Here ∣A∣ denotes the
current length of array A. After each operation, the length of the array decreases by one.

Find the maximum length of the final array A which does not contain any local maximums and local
minimums.

Input format

 The first line contains T denoting the number of test cases. The description of T test cases is
as follows:
 For each test case:
o The first line contains N denoting the size of array A.
o The second line contains N space-separated integers A[1], A[2], ....., A[N] - denoting
the elements of A.

Output formatFor each test case, print the maximum length of the final array A which does not contain
any local maximums and local minimums.

91. Maximum component

Problem statement

You are given a graph consisting of N nodes. Initially, there is no edge in the graph. You have to
process Q queries of the following two types:

 1 X Y: connect nodes X and Y with an undirected edge.

 2 K: Print the size of the largest connected component if K extra undirected edges are added
between any pair of nodes of the graph.

Note that the edges connected in the type 2 query are not considered in further queries.

Note: Since the size of input-output is large, prefer using fast input-output methods.

Input format

 The first line of input contains N denoting the number of nodes and Q denoting the number of
queries respectively.
 Q lines follow. Each of these lines contains an integer type[i], denoting the type of the i-th
query. if type[i] is 1, it contains two more integers X, Y, if type[i] = 2, it contains an
integer K.

Output format For each query of type 2, print the size of the largest connected component in a
separate line.
 DSA PROBLEMS

DIFFICULTY LEVEL -> MEDIUM

92. Breaking walls

Problem statement

Bob is assigned a task to collect the maximum stars possible. He has a hammer that can be used to
break only one wall!

You are given a grid of size N×M that contains ., ∗, # #. Here:

 . represents all the points where Bob can move

 # # represents the walls and hence bob cannot pass through it or be on it
 ∗ represents the stars bob needs to collect

Note: If you can reach this cell, you can collect this star.

Bob is allowed to start on any of the non # # cells and he is free to move up, down, left, or right. But,
having the hammer, Bob can break only one wall and move through that broken wall. Bob wants to
collect the maximum possible stars possible. Help Bob by finding the maximum possible stars he can
collect.

Input format

 The first line contains two integers N and M.

 Next N lines contains M characters consisting of ., ∗, # #.

Output format

Print a single line containing a single integer.

93.NUMBER OF RBS

Consider a string $$S$$ of $$n$$ characters '(', ')', and '?'. Your task is to replace each character '?'
with either ')' or '('. Determine the number of Regular Bracket Sequences (RBS) that is possible after
these replacements.

A bracket sequence is called regular if it is possible to obtain correct arithmetic expressions by

inserting characters «+» and «1» into this sequence. For example, sequences «(())()», «()» and
«(()(()))» are regular, whereas «)(», «(()» and «(()))(» are not.

Input format

 The first line contains one integer $$T$$ denoting the number of test cases.
 The first line of each test case contains an integer $$n$$ that denotes the length of string
$$S$$.
 The second line of each test case contains a string that denotes the string $$S$$.

Output format
 DSA PROBLEMS
For each test case, print the number of RBS modulo \(1e9+7\) in a new line.

94. Permutations

Problem statement
You are given a string S containing only lowercase alphabet characters. You are also given Q queries.
In each query, you are given two integers l and r. Consider a substring S′ of string S[l,r]. You are
required to print the number of permutations of the substring S′ that are lexicographically smallest
among all permutations of S′. Since the number can be very large, print it modulo 1e9+7.

Input format

 The first line contains an integer T denoting the number of test cases.
 The first line of each test case contains an integer n denoting the length of string S.
 The second line of each test case contains a string S.
 The third line of each test case contains an integer Q denoting the number of queries.
 Next Q lines of each test case contain two space-separated integers l and r.

Output format

For each test case, print the number of permutations for each query in the next Q lines.

95. Temporary Tree

Problem statement
You are gifted a tree consisting of N vertices. There are two types of edges each with a weight val and
denoted by a type value that is either 0 or 1. A pair (i,j), where i<j is called GOOD if, while traversing
from vertex i to vertex j, we never pass through an edge of type 0. Your task is to calculate the sum of
the path’s weight of all the GOOD pairs present in the tree. Print the final answer modulo 109+7.

Input Format:

 The first line of input contains an integer T, denoting the number of test cases.
 The first line of each test case contains the integer N.
 The next N - 1 line contains four integers A, B, type and val where A and B represents the
vertices of the tree, type represent the type of the edge and val define the edge weight.

Output format:

For each test case, print an integer denoting the sum of the path's weight of all the GOOD pairs
modulo 109+7.

96. ARITHEMATIC SEQUENCE BY EXACTLY ONE MOVE

You are given a sequence \(a = (a_1, a_2, \dots, a_N)\) consisting of \(N\) integers. You must choose
a index \(i\) and replace \(a_i\) by an integer \(k \neq a_i \)exactly once. Determine if you can
rearrange \(a\) to form an arithmetic sequence or not. Note that \(a\) is an arithmetic sequence if and
only if all differences between any two consecutive elements are the same.

Input Format

 The first line contains a single integer \(T\) — the number of test cases.
 DSA PROBLEMS
 For each testcase:
o The first line contains one integer \(n\) — the length of the sequence.
o The second line contains \(n\) integers \(a_1, a_2, ... , a_n\).

Output Format

 For each testcase, output "YES" if the \(a\) can be transformed into an arithmetic sequence.
Otherwise, output "NO".

97. Complete Knight Traversals Count

Problem statement

Given two positive integers m and n which are the height and width of a 0-indexed 2D-array board.
Find the number of Knight Traversals. A Knight Traversal includes a knight (of a chess game) starts
at (0,0) of the board and visits every cell of the board exactly once. The starting cell (0,0) is
considered visited and you shouldn't visit it again.

Note that a knight can move from cell (r1, c1) to cell (r2, c2) if 0 <= r2 <= m - 1 and 0 <= c2 <= n - 1
and min(abs(r1 - r2), abs(c1 - c2)) = 1 and max(abs(r1 - r2), abs(c1 - c2)) = 2.

Input constraints:

1 <= m, n <= 5

Input format:

The first line has two integers m and n separated by a space.

Output format:

A number indicating the number of distinct Knight Traversals.

98. Prefix XOR Sum

Problem statement
You are given an array A containing N integers and Q queries. Each query is denoted by two integers
L,R. The answer to a query is AL+(AL⊕AL+1)+⋯+(AL⊕AL+1⊕⋯⊕AR), where ⊕ denotes the
bitwise XOR operator.

Input format

 The first line contains two integers N denoting the size of array A and Q denoting the
number of queries:
 DSA PROBLEMS
 The second line contains N space-separated integers A1,A2,…,AN - denoting the elements
of A.
 Each of the next Q lines contains two integers L,R.

Output format

For each test query, print the answer in a separate line.

99. Count All Factors

Problem statement
You are given an array a of size n having distinct prime integers.
You will be given q queries. In each query, you will be given an integer k and you have to count the
sum of Perfect Factors of the factors of this number.
Perfect Factors: Let's suppose an integer k. Suppose z1,z2,...,zt (t = number of factors) are the factors
of integer k. Let's consider one of the factor, say zi. We now calculate how many elements in the
provided array (a) perfectly divide this number. Suppose ci is the number of elements in the array that
are perfectly dividing the factor zi. Therefore, number of perfect factors for factor zi = ci. So sum
of perfect factors of all the factors of number k is c1+c2+...+ct.

Input Format:

 The first line contains one integer n − size of array a.

 The second line contains n space - seperated integers a[1],a[2],...,a[n] − denoting the elements
of a.
 The third line contains one integer q − number of queries. Then q queries follow.
 The first and only line of each query contains a single integer k.

Output Format:

For each query, output in a separate line:

The sum of Perfect Factors of the factors of the number..

100. Good strings

Problem statement
Given a string S of length N consisting of only lower case alphabets. Print the total count of good
strings. A string is called good if:-- its length is N and consists of only lower case alphabets.- it
mismatches with S at exactly K different indexes.- it is lexicographically smaller than S.Since the
answer could be large print it with modulo 109+7.

Input format

 The first line contains T denoting the number of test cases.

 The first line of each test case contains integers N and K, denoting the size of the length of
the S and mismatch count.
 The next line contains S.

Output format

Print the number of total possible good strings. Since the answer could be large print it with
modulo 109+7.
 DSA PROBLEMS

101. Light Up the Bulbs

Problem statement

Demon has a warehouse and he wants to light up the warehouse by lighting N bulbs on the ceiling.
Consider the ceiling as a coordinate axis and Demon knows the X - Y coordinates of the bulbs that
need to be put at the ceiling. Now the bulbs need to be connected with each other using wires. Demon
wants to know the minimum sum of the square of the length of wires required to connect the bulbs.

Note: If bulb A and B are connected, bulb B and bulb C are connected, then bulb A and C are also
connected.

Input Format: The first line contains an integer N - the number of bulbs needed to light up the
warehouse. The next N lines contain two space-separated integers x and y - representing the
coordinates of the bulb.

Output Format: Output the minimum length of wire required to connect the light bulbs.

102. Types of burgers

Problem statement
Bob sells burgers with three different combinations, B1, B2 and B3. There are total X, Y, and Z
burgers with combinations, B1, B2, and B3 respectively. Each burger has an integer value called
deliciousness as follows:

 The deliciousness of the burgers with the B1 combination are B11,B12,B13,....,B1X.

 The deliciousness of the burgers with the B2 combination are B21,B22,B23,....,B2Y.
 The deliciousness of the burgers with the B3 combination are B31,B32,B33,....,B3Z.

Alice decides to buy K boxes containing three burgers, one from each of the combinations. The
deliciousness of a box is the sum of the deliciousness of the burgers present inside it.
There are X∗Y∗Z such ways to select a box. Print the maximum total sum of deliciousness that Alice
can get by buying K boxes.

Input format

 The first line contains an integer T denoting the number of test cases.
 The first line of each test case contains three space-separated integers X, Y, and Z.
 The second line of each test case contains a single integer K.
 The third line of each test case contains X space-separated integers denoting array B1i.
 The fourth line of each test case contains Y space-separated integers denoting array B2j.
 The fifth line of each test case contains Z space-separated integers denoting array B3k.

Output format

For each test case, print the maximum total sum of deliciousness that Alice can get by buying K
boxes in a new line.
 DSA PROBLEMS

103. Permutations

Problem statement
You are given a string S containing only lowercase alphabet characters. You are also given Q queries.
In each query, you are given two integers l and r. Consider a substring S′ of string S[l,r]. You are
required to print the number of permutations of the substring S′ that are lexicographically smallest
among all permutations of S′. Since the number can be very large, print it modulo 1e9+7.

Input format

 The first line contains an integer T denoting the number of test cases.
 The first line of each test case contains an integer n denoting the length of string S.
 The second line of each test case contains a string S.
 The third line of each test case contains an integer Q denoting the number of queries.
 Next Q lines of each test case contain two space-separated integers l and r.

Output format

For each test case, print the number of permutations for each query in the next Q lines.

Constraints

1≤T≤2000001≤n≤2000001≤Q≤2000001≤l≤r≤n

 It is guaranteed that the sum of n over T test cases does not exceed 1e6.
 It is also guaranteed that the sum of Q over T test cases does not exceed 1e6.