PROBLEM SOLVING

SDE Readiness Training

Exercise 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 Ways To Express Hard

Problem statement : You are given the number ‘N’. The task is to find the
number of ways to represent ‘N’ as a sum of two or more consecutive natural
numbers.
Example:
N=9
‘9’ can be represented as:
2+3+4=9
4+5=9
The number of ways to represent ‘9’ as a sum of consecutive natural numbers
is ‘2’. So, the answer is ‘2’.
Note:
1. The numbers used to represent ‘N’ should be natural numbers (Integers
greater than equal to 1).

Sample Input 1:
2
21
15
Sample Output 1:
3
3
Explanation Of Sample Input 1:
Test Case 1:
‘21’ can be represented as:
1 + 2 + 3 + 4 + 5 + 6 = 21

Little practice is worth more than a ton of theory

1
 PROBLEM SOLVING
SDE Readiness Training
6 + 7 + 8 = 21
10 + 11 = 21
The number of ways to represent ‘21’ as a sum of consecutive natural numbers
is ‘3’. So, the answer is ‘3’.
Test Case 2:
‘15’ can be represented as:
1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
The number of ways to represent ‘15’ as a sum of consecutive natural numbers
is ‘3’. So, the answer is ‘3’.
Sample Input 2:
2
18
16
Sample Output 2:
2
0

Constraints:
1 <= T <= 1000
3 <= N <= 10 ^ 5
Where ‘T’ is the number of test cases, and ‘N’ is the given number.
2 Butterfly star pattern Hard
Problem statement: Create a program to print a butterfly star pattern
consisting of stars in a symmetrical butterfly shape. The pattern should be
printed such that the stars form wings on both sides of the centerline. The
number of stars in each wing should decrease towards the centerline.

Input 1 : rows = 5
Output 1:
* *
** **
*** ***
**** ****
**********
**** ****

Little practice is worth more than a ton of theory

2
 PROBLEM SOLVING
SDE Readiness Training
*** ***
** **
* *

Input 2: rows =7
Output 2 :

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

3 Sum of Floored Pairs Hard

Problem Statement : Given an integer array nums, return the sum of

floor(nums[i] / nums[j]) for all pairs of indices 0 <= i, j < nums.length in the
array. Since the answer may be too large, return it modulo 10^9 + 7.

The floor() function returns the integer part of the division.

Example 1:
Input: nums = [2,5,9]
Output: 10
Explanation:
floor(2 / 5) = floor(2 / 9) = floor(5 / 9) = 0
floor(2 / 2) = floor(5 / 5) = floor(9 / 9) = 1
floor(5 / 2) = 2
floor(9 / 2) = 4
floor(9 / 5) = 1

Little practice is worth more than a ton of theory

3
 PROBLEM SOLVING
SDE Readiness Training
We calculate the floor of the division for every pair of indices in the array
then sum them up.

Example 2:
Input: nums = [7,7,7,7,7,7,7]
Output: 49

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

4 Sum of two prime numbers Hard

Problem statement: Rita has to design a code that takes a positive integer
or number which is required to be given by the user. Then the code should
further identify whether that digit can be expressed as the sum of two prime
numbers. If the inserted number can be expressed as sum of two prime
numbers then, print the integer can be expressed as sum of two prime
numbers as a result.

Sample Input 1: 34

Sample Output 1:3,31

Sample Input1: 20

Sample Output2: 7,13

Constraints:

N>=1

5 Sum of Bit Differences Hard

Problem Statement : Given an integer array of n integers, find sum of bit

differences in all pairs that can be formed from array elements. Bit difference

Little practice is worth more than a ton of theory

4
 PROBLEM SOLVING
SDE Readiness Training
of a pair (x, y) is count of different bits at same positions in binary
representations of x and y.

Examples :

Input: arr[] = {1, 2}

Output: 4
All pairs in array are (1, 1), (1, 2)
(2, 1), (2, 2)
Sum of bit differences = 0 + 2 +
2+0
=4

Input: arr[] = {1, 3, 5}

Output: 8
All pairs in array are (1, 1), (1, 3), (1, 5)
(3, 1), (3, 3) (3, 5),
(5, 1), (5, 3), (5, 5)
Sum of bit differences = 0 + 1 + 1 +
1+0+2+
1+2+0
=8
Constraints:
1 <= n <= 10^5
1 <= arr[i] <= 10^5
6 Minimum X (xor) A Hard
Problem Statement : Given two integers A and B, the task is to find an
integer X such that (X XOR A) is minimum possible and the count of set bit in
X is equal to the count of set bits in B.

Example 1:
Input:
A = 3, B = 5
Output: 3
Explanation:
Binary(A) = Binary(3) = 011

Little practice is worth more than a ton of theory

