Topic : Simple math:

Min Digit
Tom and Jerry are playing a game with an integer N that doesn't contain any zeros in its decimal
representation. Tom starts first and, on his turn, he can swap any two digits of the integer that are in
different positions. Jerry follows by always removing the last digit of the integer. The game
continues in turns until there's only one digit left. Determine the smallest integer Tom can achieve at
the end if he plays optimally.
Input Format
The first and only line of input consists of an integer N consisting of digits 1 - 9.
Output Format
Print the smallest integer that Tom can achieve.
Constraints
10 < N < 109
Example
Input
132
Output
1
Explanation
Tom can swap 3 and 1, N becomes 312. After that Jerry deletes the last digit, N becomes 31. Then
Tom swaps 3 and 1, N becomes 13 and Jerry deletes 3, so the answer is 1.

Harshad Numbers
Given an integer N, check whether it is a Harshad number or not.
Note that a Harshad number is an integer, that is divisible by the sum of its digits.
Input
The first and only line of input contains a integer - N.
Output
Print "Yes" if the number is Harshad number, "No" otherwise.
Constraints
1 <= N <= 109
Example
Input
18
Output
Yes
Explanation
18 / (1 + 8) = 2
As 18 is divisible by the sum of its digits, it is a Harshad number.

Minimum Subtraction
Given a number N, find a number X. On subtracting X from N, N-X should be a power of 2. Find the
minimum value of X.
Input Format
First and only line of input contains an integer N.
Output Format
Print the value X.
Constraints
2 <= N <= 109
Example
Input
10
Output
2
Explanation
N = 10
If we subtract X = 2 from N = 10, N - X = 8 is a power of 2.

Fuel Tank
A truck has two fuel tanks: a main tank and an additional tank. The fuel levels in both tanks are
represented by two integers: mainTank, which represents the fuel in the main tank in litres, and
additionalTank, which represents the fuel in the additional tank in litres.
The truck has a mileage of 10 kilometers per litre. Whenever 5 litres of fuel are consumed from the
main tank, if the additional tank has at least 1 litre of fuel, 1 litre of fuel will be transferred from the
additional tank to the main tank. Print the maximum distance that can be travelled with the given
fuel.
Input Format
The first and only line of input contains two integers mainTank and additionalTank.
Output Format
Print the maximum distance that can be travelled with the given fuel.
Constraints
1 <= mainTank, additionalTank <= 100
Examples
Input 1
5 10
Output 1
60
Input 2
22
Output 2
20
Explanation
Example 1:
After spending 5 litre of fuel, fuel remaining is (5 - 5 + 1) = 1 litre and the distance travelled is 50km.
After spending another 1 litre of fuel, no fuel gets injected in the main tank and the main tank
becomes empty. Total distance travelled is 60km.
Example 2:
After spending 2 litre of fuel, the main tank becomes empty. Total distance traveled is 20km.

Narcissistic Numbers
Given an integer N, check whether it is a Narcissistic number or not.
Note that a Narcissistic number is a number that is the sum of its own digits each raised to the
power of the number of digits
Input Format
The first and only line of input contains an integer - N.
Output Format
Print "Yes" if the number is a Narcissistic number, "No" otherwise.
Constraints
0 <= N <= 109
Example
Input
8208
Output
Yes
Explanation
84 + 24 + 04 + 84 = 8208
Arrange Primes
Given an integer N. Print the count of permutations for the numbers from 1 to N, considering that
prime numbers should be placed at positions with prime indices (1 - based indexing). As the result
might be a large number, print the output % 1e9 + 7.
Input Format
The first and only line of input contains an integer N.
Output Format
Print the count of permutations.
Constraints
1 ≤ N ≤ 100
Example
Input
8
Output
576
Explanation
Self Explanatory

Count Primes
Given an integer n, return the number of prime numbers that are strictly less than n.

Example 1:
Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2:
Input: n = 0
Output: 0

Example 3:
Input: n = 1
Output: 0

Constraints:
● 0 <= n <= 5 * 106
Ugly Number
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Given an integer n, return true if n is an ugly number.

Example 1:
Input: n = 6
Output: true
Explanation: 6 = 2 × 3

Example 2:
Input: n = 1
Output: true
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

Example 3:
Input: n = 14
Output: false
Explanation: 14 is not ugly since it includes the prime factor 7.

Constraints:
● -231 <= n <= 231 - 1

Topic : Patterns :

Floyd Pattern - 1
Print a right-angled triangle pattern using integers. See the example for more details.
Input Format
The first and only line of input contains a single integer N - the size of the triangle.
Output Format
For the given integer, print the right-angled triangle pattern.
Constraints
1 <= N <= 50
Example
Input
6
Output
1
23
456
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21
Explanation
Self Explanatory

Print Hollow Diamond Pattern

Print hollow diamond pattern using '*'. See examples for more details.
Input Format
First line of input contains T - number of test cases. Its followed by T lines, each line contains a
single odd integer N - the size of the diamond.
Constraints
1 <= T <= 100
3 <= N <= 201
Output Format
For each test case, print the test case number as shown, followed by the diamond pattern,
separated by newline.
Sample Input 0
4
3
7
5
15

Sample Output 0
Case #1:
*
**
*
Case #2:
*
 **
* *
* *
* *
**
*
Case #3:
*
**
* *
**
*
Case #4:
*
**
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
**
*

Explanation 0
Self Explanatory

Pascal's Triangle
Given a value N, print the Pascal's Triangle pattern.
Input Format
The first and only line of input contains an integer N.
Output Format
For the given input, print the Pascal's Triangle pattern.
Constraints
1 ≤ N ≤ 30
Example
Input
10
Output
1
11
121
1331
14641
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
Explanation
Self Explanatory

