Updates from September, 2016 Toggle Comment Threads | Keyboard Shortcuts

  • loctv 10:40 am on September 14, 2016 Permalink | Reply
    Tags: ,   

    Problem: Possible groups 

    Given an unsorted integer (positive values only) array of size ‘n’, we can form a group of two or three only, the group should be such that the sum of all elements in that group is a multiple of 3. Count all possible number of groups that can be generated in this way.

    Input: arr[] = {3, 6, 7, 2, 9}
    Output: 8
    Groups are {3,6}, {3,9}, {9,6},
               {7,2}, {3, 6,9}, 
               {3, 7, 2}, {7, 2, 6}, 
               {7, 2, 9}
    

    Input:

    The first line of input contains an integer T denoting the number of test cases.
    The first line of each test case is N, where N is the size of array.
    The second line of each test case contains N elements of input array.

    Output:

    Print number of all possible group.

    Constraints:

    1 ≤ T ≤ 50
    1 ≤ N ≤ 80
    1 ≤ arr[i] ≤ 100

    Example:

    Input
    2
    5
    3 6 7 2 9
    4
    2 1 3 4

    Output
    8
    4

    Implementation: Python 2.7

    from itertools import *
    def possible_groups(l):
        groups_2 = [x for x in list(combinations(l, 2)) if sum(x)%3==0]
        groups_3 = [x for x in list(combinations(l, 3)) if sum(x)%3==0]
        return len(groups_2) + len(groups_3)
    
    if __name__ == '__main__':
        t = input()
        for _ in range(t):
            n = input()
            l = map(int, raw_input().split())
            print possible_groups(l)
    

     

    Advertisements
     
  • loctv 10:08 am on September 14, 2016 Permalink | Reply
    Tags: ,   

    Problem: Minimum Notes Required 

    John works in RS Software and today he is supposed to receive his salary. RS Software pays its employees in cash. However, John’s wallet has one drawback. His wallet can contain no more than M notes or coins. Taking his case into consideration, his boss pays him his salary by the minimum notes possible. However John may have to leave out some money. Tell John how much money will he have to lose.

    Note: The values of notes or coins available are 1000, 500, 100, 50, 20, 10, 5, 2 and 1.

    Input:
    The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of a single line containing two space separated integers N and M denoting John’s salary and the maximum number of notes his wallet can hold, respectively.

    Output:

    Corresponding to each test case, print the desired output in a single line.

    Constraints:
    1<=T<=20
    1<=N<=100000
    1<=M<=1000

    Example:
    Input:
    3
    1712 4
    1023 2
    2341 3

    Output:
    12
    3
    241

    Implement: Python 2.7

    coins = [1000, 500, 100, 50, 20, 10, 5, 2, 1]
    def get_remain(n, m, i):
        if m == 0:
            return n
        if n <= 0:
            return 0
        if n >= coins[i]:
            n -= coins[i]
            return get_remain(n, m-1, i)
        else:
            return get_remain(n, m, i+1)
    
    if __name__ == '__main__':
        t = input()
        for _ in range(t):
            n,m = map(int, raw_input().split())
            print get_remain(n, m, 0)
    

     

     
  • loctv 3:28 am on September 14, 2016 Permalink | Reply
    Tags: ,   

    Problem: Power of Numbers 

    Given a number N, let the reverse of the number be R. The task is to print the output of the Expression pow(N,R), where pow function represents N raised to power R.

    Input:
    The first line of the input consists of an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of a single line containing an integer N .

    Output:
    Corresponding to each test case, print in a new line, the output of the expression pow as described above.
    Note: As answers can be very large, print the result modulo 100000007.

    Constraints:
    1<=T<=1000
    1<=N<=78643

    Example:
    Input:
    2
    2
    12
    Output:
    4
    33235307

    Use pow(x,y,mod) in python , it returns x**y % mod, and so much faster than pow(x,y)%mod.

    def pow_(n, r):
        mod = 100000007
        n = pow(n,r,mod)
        return n
    
    if __name__ == '__main__':
        t = input()
        for _ in range(t):
            n = input()
            l = list(str(n))
            l.reverse()
            r = int(''.join(l))
            print pow_(n, r)
    

     

     
  • loctv 2:47 am on September 14, 2016 Permalink | Reply
    Tags: ,   

    Problem: Pallindrome Patterns 

    Given a string S, find out all the possible palindromes that can be generated using the letters of the string and print them in lexicographical order.

    Input
    The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains the string S.

    Output
    Print out all the combinations in lexicographical order, seprated by a space inside curly brackets, i.e { palindrome1 palindrome 2}. If no pallindromes can be formed, print empty braces { }.

    Constraints
    1 <= T <= 100
    0 < S <= 20

    Examples

    Input
    3
    abbab
    abcabc
    abc

    Output
    { abbba babab }
    { abccba acbbca baccab bcaacb cabbac cbaabc }
    { }

    Using itertools in python
    Python 2.7

    from itertools import *
    def pallindrome_permute(s):
        """
            return permutations of s that is a
            pallindrome string
        """
        res = set(list(permutations(s)))
        for x in res:
            x = ''.join(x)
            if is_pallindrome(x):
                yield x
    
    def is_pallindrome(s):
        """
        check if a string is pallindrome
        """
        length = len(s)
        length_2 = length/2
        for _ in range(length_2):
            if s[_] != s[length-1-_]:
                return False
        else:
            return True
    
    if __name__ == '__main__':
        t = input()
        for _ in range(t):
            s = raw_input().strip()
            print "{",
            for _ in sorted(list(pallindrome_permute(s))):
                print _,
            print "}"
    

     

     
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