5
 PROBLEM SOLVING
SDE Readiness Training
Binary(B) = Binary(5) = 101
The XOR will be minimum when x = 3
i.e. (3 XOR 3) = 0 and the number
of set bits in 3 is equal
to the number of set bits in 5.

Example 2:
Input:
A = 7, B = 12
Output: 6
Explanation:
(7)2= 111
(12)2= 1100
The XOR will be minimum when x = 6
i.e. (6 XOR 7) = 1 and the number
of set bits in 6 is equal to the
number of set bits in 12.

Constraints :
0 <= A, B <= 10^9

7 Median of 2 Sorted Arrays of Different Sizes Hard

Problem Statement : Given two sorted arrays array1 and array2 of size m
and n respectively. Find the median of the two sorted arrays.

Example 1:
Input:
m = 3, n = 4
array1[] = {1,5,9}
array2[] = {2,3,6,7}
Output: 5
Explanation: The middle element for {1,2,3,5,6,7,9} is 5

Example 2:
Input:
m = 2, n = 4

Little practice is worth more than a ton of theory

6
 PROBLEM SOLVING
SDE Readiness Training
array1[] = {4,6}
array2[] = {1,2,3,5}
Output: 3.5

Constraints:
0 ≤ m,n ≤ 10^6
1 ≤ array1[i], array2[i] ≤ 10^9

8 Subarrays With Equal 0’s, 1’s and 2’s Hard

Problem statement : You are given an array containing ‘N’ integers. In the
array, the elements are 0, 1 and 2. You have a simple task, find the count of
non-empty subarrays containing an equal number of 0’s, 1’s and 2’s.

The subarray of ARR is a contiguous part of the array ARR, i. e. the array ARRi,
ARRi+1, . . . . . , ARRj for some 0 ≤ i ≤ j ≤ N - 1.

For Example :

If ‘N’ = 5, ‘ARR’ = {1, 1, 0, 2, 1}

There are exactly two subarrays that contain an equal number of 0’s, 1’s and
2’s.

The first subarray is from ‘ARR[1]’ to ‘ARR[3]’, ie: {1, 0, 2}.

The second subarray is from ‘ARR[2]’ to ‘ARR[4]’, ie: {0, 2, 1}.

Sample Input 1 :

11021

1100

Sample Output 1 :

Little practice is worth more than a ton of theory

7
PROBLEM SOLVING
SDE Readiness Training
Explanation For Sample Input 1 :

For test case 1 :

We will print 2 because:

There are exactly two subarrays that contain an equal number of 0’s, 1’s and
2’s.

The first subarray is from ARR[1] to ARR[3], ie: {1, 0, 2}, and the second
subarray is from ARR[2] to ARR[4], ie: {0, 2, 1}

For test case 2 :

We will print 0 because:

The input array doesn’t contain any element equal to 2, so it’s impossible to
form a non-empty subarray with an equal number of 0’s, 1’s and 2’s.

Sample Input 2 :

102102

110022

Sample Output 2 :

Constraints :

1 ≤ T ≤ 10

1 ≤ N ≤ 1000

ARR[i] = {0, 1, 2}

Little practice is worth more than a ton of theory

8
 PROBLEM SOLVING
SDE Readiness Training
9 Count Array Pairs Divisible by K Hard

Problem Statement : Given a 0-indexed integer array nums of length n

and an integer k, return the number of pairs (i, j) such that:
● 0 <= i < j <= n - 1 and
● nums[i] * nums[j] is divisible by k.

Example 1:
Input: nums = [1,2,3,4,5], k = 2
Output: 7
Explanation:
The 7 pairs of indices whose corresponding products are divisible by 2 are (0,
1), (0, 3), (1, 2), (1, 3), (1, 4), (2, 3), and (3, 4).
Their products are 2, 4, 6, 8, 10, 12, and 20 respectively.
Other pairs such as (0, 2) and (2, 4) have products 3 and 15 respectively,
which are not divisible by 2.

Example 2:
Input: nums = [1,2,3,4], k = 5
Output: 0
Explanation: There does not exist any pair of indices whose corresponding
product is divisible by 5.

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

10 Split Array Largest Sum Hard

Problem Statement : Given an array arr[] of N elements and a number K.,

split the given array into K subarrays such that the maximum subarray sum
achievable out of K subarrays formed is minimum possible. Find that possible
subarray sum.

Example 1:
Input:
N = 4, K = 3
arr[] = {1, 2, 3, 4}
Little practice is worth more than a ton of theory
9
 PROBLEM SOLVING
SDE Readiness Training
Output: 4
Explanation:
Optimal Split is {1, 2}, {3}, {4}.
Maximum sum of all subarrays is 4, which is minimum possible for 3 splits.

