D) String Pair
Problem Description
One person hands over the list of digits to Mr. String, But Mr. String understands only
strings. Within strings also he understands only vowels. Mr. String needs your help to find
the total number of pairs which add up to a certain digit D.
The rules to calculate digit D are as follow
Take all digits and convert them into their textual representation
Next, sum up the number of vowels i.e. {a, e, i, o, u} from all textual representation
This sum is digit D
Now, once digit D is known find out all unordered pairs of numbers in input whose sum is
equal to D. Refer example section for better understanding.
Constraints
1 <= N <= 100
1 <= value of each element in second line of input <= 100
Number 100, if and when it appears in input should be converted to textual representation
as hundred and not as one hundred. Hence number of vowels in number 100 should be 2
and not 4
Input
First line contains an integer N which represents number of elements to be processed as
input
Second line contains N numbers separated by space
Output
Lower case representation of textual representation of number of pairs in input that sum up
to digit D
Note: - (If the count exceeds 100 print "greater 100")
Time Limit
1
Examples
Example 1
Input
12345
Output
one
Explanation
1 -> one -> o, e
2 -> two -> o
3 -> three -> e, e
4 -> four -> o, u
5 -> five - > i, e
Thus, count of vowels in textual representation of numbers in input = {2 + 1 + 2 + 2 + 2} = 9.
Number 9 is the digit D referred to in section above.
Now from given list of number {1,2,3,4,5} -> find all pairs that sum up to 9.
Upon processing this we know that only a single unordered pair {4, 5} sum up to 9. Hence
the answer is 1. However, output specification requires you to print textual representation of
number 1 which is one. Hence output is one.
Note: - Pairs {4, 5} or {5, 4} both sum up to 9. But since we are asking to count only
unordered pair, the number of unordered pair is this combination is only one.
Example 2
Input
742
Output
zero
Explanation
7 -> seven -> e, e
4 -> four -> o, u
2 -> two -> o
Thus, count of vowels in textual representation of numbers in input = {2 + 2 + 1} = 5. Number
5 is the digit D referred to in section above.
Since no pairs add up to 5, the answer is 0. Textual representation of 0 is zero. Hence output
is zero.
E) Max Sum
Problem Description
Two friends A and B are playing with an array of integers. They both agree upon the
operations to be performed on the array but differ on choice of window size to perform the
said operations.
The operations to be performed on the array are explained below:
· One can choose to add at the most X consecutive elements.
· After performing the addition operation, it is mandatory to skip the next element in the
array.
· The goal is to achieve maximum sum by choosing appropriate elements in the array.
A wants X to be W, while B wants X to be (W + D). This is the only difference that they have.
Your task is to find out who wins. Winner is the person whose sum is higher.
The inputs that will be provided are values of elements of array, value of W and value of D.
Example:
Array: 4 5 6 1 2 7 8 9
Window Size (W): 3
Output: 39
Explanation
· We will choose to add elements 4, 5, 6 since window size is 3.
· Since one addition operation is complete, we have to skip one element which is 1.
· We choose to skip element 2 because the next three values are also higher than 2.
· The max sum thus obtained is 39.
Now suppose the array was: 4 5 6 1 2 3 7 8 9
· We will choose to add elements 4, 5, 6 since window size is 3.
· Since one addition operation is complete, we have to skip one element which is 1.
· Now we choose to pick element 2 because we can skip element 3 and still pick up the next 3
values viz 7, 8, 9.
· The max sum thus obtained is 41.
· Note that we picked up only one element in second selection since constraint is only on
maximum number to be chosen, not minimum.
Now suppose the array was: 4 5 6 7
· Since one can start from any index, we choose element 5, 6, 7.
· The max sum thus obtained is 18.
The above examples illustrate the game with a fixed window size of W. Since B prefers to play
the same game with the size of W+D, the steps will remain the same but the max sum output
may be different. Print different output depending on whether A wins, B wins or it’s a tie.
Constraints
0 <= N <= 10 ^ 5
5 <= W <= 10 ^ 5
-10^5 <= D <= 10^5
0 < (W + D) <= N
0 <= elements in array <= 10 ^ 9
Input
First line contains three space separated integers N and W and D respectively, which denote
N - size of array
W - window size
D - difference
Second line contains of N space separated integers denoting the elements of the array
Output
If B wins, print “Right <absolute difference>”
If A wins, print “Wrong <absolute difference>”
If It’s a tie, print “Both are Right”
Refer Examples section for better understanding.
Time Limit
1
Examples
Example 1
Input
8 5 -2
45612789
Output
Wrong 2
Explanation
Here we have given N = 8, W = 5, D = -2
A will maximize the sum of elements of the array using window size 5. Whereas B will
maximize the sum of elements of the array using window size 3 (5-2).
Using logic as depicted above A will get the max sum as 41 and B will get the max sum as 39.
The absolute difference is 41 - 39 = 2.
Hence, output will be: Wrong 2
Example 2
Input
922
456123789
Output
Right 10
Explanation
Here we have given N = 9, W = 2, D = 2
A will maximize the sum of elements of the array using window size 2. Whereas B will
maximize the sum of elements of the array using window size 4 (2+2).
Using logic as depicted above A will get the max sum as 33 and B will get the max sum as 43.
The absolute difference is 43 - 33 = 10.
Hence, output will be: Right 10
Example 3
Input
10 9 -3
4563237892
Output
Both are right
Explanation
Here we have given N = 10, W = 9, D = -3
A will maximize the sum of elements of the array using window size 9. Whereas B will
maximize the sum of elements of the array using window size 6 (9-3).
Using logic as depicted above A will get the max sum as 47 and B will get the max sum as 47.
The absolute difference is 47 - 47 = 0.
Hence, output will be: Both are right
F) 3 Palindrome
Problem Description
Given an input string word, split the string into exactly 3 palindromic substrings.
Working from left to right, choose the smallest split for the first substring that still allows the
remaining word to be split into 2 palindromes.
Similarly, choose the smallest second palindromic substring that leaves a third palindromic
substring.
If there is no way to split the word into exactly three palindromic substrings, print
"Impossible" (without quotes). Every character of the string needs to be consumed.
Cases not allowed -
After finding 3 palindromes using above instructions, if any character of the original string
remains unconsumed.
No character may be shared in forming 3 palindromes.
Constraints
1 <= the length of input sting <= 1000
Input
First line contains the input string consisting of characters between [a-z].
Output
Print 3 substrings one on each line.
Time Limit
1
Examples
Example 1
Input
nayannamantenet
Output
nayan
naman
tenet
Explanation
The original string can be split into 3 palindromes as mentioned in the output.
However, if the input was nayanamantenet, then the answer would be "Impossible".
Example 2
Input
aaaaa
Output
aaa
Explanation
The other ways to split the given string into 3 palindromes are as follows -
[a, aaa, a], [aaa, a, a], [aa, aa, a], etc.
Since we want to minimize the length of the first palindromic substring using left to right
processing, the correct way to split is [a, a, aaa].
Example 3
Input
aaaabaaaa
Output
aaabaaa
Explanation
The other ways to split the given string into 3 palindromes are as follows -
[aaaa, b, aaaa], [aa, aabaa, aa], etc.
Since we want to minimize the length of the first palindromic substring using left to right
processing, the correct way to split is [a, aaabaaa, a].