Topic : Arrays :

Max Element in Array

Find the maximum element from the given array of integers.
Input Format
The first line of input contains N - the size of the array and the second line contains the
elements of the array.
Output Format
Print the maximum element of the given array.
Constraints
1 <= N <= 103
-109 <= ar[i] <= 109
Example
Input
5
-2 -19 8 15 4
Output
15
Explanation
Self Explanatory
Number Distribution
Print the count of the occurrences of positive integers, negative integers, and zeroes in the given
array.
Input Format
The first line of the input contains an integer N - size of the array, the second line of input contains an
array of elements of the array.
Output Format
Print the frequencies of zeroes, positive elements and negative elements.
Constraints
1 <= N <= 104
-103 <= arr[i] <= 103
Example
Input
10
120 0 -9 89 68 -982 91 -54 -12 -139
Output
145
Explanation
Self Explanatory

Max Altitude
Imagine a pilot starting the flight from the ground and flying over a series of different points at
different heights. You are given an array, where A[i] represents heights.
Currently, if the pilot is at altitude X at ith point, and if he wants to reach (i+1)th point, his altitude will
become X+A[i].
The pilot starts at altitude 0 and wants to find the highest point he can reach during the entire
journey. Your task is to print the highest altitude the pilot reaches.
Input Format
The first line of input contains an integer N. The second line of input contains N space-separated
integers.
Output Format
Print the highest altitude the pilot can reach.
Constraints
1 <= N <= 1000
-1000 <= A[i] <= 1000
Example
Input
5
-5 1 5 0 -7
Output
1
Explanation
When the pilot started at point 0 his altitude was -5, when he moved to point 1 his altitude became
(-5 + 1 = -4), at point 2 his altitude became(-4 + 5 = 1), at point 3
his became altitude remains(1 + 0 = 1), and at point 4 his altitude became (1 + -7 = -6). The
maximum altitude that he reached in his journey was 1.

Reverse Array
Print the array in reverse order.
Note:
Try solving this using recursion. Do not use any inbuilt functions / libraries for your main logic.
Input Format
The first line of input contains N - the size of the array and the second line contains the elements of
the array.
Output Format
Print the given array in reverse order.
Constraints
1 <= N <= 100
0 <= ar[i] <= 1000
Example
Input
5
2 19 8 15 4
Output
4 15 8 19 2
Explanation
Self Explanatory

Odd and Even Sum

Given an array of size N. Print the sum of odd and even numbers separated by a space.
Input Format
The first line of input contains N - the size of the array and the second line contains elements of the
array.
Output Format
Print the sum of odd elements followed by the sum of even elements.
Constraints
1 <= N <= 103
1 <= ar[i] <= 106
Example
Input
5
46925
Output
14 12
Explanation
Self Explanatory

Left Sum and Right Sum

Given an array A of size N. Construct an array B, such that B[i] is calculated as follows:

● Find leftSum => sum of elements to the left of index i in array A; if none, use 0.
● Find rightSum => sum of elements to the right of index i in array A; if none, use 0.
● B[i] = | leftSum - rightSum |

Your task is to simply print the B array.

Input Format
The first line of input contains the N - size of the array. The next line contains N integers - the
elements of array A.
Output Format
Print the elements of the B array separated by space.
Constraints
1 <= N <= 100
0 <= arr[i] <= 100000
Example
Input
3
677
Output
14 1 13
Explanation
At index 0:
LeftSum = 0, RightSum = 14
B[0] = | LeftSum - RightSum | = 14.
At index 1:
LeftSum = 6, RightSum = 7
B[1] = | LeftSum - RightSum | = 1.
At index 2:
LeftSum = 13, RightSum = 0
B[2] = | LeftSum - RightSum | = 13.
Mean Median Mode
Given a sorted array A, containing N integers. Calculate and print their Mean, Median and Mode.
1. For both the Mean and Median, display the values with precision up to two decimal places.
2. Print the first Mode that you encounter from the left hand side.
Input Format
First line of input contains integer N - the size of the array. Second line of input contains N integers -
elements of the array A.
Output Format
Print Mean, Median and Mode, separated by spaces.
Constraints
3 <= N <=105
1 <= A[i] <=105
Example
Input
8
12345566
Output
4.00 4.50 5
Explanation:
The Mean is 32 / 8 = 4.00 [rounded to 2 decimals]
The Median is (4+5) / 2 = 4.50
For the given example, {5, 6} represents the Mode of the array, we'll print 5 as it's the first Mode
encountered.

Finding Missing Number

Given an array of size N, it contains all the numbers from 1 to N+1 inclusive, except one
number. You have to find the missing number.
Input Format
First line of input contains T - number of test cases. Its followed by 2T lines, first line of each test
case contains N - size of the array and the next line contains N integers - the elements of the
array.
Constraints
1 <= T <= 500
1 <= N <= 10000
1 <= ar[i] <= N+1
Output Format
For each test case, print the missing number, separated by newline.
Sample Input 0
3
8
12795638
7
3581472
10
8 11 10 2 7 4 3 5 1 6

Sample Output 0
4
6
9

Explanation 0
Test Case 1:
Array Size=8: It should have all the elements between [1,9] exactly once, except one of them.
Hence 4 is the missing element.

Test Case 2:
Array Size=7: It should have all the elements between [1,8] exactly once, except one of them.
Hence 6 is the missing element.

Find Duplicate Number in Array

Find a duplicate element in the given array of integers. There will be only a single duplicate element
in the array.
Note:
Do not use any inbuilt functions / libraries for your main logic
Input Format
The first line of input contains the size of the array - N and the second line contains the elements of
the array, there will be only a single duplicate element in the array.
Output Format
Print the duplicate element from the given array.
Constraints
2 <= N <= 100
0 <= ar[i] <= 109
Example
Input
6
5 4 10 9 21 10
Output
10
Explanation
Self Explanatory
Count Set Bits
Given a number N, find the number of bits that are set to 1 in its binary representation.
Input Format
First line of input contains T - the number of test cases. It is followed by T lines, each line
containing a single integer N.
Constraints
1 <= T <= 104
0 <= N <= 1018
Output Format
For each test case, print the number of bits set to 1 in the binary representation of N, separated
by a new line.
Sample Input 0
3
4
15
10

Sample Output 0
1
4
2

Explanation 0
Test-Case 1:
The binary representation of 4 is 100. The number of 1's in the binary representation of 4 is 1.
Test-Case 2:
The binary representation of 15 is 1111. The number of 1's in the binary representation of 15 is
4.

Gauntlets
You have a collection of N gauntlets, each with a specific color represented by A[i]. Your goal is to
maximize the number of pairs by repeatedly pairing up gauntlets of the same color. Determine the
maximum number of pairs that can be formed.
Input Format
The first line of input contains an integer N. The second line of input contains an array of size N.
Output Format
For the given input, print a single line representing the answer.
Constraints
1 ≤ N ≤ 102
1 ≤ Ai ≤ 103
Example
Input
6
417414
Output
2
Explanation
You can do the operation twice as follows.

● Choose two gauntlets with the color 1 and pair them.

● Choose two gauntlets with the color 4 and pair them.

Then, you will be left with one sock with the color 4 and another with the color 7, so you can no
longer do the operation. There is no way to do the operation three or more times, so you should print
2.

First and Last

You are given an array A of size N, containing integers. Your task is to find the first and last
occurrences of a given element X in the array A and print them.
Input Format
The input consists of three lines. The first line contains a single integer N - the size of the array. The
second line contains N integers separated by a space, representing the elements of the array A. The
third line contains a single integer X.
Output Format
Print the indexes of the first and last occurrences separated by a space.
Constraints
1 <= N <= 103
1 <= A[i] <= 105
X ∈ A
Example
Input
10
1 3 5 7 9 11 3 13 15 3
3
Output
19
Explanation
Self Explanatory

Unique Elements
Print unique elements of the array in the same order as they appear in the input.
Note:
Do not use any inbuilt functions / libraries for your main logic.
Input Format
The first line of input contains the size of the array - N and the second line contains the elements of
the array.
Output Format
Print unique elements from the given array.
Constraints
1 <= N <= 100
0 <= ar[i] <= 109
Example
Input
7
5 4 10 9 21 4 10
Output
5 9 21
Explanation
Self Explanatory

Flip Bits
You are given two numbers A and B. Write a program to count the number of bits to be flipped
to change the number A to the number B. Flipping a bit of a number means changing a bit from
1 to 0 or vice versa.
Input Format
First line of input contains T - number of test cases. Each of the next T lines contains 2 integer A
and B, separated by space.
Constraints
1 <= T <= 100000
0 <= N <= 109
Output Format
For each test case, print the number of bit flips required to convert A to B, separated by new
line.
Sample Input 0
4
20 10
16 8
1 153
549 24

Sample Output 0
4
2
3
6

Explanation 0
Self Explanatory

Merge Two Sorted Arrays

You are given two sorted integer arrays A and B of size N and M respectively. Print the entire data in
sorted order.
Input Format
First line of input contains N - the size of the array. The second line contains N integers - the
elements of the first array. The third line contains M - the size of the second array. The fourth line
contains M integers - the elements of the second array.
Output Format
For each test case, print the entire data in sorted order with each element separated by a space, on a
new line.
Constraints
1 <= N <= 103
1 <= M <= 103
-105 <= A[i], B[i] <= 105
Example
Input
7
1 1 5 8 10 12 15
5
-1 2 4 5 7
Output
-1 1 1 2 4 5 5 7 8 10 12 15
Explanation
Self Explanatory

Interchange Diagonals
Given a matrix A of size NxN, interchange the diagonal elements from top to bottom and print the
resultant matrix.
Input Format
First line of input contains N - the size of the matrix. It is followed by N lines each containing N
integers - elements of the matrix.
Output Format
Print the matrix after interchanging the diagonals.
Constraints
1 <= N <= 100
1 <= A[i][j] <= 104
Example
Input
4
5678
13 14 15 16
1234
9 10 11 12
Output
8675
13 15 14 16
1324
12 10 11 9
Explanation
Self Explanatory

Print Array A Using B

Given two arrays, A and B, for each index 'i' in array B, print the corresponding element from array A if
B[i] is within the range of A, otherwise print -1.
Input Format
The first line of input contains an integer N - size of array A. The Second line of input contains
elements of array A. The Third line of input contains an integer M - size of array B. The Fourth line of
input contains elements of array B.
Output Format
Print the values of array A for every index 'i' in B i.e. A[B[i]] if B[i] is in the range, otherwise print -1.
Constraints
1 <= N <= 100
1 <= A[k] <= 1000
1 <= M <= 100
0 <= B[i] <= 1000
Example
Input
5
100 200 400 800 1000
6
4 2 0 6 10 0
Output
1000 400 100 -1 -1 100
Explanation
B[0] is 4, A[B[0]] => A[4] = 1000
B[1] is 2, A[B[1]] => A[2] = 400
B[2] is 0, A[B[2]] => A[0] = 100
B[3] is 6, size of array A is 5, any index >= 5 is an invalid index, so print -1.
B[4] is 10, size of array A is 5, any index >= 5 is an invalid index, so print -1.
B[5] is 0, A[B[5]] => A[0] = 100

Repeated Numbers
You are given an array of N elements. All elements of the array are in range 1 to N-2. All
elements occur once except two numbers, which occur twice. Your task is to find the two
repeating numbers.
Input Format
First line of input contains T - number of test cases. Its followed by 2T lines, the first line
contains N - the size of the array and second line contains the elements of the array.
Constraints
30 points
1 <= T <= 100
4 <= N <= 103
70 points
1 <= T <= 100
4 <= N <= 106
Output Format
Print the 2 repeated numbers in sorted manner, for each test case, separated by new line.
Sample Input 0
2
8
13234655
10
1528147436

Sample Output 0
35
14

Explanation 0
Self Explanatory

Max Min Partition

Given an array D of positive integers, your goal is to divide D into two separate arrays, E and F, under
the following conditions:

● Each element in array D must belong to either array E or array F

● Both arrays E and F are non-empty
● The objective is to minimize the partition's value, calculated as the absolute difference
between the maximum value of array E (denoted as max(E)) and the minimum value of array
F (denoted as min(F))
Print the resulting integer that represents the value of this partition.
Input Format
The first line of input contains N. The second line of input contains an array of size N.
Output Format
Print the minimized partition value.
Constraints
2 ≤ N ≤ 104
1 ≤ Di ≤ 109
Example
Input
6
7 1 14 16 30 4
Output
2
Explanation
We can partition the array D into E = [7, 1, 14, 4] and F = [16, 30].

● The maximum element of the array E is equal to 14.

● The minimum element of the array F is equal to 16.

The value of the partition is |14 - 16| = 2. It can be proven that 2 is the minimum value out of all the
partitions.

Non Divisible Subsets

Given an array of N unique numbers, find the maximum length subset that can be formed such
that sum of any 2 numbers in the subset is not a multiple of K.
Input Format
First line of input contains T - number of test cases. Its followed by 2T lines, the first line
contains 2 numbers N and K. Second line contains the elements of the array.
Constraints
10 points
1 <= T <= 100
1 <= N <= 10
1 <= K <= 50
0 <= arr[i] <= 102
30 points
1 <= T <= 100
1 <= N <= 102
1 <= K <= 102
0 <= arr[i] <= 105
60 points
1 <= T <= 100
1 <= N <= 104
1 <= K <= 105
0 <= arr[i] <= 105
Output Format
For each test case, print the maximun length of the subset, separated by new line.
Sample Input 0
1
43
1724

Sample Output 0
3

Explanation 0
Self Explanatory

Product Manufacturing
There are M manufacturers and each of them produce a range of products.
M1: [a1, b1]
M2: [a2, b2]
and so on...
Given a product ID, find how many manufacturers produce the given product.
Input Format
First line of input contains T - number of test cases. The first line of each test case contains an
integer M. Next M lines contains the ith manufacturer's range of product ids - starting(S) and
ending(E) (both inclusive). The next line contains Q - number of queries and the next Q lines
contains a single integer denoting the ID of the product.
Constraints
20 points
1 <= T <= 100
1 <= M, Q <= 1000
1 <= S <= E <= 104
1 <= ID <= 104
30 points
1 <= T <= 100
1 <= M, Q <= 10000
1 <= S <= E <= 104
1 <= ID <= 104
50 points
1 <= T <= 100
1 <= M, Q <= 10000
1 <= S <= E <= 109
1 <= ID <= 109
Output Format
For each test case, print the number of merchants producing the given product for each query,
separated by newline.
Sample Input 0
1
4
13
16
35
59
4
3
8
6
10

Sample Output 0
3
1
2
0

Explanation 0
Self Explanatory

Longest Contiguous 1's

Given an array of elements containing 0's and 1's. You have to find the length of longest contiguous
1's.
Input Format
First line of input contains N - size of the array. The next line contains the N integers of array A.
Output Format
Print the length of longest contiguous 1's.
Constraints
1 <= N <= 1000
Example
Input
10
1001011110
Output
4
Explanation
Self Explanatory
Non Decreasing Subsequences
You are given an array of integers of size N. Find the total number of non-decreasing
subsequences present in the array.
Input Format
First line of input contains T - number of test cases. Its followed by 2T lines, the first line
contains N - the size of the array. The second line contains the elements of the array.
Constraints
30 points
1 <= T <= 100
1 <= N <= 20
-105 <= A[i] <= 105
70 points
1 <= T <= 100
1 <= N <= 103
-105 <= A[i] <= 105
Output Format
For each test case, print the total number of non decreasing subsequences present in the array,
on a new line.
Since this number can be very large, print the result % 1000000007.
Sample Input 0
2
4
1825
10
9786574321

Sample Output 0
9
14

Explanation 0
Test-Case 1
The are 9 non decreasing subsequences:
{1}, {8}, {2}, {5}, {1,8}, {1,2}, {1,5}, {2,5} and {1,2,5}.
Test-Case 2
The are 14 non decreasing subsequences:
{9}, {7}, {8}, {6}, {5}, {7}, {4}, {3}, {2}, {1}, {7,8}, {7,7}, {6,7} and {5,7}.
Count the Triangles
You have a collection of N rods. Each rod has a unique mark on it. You are given the lengths of
each rod. You have to tell how many different triangles can be formed using these rods.
Input Format
First line of input contains T - number of test cases. Its followed by 2T lines, the first line
contains N - the number of rods. The second line contains the lengths of the rods.
Constraints
30 points
1 <= T <= 100
1 <= N <= 100
1 <= A[i] <= 100000
70 points
1 <= T <= 100
1 <= N <= 1000
1 <= A[i] <= 100000
Output Format
For each test case, print the total number of different triangles possible, separated by new line.
Sample Input 0
2
6
20 67 72 83 23 59
6
4 2 10 12 8 10

Sample Output 0
14
10

Explanation 0
Self Explanatory

Finding the Floor

Given an array, you have to find the floor of a number x. The floor of a number x is nothing but
the largest number in the array less than or equal to x.
Input Format
First line of input contains N - size of the array. The next line contains N integers, the elements
of the array. The next line contains Q - number of queries. Each of the next Q lines contains a
single integer X, for which you have to find the floor of X in the given array.
Constraints
30 points
1 <= N <= 105
1 <= Q <= 102
-108 <= ar[i] <= 108
70 points
1 <= N <= 105
1 <= Q <= 105
-108 <= ar[i] <= 108
Output Format
For each query, print the floor of X, separated by newline. If floor not found, print the value of
"INT_MIN"
Sample Input 0
6
-6 10 -1 20 15 5
5
-1
10
8
-10
-4

Sample Output 0
-1
10
5
-2147483648
-6

Explanation 0
Self Explanatory

Finding Frequency
Given an array, you have to find the frequency of a number x.
Input Format
First line of input contains N - size of the array. The next line contains N integers, the elements
of the array. The next line contains Q - number of queries. Each of the next Q lines contains a
single integer X, for which you have to find the frequency of X in the given array.
Constraints
30 points
1 <= N <= 105
1 <= Q <= 102
-108 <= ar[i] <= 108
70 points
1 <= N <= 105
1 <= Q <= 105
-108 <= ar[i] <= 108
Output Format
For each query, print the frequency of X, separated by newline.
Sample Input 0
9
-6 10 -1 20 -1 15 5 -1 15
5
-1
10
8
15
20

Sample Output 0
3
1
0
2
1

Explanation 0
Self Explanatory

Frequency Sort
You are given an array of integers. Sort them by frequency. See examples for more
clarifications.
Input Format
First line of input contains T - number of test cases. Its followed by 2T lines, the first line
contains N - the size of the array. The second line contains the elements of the array.
Constraints
1 <= T <= 100
1 <= N <= 10000
-1000 <= A[i] <= 1000
Output Format
For each test case, print the elements of the array sorted by frequency. In case 2 elements have
the same frequency, print the smaller element first.
Sample Input 0
2
6
4 -2 10 12 -8 4
8
176 -272 -272 -45 269 -327 -945 176

Sample Output 0
-8 -2 10 12 4 4
-945 -327 -45 269 -272 -272 176 176

Explanation 0
Self Explanatory

Sum of Pairs
Given an array of integers and a number K, check if there exist a pair of indices i,j s.t. a[i] + a[j]
= K and i!=j.
Input Format
First line of input contains T - number of test cases. Its followed by 2T lines, first line of each test
case contains N - size of the array and K, and the next line contains N integers - the elements of
the array.
Constraints
30 points
1 <= T <= 100
2 <= N <= 1000
70 points
1 <= T <= 300
2 <= N <= 10000
General Constraints
-108 <= K <= 108
-108 <= ar[i] <= 108
Output Format
For each test case, print "True" if such a pair exists, "False" otherwise, separated by newline.
Sample Input 0
3
5 -15
-30 15 20 10 -10
2 20
10 10
47
-4 0 10 -7

Sample Output 0
True
True
False
Explanation 0
Self Explanatory

Pair with Difference K

You are given an integer array and a positive integer K. You have to tell if there exists a pair of
integers in the given array such that ar[i]-ar[j]=K and i≠j.
Input Format
First line of input contains T - number of test cases. Its followed by 2T lines, the first line
contains N and K - the size of the array and the number K. The second line contains the
elements of the array.
Constraints
40 points
2 <= N <= 1000
60 points
2 <= N <= 100000
General Constraints
1 <= T <= 100
-105 <= ar[i], K <= 105
Output Format
For each test case, print "true" if the arrays contains such elements, false otherwise, separated
by new line.
Sample Input 0
2
5 60
1 20 40 100 80
10 11
12 45 52 65 21 645 234 14 575 112

Sample Output 0
true
false

Explanation 0
Self Explanatory

Triplet with Sum K

You are given an integer array and a number K. You have to tell if there exists i,j,k in the given
array such that ar[i]+ar[j]+ar[k]=K, i≠j≠k.
Input Format
First line of input contains T - number of test cases. Its followed by 2T lines, the first line
contains N and K - the size of the array and the number K. The second line contains the
elements of the array.
Constraints
30 points
1 <= T <= 100
3 <= N <= 100
70 points
1 <= T <= 100
3 <= N <= 1000
General
-100000 <= A[i] <= 100000
0 <= K <= 100000
Output Format
For each test case, print "true" if the arrays contains such elements, false otherwise, separated
by new line.
Sample Input 0
3
5 60
1 20 40 100 80
12 54
12 45 52 65 21 645 234 -100 14 575 -80 112
3 15
555

Sample Output 0
false
true
true

Explanation 0
Self Explanatory

Topic : Matrix
Image Flip
You are given an N x M binary matrix called "image". You need to perform the following operations
on the matrix (in order) and return the resulting image:
 1. Flip the image horizontally: This involves reversing the order of elements in each row of the
matrix. For example, [1,0,1,0,0,0] becomes [0,0,0,1,0,1]
2. Invert the image: This involves replacing 0s with 1s and 1s with 0s in the entire matrix. For
example, [0,0,0,1,0,1] becomes [1,1,1,0,1,0]

