NITT5 - Subset and upset
The whole world is crazy about subset sum. We define subset sum as sum of all subparts. A subpart is a number which is obtained by erasing certain digits and arranging the remaining numbers in the same order. You have to calculate the subset sum of the given number. Since the number can be very large return the subset sum modulo 9.
For example if the number is 1357, then the various subparts are 1, 3, 5, 7, 13, 15, 17, 35, 37, 57, 137, 135, 157, 357, 1357.
Input
First line contains T denoting the number of test cases (T <= 50).
Next T lines containing the number (maximum number digits of the number can be 51).
Output
Print the subset sum modulo 9
Example
Input: 2 456 111 Output: 6 3
hide comments
Rishabh Joshi:
2015-05-31 15:50:39
Loved solving it in O(n).
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-10-03 14:27:13
@zukow: Yes, thanks for the idea, I've made the problem SUBSHARD
|
|
:D:
2012-10-02 22:57:23
This could be a good problem if modulo was a parameter in test case (<=10^9), and digits number <= 1000. |
|
Francky:
2012-10-02 20:15:38
Should be move to tutorial.
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-10-02 12:02:20
mod 9 make this problem easy... |
Added by: | jack(chakradarraju) |
Date: | 2012-09-23 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |