LuckyRemainder
SRM 509 · 2010-11-01 · by nV
SRM 509 · 2010-11-01 · by nV · Simple Math
Problem Statement
Problem Statement
Little Arthur loves numbers and 9 is his most favorite. When encountering a number, he always calculates its lucky remainder - the remainder after division by 9.
This time Arthur is given a number X of length N which contains no zeros. He is asked to find the supersum of X: super(X).
super(X) is defined as follows. For a given non-full set S of digit positions in X we erase the digits in these positions to obtain a sub-number. For example, if X = 12345 and S = {2, 4} we erase 2nd and 4th digits and obtain a sub-number 135. Supersum of X is simply the sum of sub-numbers for all valid sets S.
For example, if X is 123, then super(X) = 123 + 12 + 13 + 23 + 1 + 2 + 3 = 177.
Calculating super(X) is very difficult for Arthur. However, before getting to work he is wondering if it is possible to quickly tell what the lucky reminder of the supersum of X is. You have to help him.
GivenString X, which contains the decimal representation of the number X, return super(X)'s lucky remainder.
This time Arthur is given a number X of length N which contains no zeros. He is asked to find the supersum of X: super(X).
super(X) is defined as follows. For a given non-full set S of digit positions in X we erase the digits in these positions to obtain a sub-number. For example, if X = 12345 and S = {2, 4} we erase 2nd and 4th digits and obtain a sub-number 135. Supersum of X is simply the sum of sub-numbers for all valid sets S.
For example, if X is 123, then super(X) = 123 + 12 + 13 + 23 + 1 + 2 + 3 = 177.
Calculating super(X) is very difficult for Arthur. However, before getting to work he is wondering if it is possible to quickly tell what the lucky reminder of the supersum of X is. You have to help him.
Given
Constraints
- X will contain between 1 and 50 characters, inclusive.
- Each character of X will be one of the following: '1', '2', '3', '4', '5', '6', '7', '8', '9'.
Examples
0)
"123" Returns: 6
Example from the problem statement. super(123) = 177, which gives remainder 6 after division by 9.
1)
"24816" Returns: 3
Supersum of 24816 is 43986.
2)
"8" Returns: 8
3)
"11235813213455" Returns: 7
Supersum is 43950094900477.
4)
"9" Returns: 0
Submissions are judged against all 197 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class LuckyRemainder with a public method int getLuckyRemainder(string X) · 197 test cases · 2 s / 256 MB per case