PROBLEM SOLVING

SDE Readiness Training

Self-Practice No. : VI

Topics Covered : Basic Math, Control Flow, Arrays,Strings, Functions, Bit

Manipulation

Date : 20.02.2025

Solve the following problems

Q Question Detail Level

No.

1 Friendly pair Hard

Problem statement : Vino wants to check if the given two

numbers are friendly pair or not. Friendly pair(Amicable numbers)
are two different numbers related in a way such that the Ratio’s sum
of the proper divisors divided by number itself for each is same. Proper
divisors of a number are all the positive integers that divide the
number evenly, excluding the number itself. The sum of proper
divisors of a number is the total sum of all its proper divisors. For
example, the sum of proper divisors of 6 is 1 + 2 + 3 = 6.

Input : n = 6, m = 28

Output : Yes

Explanation:

Divisor of 6 are 1, 2, 3, 6.

Divisor of 28 are 1, 2, 4, 7, 14, 28.

Sum of divisor of 6 and 28 are 12 and 56 respectively.

Abundancy index of 6 and 28 are 2. So they are friendly pair.

Input : n = 18, m = 26

Output : No

Constraints:

Little practice is worth more than a ton of theory

1
 PROBLEM SOLVING
SDE Readiness Training
• 1<=N1,N2<=10 8

2 K pattern Hard

Problem statement : Print a pattern of stars in the shape of the

letter 'K'. The pattern should consist of asterisks (*) forming the
uppercase and lowercase letter 'K'. The program should take the
height of the letter 'K' as input and print the corresponding pattern.

Input 1:

height = 5

Output

*****
****
***
**
*
**
***
****
*****

Input2: height = 3

Output2:

***

**

**

***

Little practice is worth more than a ton of theory

2
 PROBLEM SOLVING
SDE Readiness Training
Constraints:
• 1 <= height <= 26

3 Count the number of subarrays Hard

Problem Statement : Given an array A[] of N integers and a range(L,

R). The task is to find the number of subarrays having sum in the
range L to R (inclusive).

Example 1:
Input:
N = 3, L = 3, R = 8
A[] = {1, 4, 6}
Output:
3
Explanation:
The subarrays are [1,4], [4] and [6]

Example 2:
Input:
N = 4, L = 4, R = 13
A[] = {2, 3, 5, 8}
Output:
6
Explanation:
The subarrays are [2,3], [2,3,5], [3,5],[5], [5,8] and [8]

Constraints:
1 ≤ N ≤ 10^6
1 ≤ A[] ≤ 10^9
1 ≤ L ≤ R ≤ 10^15

4 Self Crossing Hard

Problem Statement : You are given an array of integers distance.

You start at the point (0, 0) on an X-Y plane, and you move
distance[0] meters to the north, then distance[1] meters to the
west, distance[2] meters to the south, distance[3] meters to the

Little practice is worth more than a ton of theory

3
PROBLEM SOLVING
SDE Readiness Training
east, and so on. In other words, after each move, your direction
changes counter-clockwise.
• Return true if your path crosses itself or false if it does not.

Example 1:

Input: distance = [2,1,1,2]

Output: true
Explanation: The path crosses itself at the point (0, 1).

Example 2:

Input: distance = [1,2,3,4]

Output: false
Explanation: The path does not cross itself at any point.
Constraints:
● 1 <= distance.length <= 10^5
● 1 <= distance[i] <= 10^5

Little practice is worth more than a ton of theory

4
 PROBLEM SOLVING
SDE Readiness Training
5 Maximum Score Hard
Problem statement : Tom is playing a board game in which two lists
of distinct numbers ‘A’ and ‘B’ arranged in a non-descending order are
given. The game has certain rules and the player has to pick some
numbers from the given list and the score is the sum of unique picked
numbers. The rules are:

1. Choose any list ‘A’ or ‘B’.

2. Traverse from left to right.

3. After picking a number, if the picked number is present in both the

arrays, you are allowed to traverse to the other array.

You are given arrays,’A’ and ‘B’ of size ‘N’ and ‘M’ respectively. Your
task is to find the maximum score Tom can achieve.

Since the answer can be very large, print answer % (10^9 + 7).

For Example

If the given array are ‘A’ = [1,3,5,7,9] and ‘B’ = [3,5,100]”.The

maximum score can be achieved is 109[1+3+5+100].

Detailed explanation ( Input/output format, Notes, Images )

Sample Input 1:

53

13579

3 5 100

