## 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)
```

## 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)
```

## 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)
```

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