## Problem: Partition a number into two divisible parts

*Difficulty: Easy
Given a number (as string) and two integers a and b, divide the string in two non-empty parts such that the first part is divisible by a and second part is divisible by b. If string can not be divided into two non-empty parts, output “-1”, else print the two parts.

Input:

The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consists of single line containing 3 space seperated number denoting the respective values of  n, a and b.
Output:

For each test case output a single line containing the two space seperated non-empty parts else print -1.
Constraints:

1<=T<=100

1<=N<=106

1<=a,b<=N
Example:

Input:

3
1200 4 3
123 12 3
125 12 5

Ouput:

12 00
12 3
-1

Approach:
With Python in my pocket, I don’t think this problem deserves a medium-hard rank. The constraints is not hard, 10^6 means the length of the longest input number is just 6. The only thing to keep in mind is alway think of exceptions. Exceptions here are two case, number with length 1 and 2.

Implementation: Python2.7

```#code
def partitionToTwoPart(number, a, b):
number = str(number)
if len(number) < 2:
return -1
elif len(number) == 2:
first, second = number[0], number[1]
if int(first) % a == 0 and int(second) % b == 0:
return first, second
else:
return -1
else:
for i in range(1, len(number)):
first, second = number[:i], number[i:]
if int(first) % a == 0 and int(second) % b == 0:
return first, second
else:
return -1

def main():
t = input()
for _ in range(t):
n, a, b = map(int, raw_input().strip().split())
result = partitionToTwoPart(n, a, b)
if result != -1:
print result[0], result[1]
else:
print -1
if __name__ == '__main__':
main()
```
Advertisements

## Problem: Replace O’s with X’s

*Difficulty: Medium
Given a matrix of size NxM where every element is either ‘O’ or ‘X’, replace ‘O’ with ‘X’ if surrounded by ‘X’. A ‘O’ (or a set of ‘O’) is considered to be by surrounded by ‘X’ if there are ‘X’ at locations just below, just above, just left and just right of it.

Examples:

```Input: mat[N][M] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'O', 'X', 'X', 'O', 'X'},
{'X', 'X', 'X', 'O', 'O', 'X'},
{'O', 'X', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'O', 'X', 'O'},
{'O', 'O', 'X', 'O', 'O', 'O'},
};
Output: mat[N][M] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'X', 'X', 'X'},
{'O', 'X', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'O', 'X', 'O'},
{'O', 'O', 'X', 'O', 'O', 'O'},
};

```
```Input: mat[N][M] =  {{'X', 'X', 'X', 'X'}
{'X', 'O', 'X', 'X'}
{'X', 'O', 'O', 'X'}
{'X', 'O', 'X', 'X'}
{'X', 'X', 'O', 'O'}
};
Input: mat[N][M] =  {{'X', 'X', 'X', 'X'}
{'X', 'X', 'X', 'X'}
{'X', 'X', 'X', 'X'}
{'X', 'X', 'X', 'X'}
{'X', 'X', 'O', 'O'}
};```

Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains two integers N and M denoting the size of the matrix. Then in the next line are N*M space separated values of the matrix.

Output:
For each test case print the space separated values of the new matrix.

Constraints:
1<=T<=10
1<=mat[][]<=100
1<=n,m<=20

Example:
Input:

2
1 5
X O X O X
3 3
X X X X O X X X X
Output:
X O X O X
X X X X X X X X X

Approach:
The problem’s description is not clear enough. Just imagine that you’re playing Go, O is black and X is white, if a territory of black is surrounded by white, then all cells in that territory are replaced by white.
Problem’s difficulty is medium because the code is pretty long (I suppose)

Algorithm:
1. Get all O groups
2. From those groups, get groups that are surrounded by X
3. Replace O groups by X
Simple, isn’t it?

Implementation: Python 2.7

