Connection Status:
Competition Arena > MagicNumberThree

MagicNumberThree

SRM 729 · 2018-02-08 · by erinn

SRM 729 · 2018-02-08 · by erinn · Simple Math
Class Name: MagicNumberThree
Return Type: int
Method Name: countSubsequences
Arg Types: (string)
Problem Statement

Problem Statement

You are given an integer (provided as String s as it may be up to 50 digits in length). Return the number of subsequences of digits in the number that themselves compose an integer that is divisible by 3. Since this count could be very large, return the number mod 1000000007.

Constraints

  • s will contain between 1 and 50 characters, inclusive.
  • Each character of s will be between '0' and '9', inclusive.
Examples
0)
"132"
Returns: 3

There are 7 total subsequences of the given digits, but only some of them work: 3, 12, and 132 are divisible by 3. 1, 2, 13, and 32 are not.

1)
"9"
Returns: 1

There's only one subsequence to consider here, and it is divisible by 3.

2)
"333"
Returns: 7

There are three ways to make a "3" as a subsequence, and we could all of them individually. There are also three ways to make a subsequence of "33", which we also count. And, of course, "333" also works.

3)
"123456"
Returns: 23
4)
"00"
Returns: 3

Remember that 0 is divisible by three. The sequence 00 of course also has the value 0.

Submissions are judged against all 22 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MagicNumberThree with a public method int countSubsequences(string s) · 22 test cases · 2 s / 256 MB per case

Submitting as anonymous