## HackerRank: The Grid Search

### Problem

Given a 2D array of digits, try to find the occurrence of a given 2D pattern of digits. For example, consider the following 2D matrix:

1234567890
0987654321
1111111111
1111111111
2222222222


Assume we need to look for the following 2D pattern:

876543
111111
111111


If we scan through the original array, we observe that the 2D pattern begins at the second row and the third column of the larger grid (the 8 in the second row and third column of the larger grid is the top-left corner of the pattern we are searching for).

So, a 2D pattern of P digits is said to be present in a larger grid G, if the latter contains a contiguous, rectangular 2D grid of digits matching with the pattern P, similar to the example shown above.

Input Format
The first line contains an integer, T, which is the number of test cases. T test cases follow, each having a structure as described below:
The first line contains two space-separated integers, R and C, indicating the number of rows and columns in the grid G, respectively.
This is followed by R lines, each with a string of C digits, which represent the grid G.
The following line contains two space-separated integers, r and c, indicating the number of rows and columns in the pattern grid P.
This is followed by r lines, each with a string of c digits, which represent the pattern P.

Constraints
1T5
1R,r,C,c1000
1rR
1cC

Test Case Generation
Each individual test case has been generated by first specifying the size (R and C) of the large 2D matrix, and then randomly generating the digits in it. A limited number of digits in the larger matrix may be changed by the problem setter (no more than 5% of the total number of digits in the matrix). So the larger 2D matrix is almost-random. The pattern matrix has been manually-curated by the problem setter.

Output Format
Display ‘YES’ or ‘NO’, depending on whether (or not) you find that the larger grid GG contains the rectangular pattern PP. The evaluation will be case sensitive.

Sample Input

2
10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530
15 15
400453592126560
114213133098692
474386082879648
522356951189169
887109450487496
252802633388782
502771484966748
075975207693780
511799789562806
404007454272504
549043809916080
962410809534811
445893523733475
768705303214174
650629270887160
2 2
99
99


Sample Output

YES
NO


Explanation

The first test in the input file is:

10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530


As one may see, the given 2D grid is indeed present in the larger grid, as marked in bold below.

7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137


The second test in the input file is:

15 15
400453592126560
114213133098692
474386082879648
522356951189169
887109450487496
252802633388782
502771484966748
075975207693780
511799789562806
404007454272504
549043809916080
962410809534811
445893523733475
768705303214174
650629270887160
2 2
99
99


The search pattern is:

99
99


This cannot be found in the larger grid.

Solution

## HackerRank: Chocolate Feast

### Problem

Little Bob loves chocolate, and he goes to a store with $N$N in his pocket. The price of each chocolate is $C$C. The store offers a discount: for every MM wrappers he gives to the store, he gets one chocolate for free. How many chocolates does Bob get to eat?

Input Format:
The first line contains the number of test cases, TT.
TT lines follow, each of which contains three integers, NN, CC, and MM.

Output Format:
Print the total number of chocolates Bob eats.

Constraints:
1T10001≤T≤1000
2N1052≤N≤105
1CN1≤C≤N
2MN2≤M≤N

Sample input

3
10 2 5
12 4 4
6 2 2


Sample Output

6
3
5


Explanation
In the first case, he can buy 5 chocolates with $10 and exchange the 5 wrappers to get one more chocolate. Thus, the total number of chocolates is 6. In the second case, he can buy 3 chocolates for$12. However, it takes 4 wrappers to get one more chocolate. He can’t avail the offer and hence the total number of chocolates remains 3.

In the third case, he can buy 3 chocolates for \$6. Now he can exchange 2 of the 3 wrappers and get 1 additional piece of chocolate. Now he can use his 1 unused wrapper and the 1 wrapper of the new piece of chocolate to get one more piece of chocolate. So the total is 5.

## HackerRank: Encryption

### Problem

An English text needs to be encrypted using the following encryption scheme.
First, the spaces are removed from the text. Let LL be the length of this text.
Then, characters are written into a grid, whose rows and columns have the following constraints:

• LrowscolumnL⌊L⌋≤rows≤column≤⌈L⌉, where x⌊x⌋ is floor function and x⌈x⌉ is ceil function

For example, the sentence if man was meant to stay on the ground god would have given us roots after removing spaces is 5454 characters long, so it is written in the form of a grid with 7 rows and 8 columns.

ifmanwas
meanttos
tayonthe
groundgo
dwouldha
vegivenu
sroots

• Ensure that rows×columnsLrows×columns≥L
• If multiple grids satisfy the above conditions, choose the one with the minimum area, i.e. rows×columnsrows×columns.

The encoded message is obtained by displaying the characters in a column, inserting a space, and then displaying the next column and inserting a space, and so on. For example, the encoded message for the above rectangle is:

imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohghn sseoau

You will be given a message in English with no spaces between the words. The maximum message length can be8181 characters. Print the encoded message.

Here are some more examples:

Sample Input:

haveaniceday


Sample Output:

hae and via ecy


Sample Input:

feedthedog


Sample Output:

fto ehg ee dd


Sample Input:

chillout


Sample Output:

clu hlt io

## HackerRank: Caesar Cipher

### Problem

Julius Caesar protected his confidential information by encrypting it in a cipher. Caesar’s cipher rotated every letter in a string by a fixed number, K, making it unreadable by his enemies. Given a string, S, and a number, K, encrypt S and print the resulting string.

Note: The cipher only encrypts letters; symbols, such as -, remain non-encrypted.

Input Format

The first line contains an integer, N, which is the length of the non-encrypted string.
The second line contains the non-encrypted string, S.
The third line contains the integer encryption key, K, which is the number of letters to rotate.

Constraints
1N100
0K100
S is a valid ASCII string and doesn’t contain any spaces.

Output Format

For each test case, print the encoded string.

Sample Input

11
middle-Outz
2


Sample Output

okffng-Qwvb


Explanation

Each non-encrypted letter is replaced with the letter occurring K spaces after it when listed alphabetically. Think of the alphabet as being both case-sensitive and circular; if K rotates past the end of the alphabet, it loops back to the beginning (i.e.: the letter after z is a, and the letter after is A).

Selected Examples:
m (ASCII 109) becomes o (ASCII 111).
i (ASCII 105) becomes k (ASCII 107).
remains the same, as symbols are not encoded.
O (ASCII 79) becomes Q (ASCII 81).
z (ASCII 122) becomes b (ASCII 98); because z is the last letter of the alphabet,
a (ASCII 97) is the next letter after it in lower-case rotation.

## HackerRank: [Algo] Matrix Rotation

### Problem

You are given a 2-D matrix, a, of dimension M x N and a positive integer R. You have to rotate the matrix R times and print the resultant matrix. Rotation should be in anti-clockwise direction.

Rotation of a 4 x 5 matrix is represented by the following figure. Note that in one rotation, you have to shift elements by one step only (refer sample tests for more clarity).

It is guaranteed that the minimum of M and N will be even.

Input Format
First line contains three space separated integers, M, N and R, where M is the number of rows, N is number of columns in matrix, and R is the number of times the matrix has to be rotated.
Then M lines follow, where each line contains N space separated positive integers. These M lines represent the matrix.

Output Format
Print the rotated matrix.

Constraints
2 <= M, N <= 300
1 <= R <= 109
min(M, N) % 2 == 0
1 <= aij <= 108, where i[1..M] & j[1..N]

Sample Input #00

4 4 1
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16


Sample Output #00

2 3 4 8
1 7 11 12
5 6 10 16
9 13 14 15


Sample Input #01

4 4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16


Sample Output #01

3 4 8 12
2 11 10 16
1 7 6 15
5 9 13 14


Sample Input #02

5 4 7
1 2 3 4
7 8 9 10
13 14 15 16
19 20 21 22
25 26 27 28


Sample Output #02

28 27 26 25
22 9 15 19
16 8 21 13
10 14 20 7
4 3 2 1


Sample Input #03

2 2 3
1 1
1 1


Sample Output #03

1 1
1 1


Explanation
Sample Case #00: Here is an illustration of what happens when the matrix is rotated once.

 1  2  3  4      2  3  4  8
5  6  7  8      1  7 11 12
9 10 11 12  ->  5  6 10 16
13 14 15 16      9 13 14 15


Sample Case #01: Here is what happens when to the matrix after two rotations.

 1  2  3  4      2  3  4  8      3  4  8 12
5  6  7  8      1  7 11 12      2 11 10 16
9 10 11 12  ->  5  6 10 16  ->  1  7  6 15
13 14 15 16      9 13 14 15      5  9 13 14


Sample Case #02: Following are the intermediate states.

1  2  3  4      2  3  4 10    3  4 10 16    4 10 16 22
7  8  9 10      1  9 15 16    2 15 21 22    3 21 20 28
13 14 15 16 ->  7  8 21 22 -> 1  9 20 28 -> 2 15 14 27 ->
19 20 21 22    13 14 20 28    7  8 14 27    1  9  8 26
25 26 27 28    19 25 26 27    13 19 25 26   7 13 19 25

10 16 22 28    16 22 28 27    22 28 27 26    28 27 26 25
4 20 14 27    10 14  8 26    16  8  9 25    22  9 15 19
3 21  8 26 ->  4 20  9 25 -> 10 14 15 19 -> 16  8 21 13
2 15  9 25     3 21 15 19     4 20 21 13    10 14 20  7
1  7 13 19     2  1  7 13     3  2  1  7     4  3  2  1


Sample Case #03: As all elements are same, any rotation will reflect the same matrix.

## HackerRank: Cut the sticks

### Problem

You are given N sticks, where the length of each stick is a positive integer. A cut operation is performed on the sticks such that all of them are reduced by the length of the smallest stick.

Suppose we have six sticks of the following lengths:
5 4 4 2 2 8

Then, in one cut operation we make a cut of length 2 from each of the six sticks. For the next cut operation four sticks are left (of non-zero length), whose lengths are the following:
3 2 2 6

The above step is repeated until no sticks are left.

Given the length of N sticks, print the number of sticks that are left before each subsequent cut operations.

Note: For each cut operation, you have to recalcuate the length of smallest sticks (excluding zero-length sticks).

Input Format
The first line contains a single integer N.
The next line contains N integers: a0, a1,…aN-1 separated by space, where ai represents the length of ith stick.

Output Format
For each operation, print the number of sticks that are cut, on separate lines.

Constraints
1 ≤ N ≤ 1000
1 ≤ ai ≤ 1000

Sample Input #00

6
5 4 4 2 2 8


Sample Output #00

6
4
2
1


Sample Input #01

8
1 2 3 4 3 3 2 1


Sample Output #01

8
6
4
1


Explanation

Sample Case #00 :

sticks-length        length-of-cut   sticks-cut
5 4 4 2 2 8             2               6
3 2 2 _ _ 6             2               4
1 _ _ _ _ 4             1               2
_ _ _ _ _ 3             3               1
_ _ _ _ _ _           DONE            DONE


Sample Case #01

sticks-length         length-of-cut   sticks-cut
1 2 3 4 3 3 2 1         1               8
_ 1 2 3 2 2 1 _         1               6
_ _ 1 2 1 1 _ _         1               4
_ _ _ 1 _ _ _ _         1               1
_ _ _ _ _ _ _ _       DONE            DONE

## HackerRank: Service Lane

### Problem

Calvin is driving his favorite vehicle on the 101 freeway. He notices that the check engine light of his vehicle is on, and he wants to service it immediately to avoid any risks. Luckily, a service lane runs parallel to the highway. The length of the service lane is N units. The service lane consists of N segments of equal length and different width.

Calvin can enter to and exit from any segment. Let’s call the entry segment as index i and the exit segment as index j. Assume that the exit segment lies after the entry segment (ij) and 0i0≤i. Calvin has to pass through all segments from index i to index j (both inclusive).

Calvin has three types of vehicles – bike, car, and truck – represented by 1, 2 and 3, respectively. These numbers also denote the width of the vehicle.

You are given an array width of length N, where width[krepresents the width of the kth segment of the service lane. It is guaranteed that while servicing he can pass through at most 1000 segments, including the entry and exit segments.

• If width[k]=1, only the bike can pass through the kth segment.
• If width[k]=2, the bike and the car can pass through the kth segment.
• If width[k]=3, all three vehicles can pass through the kth segment.

Given the entry and exit point of Calvin’s vehicle in the service lane, output the type of the largest vehicle which can pass through the service lane (including the entry and exit segments).

Input Format

The first line of input contains two integers, N and T, where N denotes the length of the freeway and T the number of test cases. The next line has N space-separated integers which represent the width array.

T test cases follow. Each test case contains two integers, i and j, where i is the index of the segment through which Calvin enters the service lane and j is the index of the lane segment through which he exits.

Constraints
2N100000
1T1000
0i<j<N
2ji+1min(N,1000)
1width[k]3,where 0k<N

Output Format

For each test case, print the number that represents the largest vehicle type that can pass through the service lane.

Note: Calvin has to pass through all segments from index i to index j (both inclusive).

Sample Input

8 5
2 3 1 2 3 2 3 3
0 3
4 6
6 7
3 5
0 7


Sample Output

1
2
3
2
1


Explanation

Below is the representation of the lane:

   |HIGHWAY|Lane|    ->    Width

0: |       |--|            2
1: |       |---|           3
2: |       |-|             1
3: |       |--|            2
4: |       |---|           3
5: |       |--|            2
6: |       |---|           3
7: |       |---|           3

1. (0, 3): Because width[2] = 1, only the bike can pass through it.
2. (4, 6): Here the largest allowed vehicle which can pass through the 5th segment is the car and for the 4th and 6th segment it’s the truck. Hence the largest vehicle allowed in these segments is a car.
3. (6, 7): In this example, the vehicle enters at the 6th segment and exits at the 7th segment. Both segments allow even trucks to pass through them. Hence the answer is 3.
4. (3, 5): width[3] = width[5] = 2. While the 4th segment allows the truck, the 3rd and 5thallow up to a car. So 2 will be the answer here.
5. (0, 7): The bike is the only vehicle which can pass through the 2nd segment, which limits the strength of the whole lane to 1.

## HackerRank: BotClean Partially Observable

Problem Statement

The game Bot Clean took place in a fully observable environment, i.e., the state of every cell was visible to the bot at all times. Let us consider a variation of it where the environment is partially observable. The bot has the same actuators and sensors. But the sensors visibility is confined to its 8 adjacent cells.

Input Format
The first line contains two space separated integers which indicate the current position of the bot. The board is indexed using Matrix Convention

5 lines follow, representing the grid. Each cell in the grid is represented by any of the following 4 characters:
‘b’ (ascii value 98) indicates the bot’s current position,
‘d’ (ascii value 100) indicates a dirty cell,
‘-‘ (ascii value 45) indicates a clean cell in the grid, and
‘o’ (ascii value 111) indicates the cell that is currently not visible.

Output Format
Output is the action that is taken by the bot in the current step. It can either be any of the movements in 4 directions or the action of cleaning the cell in which it is currently located. Hence the output formats are LEFT, RIGHT, UP, DOWN or CLEAN.

Sample Input

0 0
b-ooo
-dooo
ooooo
ooooo
ooooo


Sample Output

RIGHT


Complete the function next_move that takes in 3 parameters: posr and posc denote the co-ordinates of the bot’s current position, and board denotes the board state, and print the bot’s next move.

Scoring
The goal is to clean all the dirty cells in as few moves as possible. Your score is (200 – #bot moves)/25. All bots in this challenge will be given the same input. CLEAN is also considered a move.

Solution:

Solution tester posted alongside the program for users to test their input as well.

## HackerRank: Sherlock and Squares

### Problem Statement

Watson gives two integers (and B) to Sherlock and asks if he can count the number of square integers between and (both inclusive).

Note: A square integer is an integer which is the square of any integer. For example, 1, 4, 9, and 16 are some of the square integers as they are squares of 1, 2, 3, and 4, respectively.

Input Format
The first line contains T, the number of test cases. test cases follow, each in a new line.
Each test case contains two space-separated integers denoting and B.

Output Format
For each test case, print the required answer in a new line.

Constraints
1T100
1AB10^9

Sample Input

2
3 9
17 24


Sample output

2
0


Explanation
Test Case #00: In range [3,9], 4 and 9 are the two square numbers.
Test Case #01: In range [17,24], there are no square numbers.

## HackerRank: Continuous Sequence Sum Test

### Question:

Given a sequence of positive integers A and an integer T, return whether there is a continuous sequence of A that sums up to exactly T
Example

[23, 5, 4, 7, 2, 11], 20. Return True because 7 + 2 + 11 = 20
[1, 3, 5, 23, 2], 8. Return True because 3 + 5 = 8
[1, 3, 5, 23, 2], 7 Return False because no sequence in this array adds up to 7