```def getAllOGroups(matrix):
markedO, groups = [], []
for i in range(len(matrix)):
for j in range(len(matrix[i])):
if not (i, j) in markedO and matrix[i][j] == 'O':
tempGroup = []
#get all adjacent O
getAllAdjacentOFrom(i, j, matrix, tempGroup, markedO)
groups.append(tempGroup)
return groups

def getAllAdjacentOFrom(i, j, matrix, tempGroup, markedO):
tempGroup.append((i, j))
markedO.append((i, j))
#up
i_up, j_up = i-1, j
if isInBound(i_up, j_up, matrix) and (i_up, j_up) not in markedO and matrix[i_up][j_up] == 'O':
getAllAdjacentOFrom(i_up, j_up, matrix, tempGroup, markedO)
#down
i_down, j_down = i+1, j
if isInBound(i_down, j_down, matrix) and (i_down, j_down) not in markedO and matrix[i_down][j_down] == 'O':
getAllAdjacentOFrom(i_down, j_down, matrix, tempGroup, markedO)
#left
i_left, j_left = i, j-1
if isInBound(i_left, j_left, matrix) and (i_left, j_left) not in markedO and matrix[i_left][j_left] == 'O':
getAllAdjacentOFrom(i_left, j_left, matrix, tempGroup, markedO)
#right
i_right, j_right = i, j+1
if isInBound(i_right, j_right, matrix) and (i_right, j_right) not in markedO and matrix[i_right][j_right] == 'O':
getAllAdjacentOFrom(i_right, j_right, matrix, tempGroup, markedO)

def getGroupsSurroundedByX(groups, matrix):
surroundedGroups = []
for groupO in groups:
if len([(i, j) for (i,j) in groupO if isSurroundedByX(i, j, matrix)]) == len(groupO):
surroundedGroups.append(groupO)
return surroundedGroups

def isSurroundedByX(i, j, matrix):
xUp = False
for _ in range(i-1, -1, -1):
if matrix[_][j] == 'X':
xUp = True
break
xDown = False
for _ in range(i+1, len(matrix)):
if matrix[_][j] == 'X':
xDown = True
break
xLeft = False
for _ in range(j-1, -1, -1):
if matrix[i][_] == 'X':
xLeft = True
break
xRight = False
for _ in range(j+1, len(matrix[0])):
if matrix[i][_] == 'X':
xRight = True
break
return xUp == xDown == xLeft == xRight == True

def isInBound(i, j, matrix):
return i >= 0 and i < len(matrix) and j >= 0 and j < len(matrix[0])

def replaceOByX(surroundedGroups, matrix):
for group in surroundedGroups:
for (i, j) in group:
matrix[i][j] = 'X'

def printFormated(matrix):
for row in matrix:
for cell in row:
print cell,
print

def main():
t = input()
for _ in range(t):
n, m = map(int, raw_input().strip().split())
arr = raw_input().strip().split()
matrix = [arr[i:i+m] for i in range(0, len(arr), m)]
#get all O-groups
groups = getAllOGroups(matrix)
#get groups that are surrounded by X
surroundedGroups = getGroupsSurroundedByX(groups, matrix)
#replace O with X
replaceOByX(surroundedGroups, matrix)
printFormated(matrix)

if __name__ == '__main__':
main()

```

## Problem: Help a Thief!!!

*Difficulty: Basic

You have to help a thief to steal as many as GoldCoins as possible from a GoldMine. There he saw N Gold Boxes an each Gold Boxes consists of Ai Plates each plates consists of Aj Gold Coins, Each Box consist of plates with exactly same number of GoldCoins per plate. Your task is to print the maximum gold coins theif can steal.

Input:
First line consists of T test cases. Each test case consists of three lines.
First line of each test case consistss of an Integer nT denoting the number of plates theif can steal.
Second line of each test case consists of an Integer N denoting the number of Gold Boxes available in the gold mine.
Third line of each test case consists of 2*N spaced Integers Ai,Aj dentoning number of plates in each box and number of gold coins in each plates respectively.

Output:
Print the respective result in each line.

Constraints:
1<=T<=20
1<=nT,Ai<=20
1<=N<=20
1<=Aj<=100

Example:
Input:

1
3
3
1 3 2 2 3 1
Output:
7

Implementation: Python 2.7

```#code
def sortByGoldCoins(goldBoxes):
return sorted(goldBoxes, key=lambda goldBox: goldBox[1], reverse=True)

def helpThief(goldBoxes, platesCanSteal):
maxGoldCoins, i = 0, 0
while platesCanSteal > 0:
if platesCanSteal >= goldBoxes[i][0]:
maxGoldCoins += goldBoxes[i][1] * goldBoxes[i][0]
platesCanSteal -= goldBoxes[i][0]
i += 1
else:
maxGoldCoins += platesCanSteal * goldBoxes[i][0]
platesCanSteal = 0
return maxGoldCoins

def main():
t = input()
for _ in range(t):
nT = input()
N = input()
goldBoxes = map(int, raw_input().strip().split())
plates = [goldBoxes[i] for i in range(len(goldBoxes)) if i % 2 == 0]
goldCoins = [goldBoxes[i] for i in range(len(goldBoxes)) if i % 2 != 0]
goldBoxes = zip(plates, goldCoins)
goldBoxes = sortByGoldCoins(goldBoxes)
#print goldBoxes
print helpThief(goldBoxes, nT)

if __name__ == '__main__':
main()
```

## Problem: Tom and String

*Difficulty: Very Easy

Tom is a Geek, he has a following string Initial which consists of the following letters in the mentioned order:“abcdefghijklmnopqrstuvwxyz1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ”.

He also has various lists of strings, and now he wants to compute the Hash value of each list of strings.
So, the Hash is the summation of all the character values in the input:(currentIndex + (position of the character In the string initial) ). And then this hash is multiplied by the Number of strings in the list.

Let’s assume that the list of strings is: [“aA1”, “b”]. So, his answer would be:
a: 0 + 0 = 0.
A: 1 + 36 = 37.
1: 2 + 26 = 28.
b: 0 + 1 = 1

.So, 2 * (0 + 1 + 37 + 28) = 2 * (66) = 132.

Input:

The first line will contain number of test cases T. Then T Test cases follow. For every test case, on a single line, there will be N number of string s all of them separated by a space, denoting all the strings of that particular list of strings.

Output:

Print the required hash for each of the mentioned list of strings.

Constraints:

1 ≤ Test Cases ≤ 50
1 ≤ Length of a string ≤ 30
1 ≤ Number of strings in a list ≤ 20

Example:

Input
3
aA1 b
a b c d
aa BB cc DD
Output
132
24
640

Explanation:

For the First Test Case
(0 + 1 + 37 + 28) = 2 * (66) = 132

For the Second Test Case

a: 0 + 0 = 0
b: 0 + 1 = 1
c: 0 + 2 = 2
d: 0 + 3 = 3

.So, 4* (0 + 1 + 3 + 4) = 4 * (6) = 24

For the Third Test Case

a: 0 + 0 = 0
a: 1 + 0 = 1

B: 0 + 37 = 37
B: 1 + 37 = 38

c: 0 + 2 = 2
c: 1 + 2 = 3

D: 0 + 39 = 39
D: 1 + 39 = 40

So, 4* (0 + 1 + 37+ 38 + 2 + 3 + 39 + 40) = 4 * (160) = 640

Implementation: Python 2.7

```#code
def hashValOf(listStrings, initString="abcdefghijklmnopqrstuvwxyz1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ"):
hashVal = 0
for string in listStrings:
for index, c in enumerate(string):
hashVal += index + initString.find(string[index])
return hashVal*len(listStrings)

def main():
t = input()
for _ in range(t):
listStrings = raw_input().strip().split()
print hashValOf(listStrings)

if __name__ == '__main__':
main()

```

## Problem: Reverse Coding

*Difficulty: Easy
Sherlock Being tired with the usual coding rounds started growing his interest towards reverse coding when he won the event in his college symposium. He wondered if his friend has the brain to quickly identify the pattern and verify if his inputs are correct or not. From the example portion given below, where you will be given a number(n) and its output, Using this find the pattern. Your task is that from the pattern you identified above, You have to tell if for the given n whether the given m is the correct answer or not…

Input:
The first line consists of T, the number of test cases. then T lines follow. Each line consists of n and m.

Output:
For each n and m output 1 if m is the corresponsing input for the value of n and 0 otherwise.

Constraints:
1<=t<=50
0<=n<=1000
0<=m<=10^6

Example to identify the pattern :

Input                            Output

10                                 55

20                                 210

5                                   15

0                                    0

1                                    1

2                                    3

Example:
Input:
4
10 55
4 11
2  3
6 21

Output:
1
0
1
1

Hint:
Pattern here is : Sum of first n natural numbers
Sn = n*(n+1)/2

Implementation: Python 2.7

```#code
def isCorrect(n, m):
correctValue = (n*(n+1))//2
return m == correctValue

def main():
t = input()
for _ in range(t):
n, m = map(int, raw_input().strip().split())
print 1 if isCorrect(n, m) else 0

if __name__ == '__main__':
main()
```

## Problem: Flood Fill Algorithm

*Difficulty: Easy

Given a 2D screen, location of a pixel in the screen ie(x,y) and a color(K), your task is to replace color of the given pixel and all adjacent same colored pixels with the given color K.

Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains Two integers N and M denoting the size of the matrix. Then in the next line are N*M space separated values of the matrix. Then in the next line are three values x, y and K.

Output:
For each test case print the space separated values of the new matrix.

Constraints:
1<=T<=10
1<=M[][]<=100

Example:
Input:

2
3 4
0 1 1 0 1 1 1 1 0 1 2 3
0 1 5
2 2
1 1 1 1
0 1 8

Output:
0 5 5 0 5 5 5 5 0 5 2 3
8 8 8 8

Implementation: Python 2.7

```def floodFill(rootColor, visited, screen, replaceColor, x, y):
# set color of x,y on the screen
screen[x][y] = replaceColor
# mark them as visited
visited.append((x, y))
# get all 4 directions
# first I make a mistake, I get all 8 directions
# but in the end, it's wrong
all_directions = [(x-1, y), (x, y+1),
(x+1, y), (x, y-1)]
# filter those 4 directions
# only get which one is in screen, not yet visited and has rootColor
all_directions = filter(lambda coor: isInScreen(coor[0], coor[1], screen) and not (coor[0], coor[1]) in visited and screen[coor[0]][coor[1]] == rootColor , all_directions)
# recursive call for those all directions
for (next_x,next_y) in all_directions:
floodFill(rootColor, visited, screen, replaceColor, next_x, next_y)

# check if (x, y) is in screen (not out of bound)
def isInScreen(x, y, screen):
return x >= 0 and x < len(screen) and y >= 0 and y < len(screen[0])

def printScreen(screen):
for row in screen:
for col in row:
print col,
print

def main():
t = input()
for _ in range(t):
n, m = map(int, raw_input().strip().split())
arr = map(int, raw_input().strip().split())
x, y, replaceColor = map(int, raw_input().strip().split())
screen, visited = [], []
# convert list-like array to matrix (actually is a list of list)
for i in range(0, len(arr), m):
screen.append(arr[i:i+m])
rootColor = screen[x][y]
floodFill(rootColor, visited, screen, replaceColor, x, y)
printScreen(screen)

if __name__ == '__main__':
main()
```

## Problem: Sum of All Subarrays

*Difficulty: Medium

Given an array A with N elements , you need to find the sum all sub arrays of array A. Since the sum could be very large print the sum modulo (10^9+7).

Input :
The first line contains integer T, denoting number of test cases. The first line of each test case contains an integer N, denoting the number of elements.The second line of each test case contains N space separated integers denoting values of the array A.
Output :
Print the answer of each test case in a new line.

Constraints :
1<=T<=10
1<=N<=10^5

Example
Input :

2
3
1 2 3
2
1 3

Output :
20
8

*Approach 1:

Generate all sub arrays
This is O(n^3) complexity solution

Code: Python 2.7

```def sum_all_sub_arrs(arr):
if len(arr) == 1:
return arr[0]
elif len(arr) == 2:
return arr[0] + arr[1] + sum(arr)
elif len(arr) == 3:
return sum(arr)*2 + arr[0] + arr[1] + arr[1] + arr[2]
else:
sum_all = 0
for i in range(2, len(arr)):
for j in range(len(arr)):
#print arr[j:j+i]
sum_all += sum(arr[j:j+i])
if j+i == len(arr):
break
return sum_all + sum(arr)*2

if __name__ == '__main__':
t = input()
for _ in range(t):
n = input()
arr = map(int, raw_input().strip().split())
print sum_all_sub_arrs(arr) % (10**9+7)
```

It cant be applied to solve this problem, since if using C++, I can barely pass this problem with runtime nearly reach 5 seconds. (This is Python, so it’s impossible)

After 30 minutes working on papers, I figured out something’s interesting.
Example with input array’s length is odd
Array: 1 2 3 4 5
Sum of all sub-arrays:
1 + 2 + 3 + 4 + 5 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 1 + 2 + 3 + 2 + 3 + 4+ 3 + 4 + 5 + 1 + 2 + 3 + 4 + 2 + 3 + 4 + 5 + 1 + 2 + 3 +4 + 5 = 105
Here’s is the array and the number of times of each element in the equation above:
Array:              1 – 2 – 3 – 4 – 5
Frequency:     5 – 8 – 9 – 8 – 5
Example with input array’s length is even
Array: 1 2 3 4
Sum of all sub-arrays:
1 + 2 + 3 + 4 + 1 + 2 + 2 + 3 + 3 +4 + 1 +2 +3 + 2 + 3 + 4 + 1 +2 + 3 + 4 = 50
Array:           1 – 2 – 3 – 4
Frequency: 4 – 6 – 6 – 4
In general:
+ if length of input array is odd, and n is the length
Frequency: n –  prev+(n-2)  – prev+(n-4) – … – prev+1  – … – prev+(n-4)  – prev+(n-2) – n
+ if length of input array is even, and n is the length
Frequency: n – prev+(n-2) – prev+(n-4) – ….. – prev+(n-4) – prev+(n-2) – n

Code: Python 2.7

```def sum_all_sub_arrs(arr):
# input array contains only one element
if len(arr) == 1:
return arr[0]
# init steps
frequency = [0]*len(arr)
dif = len(arr)-2
# because frequency values are symmetric
# example: 4 6 6 4
#          3 4 3
#          etc
# we need to traverse only half first of the input array
# and work out the frequency of each value
for i in range(0, len(arr)//2 + 1 if len(arr) % 2 != 0 else len(arr)//2):
# first frequency = len(arr)
if i == 0:
frequency[i] = len(arr)
# then, each of next element is its previous cell plus difference
# and decrease the difference by 2
else:
frequency[i] += (frequency[i-1] + dif)
dif -= 2
# half left of frequency
for i in range(len(arr)//2+1 if len(arr) % 2 != 0 else len(arr)//2, len(arr)):
offset = len(arr) - i - 1
frequency[i] = frequency[offset]
return sum(x*y for (x,y) in zip(arr, frequency))

if __name__ == '__main__':
t = input()
mod = 10**9 + 7
for _ in range(t):
n = input()
arr = map(int, raw_input().strip().split())
print sum_all_sub_arrs(arr) % mod
```

Solution took: 94ms

• #### loctv 11:33 pm on January 23, 2017 Permalink | Reply

Feeling tired!zzzzZz!!!

## Problem: Largest Divisibility Test

*Difficulty: Medium

Babul’s favourite number is 17. He likes the numbers which are divisible by 17. This time what he does is that he takes a number N and tries to find the largest number which is divisible by 17, by rearranging the digits. As the number increases he gets puzzled with his own task. So you as a programmer have to help him to accomplish his task.