Input Format
Line of input contains N - number of rows and M - number of columns. The next N lines contains M
integers each denoting the elements of the matrix image.
Output Format
You have to print the resultant matrix image.
Constraints
1 <= N <=100
1 <= M <=100
Example
Input
22
10
01
Output
10
01
Explanation
Self Explanatory

Rotation of Matrix
Given a 2D square matrix, rotate the matrix by 90 degrees in a clockwise manner.
Note: Try to solve it by first scanning the matrix, then do an in-place rotation and then print the
rotated matrix.
Input Format
First line of input contains T - number of test cases. First line of each test case contains N - size
of the matrix [NxN]. Its followed by N lines each containing N integers - elements of the matrix.
Constraints
1 <= T <= 100
1 <= N <= 100
-100 <= ar[i][j] <= 100
Output Format
For each test case, print the rotated matrix, separated by newline.
Sample Input 0
4
1
1
2
12
43
3
123
894
765
5
-44 25 -52 69 -5
17 22 51 27 -44
-79 28 -78 1 -47
65 -77 -14 -21 -6
-96 43 -21 -20 90

Sample Output 0
Test Case #1:
1
Test Case #2:
41
32
Test Case #3:
781
692
543
Test Case #4:
-96 65 -79 17 -44
43 -77 28 22 25
-21 -14 -78 51 -52
-20 -21 1 27 69
90 -6 -47 -44 -5

Explanation 0
Self Explanatory

Local Max in Matrix

Given an integer matrix C with dimensions N × N. Construct a new integer matrix D of size (N - 2) ×
(N - 2) such that each element D[i][j] represents the maximum value within a 3 × 3 submatrix of C,
where the center of the submatrix is located at row i + 1 and column j + 1 in matrix C. We aim to
identify the highest value within every continuous 3 × 3 submatrix within C. Print the resulting matrix
D.
Input Format
The first line of input contains an integer N. For the next N lines, each line contains N elements
separated by space.
Output Format
Print the generated matrix.
Constraints
3 ≤ N ≤ 100
-1000 ≤ Cij ≤ 1000
Example
Input
4
12 9 8 40
5 20 2 6
8 14 6 30
6 2 25 2
Output
20 40
25 30
Explanation
Self Explanatory

The Hourglass sum:

Given a 2D Array, :
111000
010000
111000
000000
000000
000000

An hourglass in is a subset of values with indices falling in this pattern in 's graphical
representation:
abc
d
efg

There are hourglasses in . An hourglass sum is the sum of an hourglass' values. Calculate the
hourglass sum for every hourglass in , then print the maximum hourglass sum. The array will
always be .
Example
-9 -9 -9 1 1 1
0 -9 0 4 3 2
-9 -9 -9 1 2 3
0 0 8 660
0 0 0 -2 0 0
0 0 1 240
The hourglass sums are:
-63, -34, -9, 12,
-10, 0, 28, 23,
-27, -11, -2, 10,
9, 17, 25, 18

The highest hourglass sum is from the hourglass beginning at row , column :

043
1
866

hourglassSum has the following parameter(s):

● int arr[6][6]: an array of integers
Returns
● int: the maximum hourglass sum
Input Format
Each of the lines of inputs contains space-separated integers .
Constraints
● -9<=a[i][j]<=9
● 0<=i,j<=5
Output Format
Print the largest (maximum) hourglass sum found in .
Sample Input
111000
010000
111000
002440
000200
001240

Sample Output
19

Explanation
contains the following hourglasses:
The hourglass with the maximum sum () is:
244
2
124

Zero Row and Zero Column

Given a matrix A of size N x M. Elements of the matrix are either 0 or 1. If A[i][j] = 0, set all the
elements in the ith row and jth column to 0. Print the resultant matrix.
Input Format
The first line of input contains N, M - the size of the matrix A. It is followed by N lines each containing
M integers - elements of the matrix.
Output Format
Print the resultant matrix.
Constraints
1 <= N, M <= 100
A[i][j] ∈ {0,1}
Example
Input
45
01101
11111
11011
11111
Output
00000
01001
00000
01001
Explanation
Self Explanatory

Smart Square
Consider matrix of size 3x3. A matrix is said to be a smart matrix, if it consists of distinct
numbers from 1 to 9 and the sum of every row, column and diagonal is divisible by 5. Given a
matrix, find the minimum cost of converting it to a smart matrix by changing zero or more of its
digits. We can convert any digit a to b in the range of [1,9] at cost |a-b|.
Input Format
First line of input contains T - number of test cases. Its followed by 3T lines. Each test case
contains a 3x3 matrix with distinct numbers from 1 to 9.
Constraints
1 <= T <= 105
Output Format
For each test case, print the minimum cost to convert the matrix into a smart one, separated by
newline.
Sample Input 0
3
492
357
681
861
352
497
146
359
276

Sample Output 0
4
0
10

Explanation 0
Test Case 1
We can convert the given matrix to the following smart matrix which gives a minimum cost of 4.
492
357
861
Test Case 2
The given matrix is already a smart matrix.
Test Case 3
We can convert the given matrix to the following smart matrix which gives a minimum cost of 10.
127
659
384

Right Triangles
You are given a 2D boolean matrix grid.
Return an integer that is the number of right triangles that can be made with the 3 elements of
grid such that all of them have a value of 1.
Note:
● A collection of 3 elements of grid is a right triangle if one of its elements is in the same
row with another element and in the same column with the third element. The 3 elements
do not have to be next to each other.

Example 1:
0 1 0

0 1 1

0 1 0

0 1 0

0 1 1

0 1 0
Input: grid = [[0,1,0],[0,1,1],[0,1,0]]
Output: 2
Explanation:
There are two right triangles.
Example 2:
1 0 0 0

0 1 0 1

1 0 0 0
Input: grid = [[1,0,0,0],[0,1,0,1],[1,0,0,0]]
Output: 0
Explanation:
There are no right triangles.
Example 3:
1 0 1

1 0 0

1 0 0

1 0 1

1 0 0

1 0 0
Input: grid = [[1,0,1],[1,0,0],[1,0,0]]
Output: 2
Explanation:
There are two right triangles.

Constraints:
● 1 <= grid.length <= 1000
● 1 <= grid[i].length <= 1000
● 0 <= grid[i][j] <= 1

Topic : Strings:
Letter Coverage
Given a string, check if it contains all the letters of the alphabet.
Input Format
Input contains a string S, consisting of lowercase and uppercase characters.
Output Format
Print "Yes" if the string contains all the letters of the alphabet, and "No" otherwise.
Constraints
1 <= len(S) <= 100
Example
Input
askhtwsflkqwertYuioPasdfghjklZxcvbnm
Output
Yes
Explanation
Self Explanatory

String GCD
Given two strings, P and Q, your task is to find the largest common divisor string S, such that both P
and Q are divisible by S. In other words, there exists a string 'S' for which P = S + S + ... + S and Q = S
+ S + ... + S. If such a string S exists, output the largest possible S, otherwise, print -1.
Note: A string X is divisible by string Y if and only if X can be obtained by concatenating Y with itself
one or more times.
Input Format
The first line of input contains the string P. The Second line of input contains string Q.
Output Format
Print the largest string S.
Constraints
1 ≤ len(P), len(Q) ≤ 1000
'A' <= P[i],Q[i] <= 'Z'
Example
Input
ABABAB
ABAB
Output
AB
Explanation
Self Explanatory

Anagram Basic
Given two strings A and B consisting of lowercase characters. Print TRUE if A and B are anagrams
otherwise FALSE.
Input Format
The first line of input contains string A. The second line of input contains string B.
Output Format
Print "TRUE" if A and B are anagrams otherwise "FALSE".
Constraints
1 ≤ len(A), len(B) ≤ 104
Example
Input
smartinterviews
viewsintersmart
Output
TRUE
Explanation
Self Explanatory

Strings Rotation
Given two strings A and B of length N, check if string A is a rotation of string B.
Input Format
The first line of input contains N - the length of the strings. The second line contains A and B
separated by a space.
Output Format
Print "yes" if A is a rotation of B, otherwise "no".
Constraints
1 <= N <= 500
'a' <= A[i], B[i] <= 'z'
Example
Input
5
hello lohel
Output
yes
Explanation
Self Explanatory

Next Palindromic Number

Given a number N, find the least palindromic number K, such that K>N.
Input Format
First line of input contains T - number of test cases. Its followed by T lines, each contains a
single number N.
Constraints
30 points
1 <= T <= 104
1 <= N <= 104
70 points
1 <= T <= 105
1 <= N <= 109
Output Format
For each test case, print the least palindromic number K, such that K>N, separated by newline.
Sample Input 0
2
11
121
 Sample Output 0
22
131

Explanation 0

Self Explanatory

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".

Example 1:
Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Constraints:
● 1 <= strs.length <= 200
● 0 <= strs[i].length <= 200
● strs[i] consists of only lowercase English letters.

Strong Password
Find the minimum number of characters to add to a password (P) to ensure that P meets the
following criteria:
1. Contains at least 6 characters.
2. Contains at least one digit.
3. Contains at least one lowercase character.
4. Contains at least one uppercase character.
5. Contains at least one special character (!@#$%^&*()-+).
Input Format
First and only line of input contains a string P.
Output Format
Print the minimum number of characters that has to be added to P.
Constraints
1 <= len(P) <=50
P[i] ∈ {[a-z], [A-Z], [0-9], or [!@#$%^&*()-+ ]}.
Example
Input
He!!0
Output
1
Explanation
The given password P already contains one digit, one lowercase character, one uppercase character
and one special character. However, it should also contain at least 6 characters. So we need to add 1
character to ensure it meets all the criteria.

Longest Prefix Suffix

Given a string, compute the length of the longest proper prefix which is same as the suffix of the
given string.
Input Format
The input contains a string S, consisting of only lowercase characters.
Output Format
Print the length of the longest proper prefix which is the same as a suffix of the given string.
Constraints
1 <= len(S) <= 100
Example
Input
smartintsmart
Output
5
Explanation
Self Explanatory

Time of the Year

Given the number of seconds elapsed since epoch [01-01-1970 00:00:00 Thursday], you need
to find the current date, along with the day.
Note: Do not use any inbuilt functions/libraries for your main logic.
Input Format
First line of input contains T - number of test cases. Its followed by T lines, each line contains
the number of seconds elapsed since epoch.
Constraints
1 <= T <= 10000
0 <= S <= 109
Output Format
For each test case, print the date in DD-MMM-YYYY format, followed by the day, separated by
newline.
Sample Input 0
10
86399
86400
2592000
2678400
8639999
8640000
31535999
31536000
68169599
68169600

Sample Output 0
01-JAN-1970 Thursday
02-JAN-1970 Friday
31-JAN-1970 Saturday
01-FEB-1970 Sunday
10-APR-1970 Friday
11-APR-1970 Saturday
31-DEC-1970 Thursday
01-JAN-1971 Friday
28-FEB-1972 Monday
29-FEB-1972 Tuesday

Explanation 0
Self Explanatory

Long Pressed Keys

Observing your friend as they type their name on the keyboard, you notice that occasionally a key
might be held down longer, causing a character to appear multiple times. After examining the
sequence of typed characters, determine whether it's possible that the typed sequence corresponds
to your friend's name. Print true if typed_name corresponds to your friend_name, otherwise print
false.
Input Format
The first and only line of input contains two strings separated by space.
Output Format
Print true if typed_name corresponds to your friend_name, otherwise print false.
Constraints
1 ≤ len(friend_name), len(typed_name) ≤ 1000
Example
Input
raju rrraaajjjjjjjjjjjjjjuuuu
Output
true
Explanation
Self Explanatory

Check if All Characters Have Equal Number of Occurrences

Given a string s, return true if s is a good string, or false otherwise.

A string s is good if all the characters that appear in s have the same number of occurrences
(i.e., the same frequency).

Example 1:
Input: s = "abacbc"
Output: true
Explanation: The characters that appear in s are 'a', 'b', and 'c'. All characters occur 2 times in s.

Example 2:
Input: s = "aaabb"
Output: false
Explanation: The characters that appear in s are 'a' and 'b'.
'a' occurs 3 times while 'b' occurs 2 times, which is not the same number of times.

Constraints:
● 1 <= s.length <= 1000
● s consists of lowercase English letters.

Printing Balanced Paranthesis

Write a program to generate all possible strings with balanced parentheses having N pairs of
curly braces.
Input Format
First line of input contains T - number of test cases. Its followed by T lines, each contains a
single integer N.
Constraints
1 <= T <= 12
1 <= N <= 12
Output Format
For each test case, print each combinational pair of balanced paranthesis of length N in a
lexicographical order along with the test case number, separated by newline.
Sample Input 0
2
3
2

Sample Output 0
Test Case #1:
{{{}}}
{{}{}}
{{}}{}
{}{{}}
{}{}{}
Test Case #2:
{{}}
{}{}

Explanation 0
Self Explanatory

Interleavings
Given 2 strings A and B, print all the interleavings of the 2 strings. An interleaved string of given
two strings preserves the order of characters in individual strings and uses all the characters of
both the strings. For simplicity, you can assume that the strings have unique characters.
Input Format
First line of input contains T - number of test cases. It is followed by T lines, each containing 2
space separated strings A and B.
Constraints
1 <= T <= 100
'a' <= A[i], B[i] <= 'z'
1 <= len(A), len(B) <= 10
Output Format
For each test case, print the test case number, followed by the interleavings of the 2 strings in a
sorted order, separated by newline.
Sample Input 0
2
nkb gl
bn zh

Sample Output 0
Case #1:
glnkb
gnkbl
gnklb
gnlkb
ngkbl
ngklb
nglkb
nkbgl
nkgbl
nkglb
Case #2:
bnzh
bzhn
bznh
zbhn
zbnh
zhbn

Explanation 0
Self Explanatory

Topic : Sorting:

Bubble Sort Adhoc

Implement Bubble Sort and print the total number of swaps involved to sort the array.
Input Format
First line of input contains T - number of test cases. Its followed by 2T lines. First line of each
test case contains N - size of the array. The next line contains N integers - elements of the array.
Constraints
1 <= T <= 100
1 <= N <= 100
-1000 <= ar[i] <= 1000
Output Format
For each test case, print the total number of swaps, separated by new line.
Sample Input 0
4
8
176 -272 -272 -45 269 -327 -945 176
2
-274 161
7
274 204 -161 481 -606 -767 -351
2
154 -109

Sample Output 0
15
0
16
1

Explanation 0
Self Explanatory

Selection Sort Adhoc

Implement Selection Sort and print the index which gets swapped at each step.
Input Format
First line of input contains T - number of test cases. Its followed by 2T lines. First line of each
test case contains N - size of the array. The next line contains N integers - elements of the array.
Constraints
1 <= T <= 100
2 <= N <= 100
-1000 <= ar[i] <= 1000

Output Format
For each test case, print the index which gets swapped at each step, separated by space.
Separate the output of different tests by newline.
Sample Input 0
6
8
176 -272 -272 -45 269 -327 -945 176
2
-274 161
7
274 204 -161 481 -606 -767 -351
2
154 -109
4
5315
4
40 10 20 40

Sample Output 0
4043121
1
301221
0
001
000

Explanation 0
Self Explanatory

Insertion Sort Adhoc

Implement Insertion Sort and print the index at which the ith element gets inserted [i>=1].
Input Format
First line of input contains T - number of test cases. Its followed by 2T lines. First line of each
test case contains N - size of the array. The next line contains N integers - elements of the array.
Constraints
1 <= T <= 100
2 <= N <= 100
-1000 <= ar[i] <= 1000
Output Format
For each test case, print the index at which the ith element gets inserted [i>=1], separated by
space. Separate the output of different tests by newline.
Sample Input 0
4
8
176 -272 -272 -45 269 -327 -945 176
2
-274 161
7
274 204 -161 481 -606 -767 -351
2
154 -109

Sample Output 0
0124006
1
003002
0

Explanation 0
Self Explanatory

Topic : Searching:
Linear Search
Given an array of integers, search a given key in the array using linear search.
Note: Do not use any inbuilt functions / libraries for your main logic.
Input Format
The first line of input contains two integers N and K. N is the size of the array and K is the key. The
second line contains the elements of the array.
Output Format
If the key is found, print the index of the array, otherwise print -1.
Constraints
1 <= N <= 102
0 <= ar[i] <= 109
Example
Input
5 15
-2 -19 8 15 4
Output
3
Explanation
Self Explanatory

Sqrt(x)
Given a non-negative integer x, return the square root of x rounded down to the nearest integer.
The returned integer should be non-negative as well.
You must not use any built-in exponent function or operator.
● For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Example 1:
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.
Example 2:
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest
integer, 2 is returned.

Constraints:
● 0 <= x <= 231 - 1