Optional Questions

Lab 8

Q1. House Allocation (MEDIUM) - arrays

In a bustling city, there are n applicants looking for houses and m available houses to rent. Each
applicant has a specific size in mind for their desired house, and they are willing to accept a house
as long as its size falls within a certain acceptable range. Your task is to write a C++ program that
distributes the houses to the applicants in a way that maximizes the number of applicants who
receive a house and print the number of applicants who successfully received the house.

Input

● The first line contains three integers:

○ n: the number of applicants (1 ≤ n ≤ 200)
○ m: the number of available houses(1 ≤ m ≤ 200)
○ k: the maximum allowed size difference (0 ≤ k ≤ 1,000)
● The second line contains n integers, where the i-th integer ai (1 ≤ ai ≤ 1000) represents the
desired house size of the i-th applicant.
● The third line contains m integers, where the j-th integer bj (1 ≤ bj ≤ 1000) represents the
size of the j-th house.

Output

● Print a single integer: the maximum number of applicants who can successfully receive a
house.

Example

Input -
543
50 70 80 90 60
48 72 83 60

Output -
4

Explanation -

The first applicant wants a house with size 50, and as k = 3, the applicant can accept any house
with size between 47 to 53.
As there is a house with size 48 available, the first applicant will get that house.

The second applicant wants a house with size 70, and as k = 3, the applicant can accept any
house with size between 67 to 73.
As there is a house with size 72 available, the second applicant will get that house.
Similarly, we can find houses for all the applicants.
For this example, a good choice will be :
Applicant 1 gets house 1 (i.e. house with size 48)
Applicant 2 gets house 2 (i.e. house with size 72)
Applicant 3 gets house 3 (i.e. house with size 83)
Applicant 4 doesn’t get any house.
Applicant 5 gets house 4 (i.e. house with size 60)

Note
● Do not write any C++ statements for printing general messages. For example, the following
should NOT be present in your program:
○ cout << "Enter a number:"
○ cout << "The computed answer is", etc.
● cout should be used to print only the computed final output. In addition, do not print
unnecessary spaces unless specified in the program.
● If any hard coding is found, or if any test case passes by merely writing a cout statement
and without any logic, then the marks for that test case will NOT be awarded.
● IMPORTANT: Do not use variable-length arrays. (It is not C++ standard and doesn’t work
on MS Visual C++.)

Visible Test Cases

Input Output

654 5
30 40 60 70 80 90
28 33 58 65 77

335 3
40 50 60
45 55 65

4 2 10 2
100 150 200 250
110 140

252 2
75 85
74 73 76 86 87

630 3
10 20 30 40 50 60
10 20 30
Q2. String Interleavings

Write a C++ program that implements a recursive function to generate and print all
possible interleavings of two strings that are accepted from the user in the main program.

Interleaving of two strings means, combining them in such a way that the order of the
characters from each string is preserved. For example, if we have strings “ab” and “12”,
one possible interleaving is “a1b2” but “b1a2” is invalid as the order of the characters from
string 1 is not maintained. If two interleavings result in the same string, then print both the
strings.

Input format:

● The first line will contain 2 integers m and n, representing the length of the strings a
and b, respectively. (1 <= n, m <= 10)
● The second and the third line contains two strings a and b respectively. (All the
characters are lowercase letters)

Output format:

● Print all possible interleavings of a and b, each on a new line.

Order of the output

● The order of the output is important.

● Begin with the characters of the first string followed by the characters of the second
string
● Prioritize combinations that start with the first string first, followed by the
combinations that introduce characters from the second string in the specific
sequence. i.e. start with the characters from the first string in leftmost positions, then
interleave with the characters from the second string while respecting the order.
● See the testcaes to know the pattern.

Note :

● Do not write any C++ statements for printing general messages. For example, the
following should NOT be present in your program:
● cout << "Enter a number:"
● cout << "The computed answer is", etc.
● cout should be used to print only the computed final output. In addition, do not print
unnecessary spaces unless specified in the program.
● If any hard coding is found, or if any test case passes by merely writing a cout
statement and without any logic, then the marks for that test case will NOT be
awarded.
Visible Test Cases
Input Output

22 byme
by bmye
me bmey
mbye
mbey
meby

22 meby
me mbey
by mbye
bmey
bmye
byme

32 dogon
dog doogn
on doong
doogn
doong
donog
odogn
odong
odnog
ondog

33 boxcap
box bocxap
cap bocaxp
bocapx
bcoxap
bcoaxp
bcoapx
bcaoxp
bcaopx
bcapox
cboxap
cboaxp
cboapx
cbaoxp
cbaopx
cbapox
caboxp
cabopx
cabpox
capbox
23 gorun
go groun
run gruon
gruno
rgoun
rguon
rguno
rugon
rugno
rungo

11 ab
a ba
b

11 aa
a aa
a
Q3. Phone Number using recursion

Write a C++ program to generate all possible letter combinations from a given string of digits (2-9) based
on the mapping of digits to letters found on a telephone keypad.

On a traditional telephone keypad, the digits correspond to the following letters:

● 2: "abc"
● 3: "def"
● 4: "ghi"
● 5: "jkl"
● 6: "mno"
● 7: "pqrs"
● 8: "tuv"
● 9: "wxyz"

