• #### 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