43

1235

1 3 10

Sample Output 1:

109

16

Little practice is worth more than a ton of theory

5
PROBLEM SOLVING
SDE Readiness Training
Explanation of sample input 1:

For the first test case,

The numbers Tom will be pick are [1,3,5,100].The sum of unique

numbers are 109.

Hence, the answer is 109.

For the second test case:

The numbers Tom will be pick are [1,2,3,3,10].The sum of unique

numbers are 16(1+2+3+10).

Hence, the answer is 16.

Sample Input 2:

54

2 4 5 8 10

4689

55

12345

6 7 8 9 10

Sample Output 2:

30

40

Constraints:

• <= T <= 10

• 1 <= N,M <= 10^4.

• 1 <= A[i], B[i] <= 10^6.

Little practice is worth more than a ton of theory

6
 PROBLEM SOLVING
SDE Readiness Training
6 Minimize OR of Remaining Elements Using Operations Hard

Problem Statement : You are given a 0-indexed integer arraynums

and an integer k.
In one operation, you can pick any index i of nums such that 0 <= i
< nums.length - 1 and replace nums[i] and nums[i + 1] with a
single occurrence of nums[i] & nums[i + 1], where & represents the
bitwise AND operator.
Return the minimum possible value of the bitwise OR of the
remaining elements of nums after applying at most k operations.

Example 1:
Input: nums = [3,5,3,2,7], k = 2
Output: 3
Explanation: Let's do the following operations:
1. Replace nums[0] and nums[1] with (nums[0] & nums[1]) so that
nums becomes equal to [1,3,2,7].
2. Replace nums[2] and nums[3] with (nums[2] & nums[3]) so that
nums becomes equal to [1,3,2].
The bitwise-or of the final array is 3.
It can be shown that 3 is the minimum possible value of the bitwise
OR of the remaining elements of nums after applying at most k
operations.

Example 2:
Input: nums = [7,3,15,14,2,8], k = 4
Output: 2
Explanation: Let's do the following operations:
1. Replace nums[0] and nums[1] with (nums[0] & nums[1]) so that
nums becomes equal to [3,15,14,2,8].
2. Replace nums[0] and nums[1] with (nums[0] &
nums[1]) so that nums becomes equal to [3,14,2,8].
3. Replace nums[0] and nums[1] with (nums[0] &
nums[1]) so that nums becomes equal to [2,2,8].
4. Replace nums[1] and nums[2] with (nums[1] &
nums[2]) so that nums becomes equal to [2,0].
The bitwise-or of the final array is 2.

Little practice is worth more than a ton of theory

7
 PROBLEM SOLVING
SDE Readiness Training
It can be shown that 2 is the minimum possible value
of the bitwise OR of the remaining elements of nums
after applying at most k operations.

Constraints:
● 1 <= nums.length <= 10^5
● 0 <= nums[i] < 230
● 0 <= k < nums.length

7 Cake Distribution Problem Hard

Problem Statement : Geek is organizing a birthday party, so his

friends brought a cake for him. The cake consists of N chunks, whose
individual sweetness is represented by the sweetness array. Now at
the time of distribution, Geek cuts the cake into K + 1 pieces to
distribute among his K friends. One piece he took for himself. Each
piece consists of some consecutive chunks. He is very kind, so he left
the piece with minimum sweetness for him.

You need to find the maximum sweetness that the Geek can get if he
distributes the cake optimally.

Example 1:

Input:

N = 6, K = 2

sweetness[] = {6, 3, 2, 8, 7, 5}

Output:

Explanation:

Geek can divide the cake to [6, 3], [2, 8], [7, 5] with sweetness
level 9, 10 and 12 respectively.

Example 2:

Input:

N = 7, K = 3

Little practice is worth more than a ton of theory

8
 PROBLEM SOLVING
SDE Readiness Training
sweetness[] = {1, 2, 4, 7, 3, 6, 9}

Output:

Explanation:

Geek can divide the cake to [1, 2, 4], [7], [3, 6], [9] with
sweetness level 7, 7, 9 and 9 respectively.

Constraints:

1 <= N <= 10^5

0 <= K < N

1 <= sweetness[i] <= 10^9

8 3Sum With Multiplicity Hard

Problem Statement : Given an integer array arr, and an integer
target, return the number of tuples i, j, k such that i < j < k and
arr[i] + arr[j] + arr[k] == target.

As the answer can be very large, return it modulo 109 + 7.

Example 1:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8

Output: 20
Explanation:
Enumerating by the values (arr[i], arr[j], arr[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.

Example 2:

Input: arr = [1,1,2,2,2,2], target = 5

Output: 12
Explanation:
arr[i] = 1, arr[j] = arr[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,

Little practice is worth more than a ton of theory

9
 PROBLEM SOLVING
SDE Readiness Training
and two 2s from [2,2,2,2] in 6 ways.

Example 3:

Input: arr = [2,1,3], target = 6

Output: 1
Explanation: (1, 2, 3) occured one time in the array so we return 1.

Constraints:

3 <= arr.length <= 3000

0 <= arr[i] <= 100

0 <= target <= 300

9 ZigZag Reversal of Two Arrays Hard

Problem Statement : You are given two lists/arrays ‘ARR1’ and

‘ARR2’ consisting of ‘N’ and ‘M’ integers respectively.

Your task is to traverse both ‘ARR1’ and ‘ARR2’ together in Zigzag

order and return a list/array representing their Zigzag traversal.

In ZigZag traversal, we iterate the arrays/list alternatively starting

with ‘ARR1’ i.e. in order ARR1[0], ARR2[0], ARR1[1], ARR2[1],
ARR1[2], ARR2[2] and so on. See the example for more clarity.

Example:Consider ARR1 = [1, 2] and ARR2 = [3, 4, 5, 6], then their

Zigzag traversal will be represented by the list/array [1, 3, 2, 4, 5,
6].
We traverse in order ARR1[0], ARR2[0], ARR1[1], ARR2[1], ARR2[2],
ARR2[3]. Note, ARR1 is completely traversed at the 3rd position, and
after which we simply iterate over ‘ARR2’.

Sample Input 1:

2
10
1
24

Little practice is worth more than a ton of theory

10
 PROBLEM SOLVING
SDE Readiness Training
12
3456

Sample Output 1:

1
132456
Explanation Of Sample Input 1:Test case 1:
Here ’ARR2’ is empty, and ‘ARR1’ has a single integer 1. Thus
their Zigzag traversal is also 1.

Test case 2:
See the problem statement for an explanation.

Sample Input 2:

2
33
111
222
52
12321
91

Sample Output 2:

121212
1921321

Constraints:

• 1<= T <= 50
0 <= N <= 10^4
0 <= M <= 10^4
0 <= ARR1[i] <= 10^9
0 <= ARR2[i] <= 10^9
N+M>0

Minimum Window Substring Hard

10
Problem statement :You are given two strings ‘A’ and ‘B’. Your task
is to return a substring ‘S’ of ‘A’ such that the following conditions hold
true :

Little practice is worth more than a ton of theory

11
 PROBLEM SOLVING
SDE Readiness Training
• You can make ‘B’ from ‘S’ by removing some characters and
rearranging some characters zero or more times.
• Length of ‘S’ must be as minimum as possible.

Note :

Testcases are generated such that a substring always exists and is

unique.
Sample Input 1 :

fight it
Sample Output 1 :

ight
Explanation Of Sample Input 1 :

Given A = “fight” and B = “it”

Consider the substring “ight” of A.
We can remove g and h from it to get “it”.
We can also get "it" from "fight" but it is not the substring with
minimum length.

Sample Input 2 :

Coding cin

Sample Output 2 :

codin
Constraints :

1 <= |A| = |B| <= 3000

Both A, B contain only lowercase English letters.

Where |A| and |B| are the length of strings.

11 Count Subarrays With Median K

Problem Statement : You are given an array nums of size n

consisting of distinct integers from 1 to n and a positive integer k.

Little practice is worth more than a ton of theory

12
PROBLEM SOLVING
SDE Readiness Training
Return the number of non-empty subarrays in nums that have a
median equal to k.

Note:

The median of an array is the middle element after sorting the array
in ascending order. If the array is of even length, the median is the
left middle element.

For example, the median of [2,3,1,4] is 2, and the median of

[8,4,3,5,1] is 4.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [3,2,1,4,5], k = 4

Output: 3
Explanation: The subarrays that have a median equal to 4 are: [4],
[4,5] and [1,4,5].

Example 2:

Input: nums = [2,3,1], k = 3

Output: 1
Explanation: [3] is the only subarray that has a median equal to 3.

Constraints:

• n == nums.length

• <= n <= 10^5

• 1 <= nums[i], k <= n

• The integers in nums are distinct.

Little practice is worth more than a ton of theory

13