Updates from January, 2017 Toggle Comment Threads | Keyboard Shortcuts

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

    Feeling tired!zzzzZz!!!

    Advertisements
     
  • loctv 11:22 pm on January 23, 2017 Permalink | Reply
    Tags: ,   

    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)

     
  • loctv 2:11 am on January 23, 2017 Permalink | Reply
    Tags: ,   

    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:

    print-all-paths-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:

    PrintAllPaths.png

    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