Statistics

Problem Statement for "MagicNumberThree"

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.

Definition

Class:
MagicNumberThree
Method:
countSubsequences
Parameters:
String
Returns:
int
Method signature:
int countSubsequences(String s)
(be sure your method is public)

Constraints

  • s will contain between 1 and 50 characters, inclusive.
  • Each character of s will be between '0' and '9', inclusive.

Examples

  1. "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.

  2. "9"

    Returns: 1

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

  3. "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.

  4. "123456"

    Returns: 23

  5. "00"

    Returns: 3

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

  6. "33333333333333333333333333333333333333333333333333"

    Returns: 898961330

  7. "62384743394755163270431467082083782018151384161323"

    Returns: 966233066

  8. "30165309167602009721451281463066597821289264752531"

    Returns: 967019498

  9. "74118889738451011152784322864398222154080338046446"

    Returns: 966331370

  10. "30013897969143401388570614453754279881842744988049"

    Returns: 966495210

  11. "33650603094342059736105468256254133276638419983234"

    Returns: 943950826

  12. "91688271924467302088720076954859123473514564847369"

    Returns: 966233066

  13. "52457605013271742438295641552395952256463223828573"

    Returns: 966331370

  14. "13977677151537272284950740718239881552765859588410"

    Returns: 966319082

  15. "96724632278588216466104190002512072725452390709673"

    Returns: 965970922

  16. "14859915336296565054819038043913383735835611903241"

    Returns: 960728042

  17. "0000000000000000000000000000000000000000"

    Returns: 511620082

  18. "41184676334265001916915724114782935826962244645705"

    Returns: 966364138

  19. "12345678901234567890123456789012345678901234567890"

    Returns: 967019498

  20. "32132132133213213213321321321332132132133213213213"

    Returns: 967019498

  21. "0000000000000000000000000000000000000000000000000"

    Returns: 949480668

  22. "01234067891111111111111122222222222222222222111111"

    Returns: 966320458

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: