Feeling tired!zzzzZz!!!
Updates from January, 2017 Toggle Comment Threads  Keyboard Shortcuts

loctv
Advertisements 
loctv
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^10Example:
Input:
4
17
43
15
16Output:
17
34
51
Not PossibleMy approach: (it might be not an elegant, efficient solution, but it works).
Generate all permutations of number n, then check each permutation for 17divisibility.
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)

loctv
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 topleft cell and ending at bottomright 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<=10Example:
Input:
1
3 4
a a a b b a a a a b b aOutput:
3Approach: 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 topleft 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)1i]: 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
Advertisements
Reply