In the main function, accept a string of digits from the user. Define a recursive function named
generateCombinations and pass the string of digits as input to the function. The function should not return
any value; instead, it should print each valid combination of letters formed.

Input
● A string digits (1 ≤ length ≤ 4) containing only digits from 2 to 9.

Output
● A list of all possible letter combinations.

Assumptions on the input

● The input string will only contain digits from 2 to 9.
● The length of the input string will be at least 1 and at most 4.

Note
● Do not write any C++ statements for printing general messages. For example, the
following should NOT be present in your program:
○ cout << "Enter a number:"
○ cout << "The computed answer is", etc.
● cout should be used to print only the computed final output. In addition, do not print
unnecessary spaces unless specified in the program.
● If any hard coding is found, or if any test case passes by merely writing a cout
statement and without any logic, then the marks for that test case will NOT be
awarded.
● IMPORTANT: Do not use variable-length arrays. (It is not C++ standard and doesn’t
work on MS Visual C++.)
Visible Test Cases
Input Output

23 ad
ae
af
bd
be
bf
cd
ce
cf

85 tj
tk
tl
uj
uk
ul
vj
vk
vl

234 adg
adh
adi
aeg
aeh
aei
afg
afh
afi
bdg
bdh
bdi
beg
beh
bei
bfg
bfh
bfi
cdg
cdh
cdi
ceg
ceh
cei
cfg
cfh
cfi
Q4. Minimum Swaps to bring elements less than k together

You are given an array (nums) of integers and an integer k. You are required to find the
minimum number of swaps to bring all the elements in the array which are less than or
equal to k together (They must be consecutive but not necessarily sorted).

Swapping can be done for any two elements in the array, they may not be consecutive.

Input format:

● The first line contains an integer n which represents the size of the array and
another integer k. (1 <= n <= 100,000 and 1 <= k <= 10,000,000)
● The second line contains n integers which are the elements of the array nums. (1 <=
nums[i] <= 10,000,000 for all i from 0 to n-1)

Output format:

● A single line containing an integer which is the minimum number of swaps required
to bring all elements of the array less than or equal to k together.

Note :

● Do not write any C++ statements for printing general messages. For example, the
following should NOT be present in your program:
● cout << "Enter a number:"
● cout << "The computed answer is", etc.
● cout should be used to print only the computed final output. In addition, do not print
unnecessary spaces unless specified in the program.
● If any hard coding is found, or if any test case passes by merely writing a cout
statement and without any logic, then the marks for that test case will NOT be
awarded.

Visible Test Cases

Input Output

52 0
12345

1 100 0
5

58 0
5 3 7 21 9
84 2
13572468

86 1
24741584

In the first testcase, we see that only two elements are less than k (2 here) and they are
already grouped (1st two elements). Hence, number of swaps required are 0.

In the last testcase, 6 elements are less than 6 which are 2, 4, 4, 1, 5, 4. Swapping the last
4 with the 7 results in all elements less than k to be together. Hence the answer is 1.
Q5. Split array largest sum
Given an Array[] nums of N elements and a number m. ( 1 <= m <= N ) . Write a function to split a given
array into m subarrays (they must cover all the elements). The maximum subarray sum achievable out of m
subarrays formed, must be the minimum possible. Find that possible subarray sum. The function should
take n, m and the array nums as input and return the minimized subarray sum.

Input format:

● The first line will contain an integer n (number of elements in array nums).
● The second line will contain the elements of array nums.
● The third line will contain an integer m.
● Assume that m<=n in all cases.

Output format:

● Output will be the minimized largest sum among m subarrays. It should be an integer.

Note :

● Do not write any C++ statements for printing general messages. For example, the following should
NOT be present in your program:
● cout << "Enter a number:"
● cout << "The computed answer is", etc.
● cout should be used to print only the computed final output. In addition, do not print unnecessary
spaces unless specified in the program.
● If any hard coding is found, or if any test case passes by merely writing a cout statement and
without any logic, then the marks for that test case will NOT be awarded.
● IMPORTANT: Do not use variable length arrays. (It is not C++ standard and doesn’t work on MS
Visual C++.)

Visible Test Cases:

Input Output
5 18
7 2 5 10 8
2
5 6
12345
3

6 31
962716
1

4 60
10 20 30 40
2
7 25
9 4 14 25 6 7 12
5
Explanation :
For Input:
5
7 2 5 10 8
2

● Split 1: [7, 2, 5] and [10, 8]

○ Sum of first subarray = 7 + 2 + 5 = 14
○ Sum of second subarray = 10 + 8 = 18
○ Maximum subarray sum = max(14, 18) = 18
● Split 2: [7, 2] and [5, 10, 8]
○ Sum of first subarray = 7 + 2 = 9
○ Sum of second subarray = 5 + 10 + 8 = 23
○ Maximum subarray sum = max(9, 23) = 23
● Split 3: [7] and [2, 5, 10, 8]
○ Sum of first subarray = 7
○ Sum of second subarray = 2 + 5 + 10 + 8 = 25
○ Maximum subarray sum = max(7, 25) = 25
Minimize the largest sum: Out of all the possible splits, the first split gives the smallest maximum
subarray sum, which is 18.