Example 2:
Input:
N = 3, K = 2
A[] = {1, 1, 2}
Output:
2
Explanation:
Splitting the array as {1,1} and {2} is optimal.
This results in a maximum sum subarray of 2.

Constraints:
1 ≤ N ≤ 10^5
1≤K≤N
1 ≤ arr[i] ≤ 10^4

11 Print Spiral Hard

Problem statement : For a given two-dimensional integer array/list of size
(N x M), print it in a spiral form. That is, you need to print in the order followed
for every iteration:
a. First row(left to right)
b. Last column(top to bottom)
c. Last row(right to left)
d. First column(bottom to top)
Mind that every element will be printed only once.

Little practice is worth more than a ton of theory

10
PROBLEM SOLVING
SDE Readiness Training
Refer to the Image:

Sample Input 1:
1
44
1234
5678
9 10 11 12
13 14 15 16
Sample Output 1:
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
Sample Input 2:
2
33
123
456
789
31
10
20
30
Sample Output 2:
123698745
10 20 30

Constraints :
1 <= t <= 10^2

Little practice is worth more than a ton of theory

11
 PROBLEM SOLVING
SDE Readiness Training
0 <= N <= 10^3

0 <= M <= 10^3

12 Zigzag Conversion Hard

Problem Statement: The string "PAYPALISHIRING" is written in a zigzag
pattern on a given number of rows like this: (you may want to display this
pattern in a fixed font for better legibility)
P A H N
APLSIIG
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a
number of rows:
string convert(string s, int numRows);

Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A LS IG
YA HR
P I

Constraints:
● 1 <= s.length <= 1000
● s consists of English letters (lower-case and upper-case), ',' and '.'.
● 1 <= numRows <= 1000
●
13 Longest repeating and non-overlapping substring Hard
Problem Statement: Given a string s of length n, find the longest repeating
non-overlapping substring in it. In other words, find 2 identical substrings of

Little practice is worth more than a ton of theory

12
 PROBLEM SOLVING
SDE Readiness Training
maximum length which do not overlap. Return the longest non-overlapping
substring. Return "-1" if no such string exists.
Note: Multiple Answers are possible but you have to return the substring
whose first occurrence is earlier.
For Example: "abhihiab", here both "ab" and "hi" are possible answers. But
you will have to return "ab" because it's first occurrence appears before the
first occurrence of "hi".

Example 1:
Input:
n=9
s = "acdcdacdc"
Output:
"acdc"
Explanation:
The string "acdc" is the longest Substring of s which is repeating but not
overlapping.

Example 2:
Input:
n=7
s = "heheheh"
Output:
"heh"

Explanation:
The string "heh" is the longest Substring of s which is repeating but not
overlapping.

Constraints:
1 <= n <= 10^3
14 Palindrome partitioning Hard

Problem statement : You are given a string 'str' of length 'n'.

Find the minimum number of partitions in the string so that no partition is
empty and every partitioned substring is a palindrome.

Little practice is worth more than a ton of theory

13
 PROBLEM SOLVING
SDE Readiness Training
Example :
Input: 'str' = "aaccb"
Output: 2
Explanation: We can make a valid partition like aa | cc | b.
Detailed explanation ( Input/output format, Notes, Images )

Sample Input 1 :
aaccb
Sample Output 1 :
2
Explanation of sample input 1 :
We can make a valid partition like aa | cc | b.

Sample Input 2 :
ababa
Sample Output 2 :
0
Explanation of sample input 2 :
The string is already a palindrome, so we need not make any partition.

Constraints :
1 <= 'n' <= 100

15 K th element of Two sorted arrays

Problem statement : Richal wants to serve food to needy people. So, he
bought Ladoos from a sweet shop and placed them on plates. There can be
any number of Ladoos present in a plate.
Plates containing Ladoos are placed in two rows. Each row is sorted in
increasing order by the number of Ladoos in a plate.
For example :‘ROW1’ : [2, 5, 8, 17] and ‘ROW2’ : [1, 4, 8, 13, 20]

Now people come one by one in a line to take plates of Ladoos from Richal.
Richal picks the two plates in front, one from each row and gives that plate
to people in which the number of ladoos is the smallest (if both plates

Little practice is worth more than a ton of theory

14
PROBLEM SOLVING
SDE Readiness Training
contain equal numbers of ladoos then he serves any plate from the two
plates) and places the other plate back to its position.
For Example :If ‘ROW1’ is [2, 5, 8, 17] and ‘ROW2’ is [1, 4, 8, 13, 20], then
Richal picks the first plates from each rows, plate containing 2 ladoos from
‘ROW1’ and a plate containing 1 ladoo from ‘ROW2’.
Then he gives the plate with 1 Ladoo to the first person in line and places the
other plate back to its position.

Can you tell how many ladoos the ‘K'th’ person will get?

Sample Input 1 :
2
543
3 11 23 45 52
4 12 14 18
112
1
2
Sample Output 1 :
11
2
Explanation for Sample Output 1 :For sample test case 1:
1’st person will get 3 ladoos i.e a minimum of 3 and 4. Now ‘ROW1’ : [11,
23, 45, 52] and ‘ROW2’ : [4, 12, 14, 18].
2’nd person will get 4 ladoos i.e minimum of 11 and 4. Now ‘ROW1’ : [11,
23, 45, 52] and ‘ROW2’ : [12, 14, 18].
3’rd person will get 11 ladoos i.e minimum of 11 and 12.

For sample test case 2:

1’st person will get 1 ladoos i.e a minimum of 1 and 2. Now ‘ROW1’ : [ ]
and ‘ROW2’ : [2].
2’st person will get 2 ladoos because we have only one element left in ROW2
. Now ‘ROW1’ : [] and ‘ROW2’ : [].
Sample Input 2 :
2
53
1 3 6 7 10

Little practice is worth more than a ton of theory

15
 PROBLEM SOLVING
SDE Readiness Training
3557
332
10 20 20
123
Sample Output 2 :
3
2
Explanation for Sample Output 2 :For sample test case 1:
1’st person will get 1 ladoo i.e minimum of 1 and 3. Now ‘ROW1’ : [3, 7,
10] and ‘ROW2’ : [3, 5, 5, 7].
2’nd person will get 3 ladoos i.e now from both rows we will get a plate of 3
ladoos so Richal can give any one plate containing ladoos from each row. Let
us assume Richal give a plate from ‘ROW2’. Now ‘ROW1’ : [3, 7, 10] and
‘ROW2’ : [5, 5, 7].
3’rd person will get 3 ladoos i.e minimum of 3 and 5. Now ‘ROW1’ : [7, 10]
and ‘ROW2’ : [5, 5, 7].

For sample test case 2:

1’st person will get 1 ladoo i.e minimum of 10 and 1. Now ‘ROW1’ : [10,
20, 30] and ‘ROW2’ : [ 2, 3].
2’nd person will get 2 ladoos i.e minimum of 10 and 2. Now ‘ROW1’ : [10,
20, 30] and ‘ROW2’ : [3].

Constraints :
1 <= T <= 100
1 <= N, M, K <= 10^5
K <= (N + M)
0 <= ROW1[i], ROW2[i] <= 10^5

where ROW1[i] and ROW2[i] denote the number of Ladoos in i’th plates of
ROW1 and ROW2 respectively.

16 Number of Subarrays with Bounded maximum

Problem Statement : Given an integer array nums and two integers left and
right, return the number of contiguous non-empty subarrays such that the
value of the maximum array element in that subarray is in the range [left,
right].

Little practice is worth more than a ton of theory

16
 PROBLEM SOLVING
SDE Readiness Training
The test cases are generated so that the answer will fit in a 32-bit integer.

Example 1:
Input: nums = [2,1,4,3], left = 2, right = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2,
1], [3].

Example 2:
Input: nums = [2,9,2,5,6], left = 2, right = 8
Output: 7

Constraints:
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
0 <= left <= right <= 10^9

17 Longest Substring Of All Vowels in Order

Problem Statement : A string is considered beautiful if it satisfies the

following conditions:
• Each of the 5 English vowels ('a', 'e', 'i', 'o', 'u') must appear at least
once in it.
• The letters must be sorted in alphabetical order (i.e. all 'a's before 'e's,
all 'e's before 'i's, etc.).

For example, strings "aeiou" and "aaaaaaeiiiioou" are considered beautiful, but
"uaeio", "aeoiu", and "aaaeeeooo" are not beautiful.
Given a string word consisting of English vowels, return the length of the
longest beautiful substring of word. If no such substring exists, return 0.
A substring is a contiguous sequence of characters in a string.

Example 1:
Input: word = "aeiaaioaaaaeiiiiouuuooaauuaeiu"
Output: 13
Explanation: The longest beautiful substring in word is "aaaaeiiiiouuu" of
length 13.
Example 2:

Little practice is worth more than a ton of theory

17
PROBLEM SOLVING
SDE Readiness Training
Input: word = "aeeeiiiioooauuuaeiou"
Output: 5
Explanation: The longest beautiful substring in word is "aeiou" of length 5.

Example 3:
Input: word = "a"
Output: 0
Explanation: There is no beautiful substring, so return 0.

Constraints:
1 <= word.length <= 5 * 10^5
word consists of characters 'a', 'e', 'i', 'o', and 'u'.

Little practice is worth more than a ton of theory

18