Note: If the number is not divisible by rearranging the digits, then print “Not Possible”. N may have leading zeros.

Input:
The first line of input contains an integer T denoting the no of test cases. Each of the next T lines contains the number N.

Output:
For each test case in a new line print the desired output.

Constraints:
1<=T<=100
1<=N<=10^10

Example:
Input:

4
17
43
15
16

Output:
17
34
51
Not Possible

My approach: (it might be not an elegant, efficient solution, but it works).

Generate all permutations of number n, then check each permutation for 17-divisibility.
If there is no number divisible by 17, return None, otherwise, return max of those numbers.

I dont consider my solution is not cheating. I use Python since it has an enormous  amount of packages that support problem solving.
**’Life is short, why haven’t you learned Python yet?’ 🙂

Implementation: Python 2.7

```import itertools

def largest_divisible_of(number):
"""
generate all permutations of a number and
check each permutation if it is divisible by 17
number: type string
return: None if there is no number divisible by 17,
otherwise, return max
"""
divisibles = list(''.join(x) for x in itertools.permutations(list(number)) if int(''.join(x)) % 17 == 0)
return None if len(divisibles) == 0 else max(divisibles)

if __name__ == '__main__':
t = input()
for _ in range(t):
n = raw_input().strip()
result = largest_divisible_of(n)
print result if result is not None else 'Not Possible'
```

Solution took: 3.112 seconds (still < 5s)

## Problem:

*Difficulty: Medium

Given a matrix containing lower alphabetical characters only, we need to count number of palindromic paths in given matrix. A path is defined as a sequence of cells starting from top-left cell and ending at bottom-right cell. We are allowed to move to right and down only from current cell.

Input:
The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consists of two lines.
First line of each test case consist of two space separated integers R and C, denoting the number of element in a row and column respectively.
Second line of each test case consists of R*C space separated chars denoting the elements in the matrix in row major order.

Output:
It should be single line output, Print the respective output in the respective line.

Constraints:
1<=T<=20
1<=R,C<=10

Example:
Input:

1
3 4
a a a b b a a a a b b a

Output:
3

Approach: Recursion

Source: Algorithms

Example:

As we can only move right or down, we need to keep track of when we reach the bottom or the right side. As soon as we reach those, we either go right straight to the destination or go down straight to the destination (As described in the photo above). So the recursion will have two recursion calls and two base cases. One recursion call to move right (increase col), and one to move down (increase row), one base case when we reach bottom and one when we reach right side. In my opinion, it’s easier to implement problem solving in Python, so let’s get started.
But before we jump in to the code, here’s the picture shows how the recursion works under the hood:

Implementation: Python 2.7

```def all_paths(matrix, row, col, path, paths):
"""
generate all possible paths from top-left to botrom right
by only moving right and down from current cell.
"""
# touch the bottom, go all the way right to destination
if row == len(matrix)-1:
for i in range(col, len(matrix[0])):
path += matrix[row][i]
paths.append(path)
return
# touch the right side, go all the way down to destination
if col == len(matrix[0])-1:
for i in range(row, len(matrix)):
path += matrix[i][col]
paths.append(path)
return
path += matrix[row][col]
# go right
all_paths(matrix, row+1, col, path, paths)
# and go down
all_paths(matrix, row, col+1, path, paths)

def is_palindrom(string):
bound = len(string) // 2
for i in range(bound):
if string[i] != string[len(string)-1-i]:
return False
return True

if __name__ == '__main__':
t = input()
for _ in range(t):
n, m = map(int, raw_input().strip().split())
line = raw_input().strip().split()
matrix = []
for i in range(0, len(line), m):
matrix.append(line[i:i+m])
all_possible_paths, count_palindroms = [], 0
all_paths(matrix, 0, 0, "", all_possible_paths)
for path in all_possible_paths:
if is_palindrom(path):
count_palindroms += 1
print count_palindroms

```

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel