Statistics

Problem Statement for "DigitMultiples"

Problem Statement

You are given two strings of digits, single and multiple. Your job is to find the length of the longest substring (which may be the whole string) of digits in single such that there is a corresponding substring (of the same length) in multiple which satisfies the following constraint. Each digit in the substring of multiple is the same exact integer multiple of the corresponding digit in the substring of single. So "48" is a multiple (4) of "12", but "72" is not a multiple of "36". Multiplication factors from 0 to 9 are possible. Leading zeros are *allowed* in single and multiple and all substrings.

For example: in "3211113321571" and "5555266420", here are a few (but not all) of the multiples:

"3211113321571"        "5555266420"
"-----------7-"  x 0 = "---------0"
"--------2----"  x 1 = "----2-----"
"--11---------"  x 6 = "-----66---"
"321----------"  x 2 = "------642-"
"--1111-------"  x 5 = "5555------"
"-----13321---"  x 2 = "----26642-"

The answer is 5, the length of the longest string with a multiple, "13321".

Definition

Class:
DigitMultiples
Method:
getLongest
Parameters:
String, String
Returns:
int
Method signature:
int getLongest(String single, String multiple)
(be sure your method is public)

Notes

  • Each digit multiple must be exactly a single digit. For example: '3' x 4 never matches.

Constraints

  • single will have between 1 and 50 characters inclusive.
  • multiple will have between 1 and 50 characters inclusive.
  • each character of single will be between '0' and '9' inclusive.
  • each character of multiple will be between '0' and '9' inclusive.

Examples

  1. "3211113321571"

    "5555266420"

    Returns: 5

    The example from above. Longest multiple = "13321" x 2 = "26642"

  2. "100200300"

    "100400600"

    Returns: 8

    "00200300" x 2 = "00400600"

  3. "111111111100000000000000000000000000000000000"

    "122333444455555666666777777788888888999999999"

    Returns: 9

  4. "000000000000"

    "000000000000"

    Returns: 12

    Any integer multiple works here.

  5. "11111111111"

    "11111111111"

    Returns: 11

    The factor is one.

  6. "89248987092734709478099"

    "00000000000000000000000"

    Returns: 23

    The factor is zero.

  7. "99999999999999999999999999999999"

    "0000000000000000000000000999999999999"

    Returns: 25

  8. "11111211312112212313113213321121222122323123223331"

    "12346612363621621636216126316363636216263661623261"

    Returns: 4

  9. "00101101010100010101011101110110110101010101001011"

    "00010110101101101110101010110101010100101001010111"

    Returns: 14

  10. "49348938595890134493859890581397857501935890571033"

    "98905819084901000000000000000189347875831758578933"

    Returns: 15

  11. "8978575893475895487346384673892579238753847928347"

    "7897857589347589548734638467389257923875384792834"

    Returns: 48

  12. "01234801395880000101390302439000430485839583015007"

    "48013958800001013903024390004304858395830150012346"

    Returns: 45

  13. "12131415161718191920212223242526272829303132333435"

    "71727374757677787980818283848586878789909192939495"

    Returns: 4

  14. "01020304050607080910112131415161718192102223242526"

    "71727374757677787981828384858687878991939495979899"

    Returns: 2

  15. "01020304050607080901020304050607080901020304050607"

    "99989796959493929179787776757473727189888786858483"

    Returns: 1

  16. "90919293949596979899808182838485868788897071727374"

    "01020304050610111213141516202122232425263031323334"

    Returns: 1

  17. "2222222222222222222222222233333333333333333333333"

    "4444444444444444446666666666666666669999999999999"

    Returns: 36

  18. "22222222222222222222222222222223333333333333"

    "22222222222222226666666666666666999999999999"

    Returns: 28

  19. "77777777777777777777777777777777777777777777777777"

    "55555555555555555555555555555555555555555555555555"

    Returns: 0

  20. "77777777777777777777777777777777777777777777777773"

    "35555555555555555555555555555555555555555555555555"

    Returns: 1

  21. "00000000000000000000000000000000000000000000000000"

    "00000000000000000000000000000000000000000000000000"

    Returns: 50

  22. "11111111111111111111111111111111111111111111111111"

    "00000000000000000000000001111111111111111111111111"

    Returns: 25

  23. "39"

    "71"

    Returns: 0

  24. "16"

    "32"

    Returns: 1

  25. "000"

    "123"

    Returns: 0

  26. "9"

    "7"

    Returns: 0

  27. "000"

    "111"

    Returns: 0

  28. "36"

    "72"

    Returns: 0

  29. "123"

    "216"

    Returns: 1

  30. "25"

    "75"

    Returns: 1

  31. "6"

    "00"

    Returns: 1

  32. "09"

    "81"

    Returns: 0

  33. "121"

    "131"

    Returns: 1

  34. "2"

    "3"

    Returns: 0

  35. "11111111111111111111111111111111111111111111111111"

    "0000000000000000000111111111111111111111111111111"

    Returns: 30

  36. "04"

    "32"

    Returns: 0

  37. "52"

    "31"

    Returns: 0

  38. "12121"

    "23232"

    Returns: 1

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: