Statistics

Problem Statement for "RecurrenceRelation"

Problem Statement

Consider a sequence {x0, x1, x2, ...}. A relation that defines some term xn in terms of previous terms is called a recurrence relation. A linear recurrence relation is one where the recurrence is of the form xn = ck-1xn-1 + ck-2xn-2 + ... + c0xn-k, where all the ci are real-valued constants, k is the length of the recurrence relation, and n is an arbitrary positive integer which is greater than or equal to k.

You will be given a int[] coefficients, indicating, in order, c0, c1, ..., ck-1. You will also be given a int[] initial, giving the values of x0, x1, ..., xk-1, and an int N. Your method should return xN modulo 10.

Note that the value of X modulo 10 equals the last digit of X if X is non-negative. However, if X is negative, this is not true; instead, X modulo 10 equals ((10 - ((-X) modulo 10)) modulo 10). For example, (-16) modulo 10 = ((10 - (16 modulo 10)) modulo 10) = (10 - 6) modulo 10 = 4.

More specifically, if coefficients is of size k, then the recurrence relation will be

  • xn = coefficients[k - 1] * xn-1 + coefficients[k - 2] * xn-2 + ... + coefficients[0] * xn-k.

For example, if coefficients = {2,1}, initial = {9,7}, and N = 6, then our recurrence relation is xn = xn-1 + 2 * xn-2 and we have x0 = 9 and x1 = 7. Then x2 = x1 + 2 * x0 = 7 + 2 * 9 = 25, and similarly, x3 = 39, x4 = 89, x5 = 167, and x6 = 345, so your method would return (345 modulo 10) = 5.

Definition

Class:
RecurrenceRelation
Method:
moduloTen
Parameters:
int[], int[], int
Returns:
int
Method signature:
int moduloTen(int[] coefficients, int[] initial, int N)
(be sure your method is public)

Notes

  • (a + b) modulo x = ( (a modulo x) + (b modulo x) ) modulo x for any values of a, b, and x.

Constraints

  • coefficients will have between 1 and 10 elements, inclusive.
  • initial will have the same number of elements as coefficients.
  • Each element of coefficients will be between -1000 and 1000, inclusive.
  • Each element of initial will be between -1000 and 1000, inclusive.
  • N will be between 0 and 100000, inclusive.

Examples

  1. {2,1}

    {9,7}

    6

    Returns: 5

    As described in the problem statement.

  2. {1,1}

    {0,1}

    9

    Returns: 4

    This is the famous Fibonacci sequence, which goes 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

  3. {2}

    {1}

    20

    Returns: 6

    This sequence is 1, 2, 4, 8, 16, ...

  4. {2}

    {1}

    64

    Returns: 6

    Watch out for overflow.

  5. {1,2,3,4,5,6,7,8,9}

    {9,8,7,6,5,4,3,2,1}

    96837

    Returns: 3

  6. {25,143}

    {0,0}

    100000

    Returns: 0

    This sequence will always be zero.

  7. {9,8,7,6,5,4,3,2,1,0}

    {1,2,3,4,5,6,7,8,9,10}

    654

    Returns: 5

  8. {901,492,100}

    {-6,-15,-39}

    0

    Returns: 4

    Watch out for negative numbers.

  9. {901,492,100}

    {5,-15,-39}

    2

    Returns: 1

  10. {-2}

    {-4}

    3

    Returns: 2

  11. {4,9,-150,-30}

    {63,10,-199,593}

    83

    Returns: 1

  12. {157,-358,1000,29,-599}

    {28,0,53,-66,-599}

    93753

    Returns: 9

  13. {999,999,999,999,999,999,999,999,999,999}

    {999,999,999,999,999,999,999,999,999,999}

    99999

    Returns: 9

  14. {217, 588, 967, -12, -659, 764, -778, -529}

    {-475, -963, -265, -270, -557, 365, 843, 342}

    28387

    Returns: 8

  15. {771}

    {-891}

    73266

    Returns: 9

  16. {-377, 442, -643, 692, -569}

    {-713, 267, 771, 950, -535}

    78556

    Returns: 5

  17. {-941, -246, -272, 47, 575, -667, 726, 54, -873, 796}

    {-559, -396, -347, -509, -174, -955, -982, 496, -733, -693}

    6441

    Returns: 1

  18. {574, -878, -582, 287, -871, -109, 950, -349, 667}

    {-532, 265, -447, -107, 346, -559, 176, -447, -775}

    2239

    Returns: 5

  19. {-729, 576, -843}

    {105, -118, 260}

    71291

    Returns: 1

  20. {568, -696, 286, 521}

    {-183, -302, 984, 261}

    69507

    Returns: 3

  21. {711, -847, -336, 334, -787, 540, -886, -746, 808}

    {-777, -842, 660, 315, -443, 593, 368, 247, 969}

    8286

    Returns: 5

  22. {478, -555, 887, 322, -452}

    {189, 339, 731, 407, 416}

    57268

    Returns: 9

  23. {639, -584}

    {925, 860}

    70138

    Returns: 5

  24. {-384, 706, -912, -643, -229, -379, -566}

    {-397, -810, -280, -388, -483, -429, -407}

    12128

    Returns: 9

  25. {-150, 716, 96, -624, -527, -901, -662, 507}

    {151, 203, -42, 399, -501, 134, 875, -46}

    38428

    Returns: 7

  26. {144, 932, -708, 576}

    {-877, 58, -298, -87}

    68447

    Returns: 8

  27. {506, -560, 561}

    {-148, 913, -844}

    24724

    Returns: 6

  28. {-329, 612, 991, 835, 586, -161, -447, 744, -403}

    {492, 144, 711, -672, 341, 621, 983, -516, -964}

    73462

    Returns: 3

  29. {-494, 297, 984, 925}

    {575, -988, 294, 101}

    56215

    Returns: 5

  30. {758, -912}

    {678, 369}

    50217

    Returns: 4

  31. {-363, 521, 555, -43, 899, -852}

    {-344, 780, -641, -893, -743, -505}

    14068

    Returns: 7

  32. {-775, 581, -631, -628}

    {-643, 522, 122, 851}

    39505

    Returns: 7

  33. {-110, 57, -94, -387}

    {980, -22, 879, 100}

    69226

    Returns: 4

  34. {-893, -798, 605}

    {-774, -813, -466}

    21337

    Returns: 5

  35. {-647, 251, -246, 53, 109, -393, -566, -602, 692}

    {721, -275, 259, 656, -423, 903, 706, 179, -191}

    28546

    Returns: 1

  36. {-65, 819, 904, 229, -446, 764, 708, 190}

    {678, 42, -980, 66, 988, -93, -428, -539}

    20988

    Returns: 2

  37. {674, -623, -601, 544, 991, 606, -217, -915, 139}

    {-60, -720, -189, -203, 235, -592, -460, -399, 547}

    5036

    Returns: 4

  38. {-831, 913, 640, -939, 639}

    {176, 490, 620, -614, 450}

    1166

    Returns: 4

  39. {-611, 593, -69, 142, 928, -114, -155, 311}

    {-437, -655, 136, -79, -253, -290, -471, 984}

    41238

    Returns: 3

  40. {909, -336, -595, -3, 805, 474, 948}

    {359, 378, 862, -533, -365, 991, 863}

    52247

    Returns: 7

  41. {765}

    {42}

    16129

    Returns: 0

  42. {520, 210, 984, -508, 596, -661, -403, -562}

    {274, 964, -946, -149, 682, 61, -439, 2}

    95186

    Returns: 6

  43. {469, 628, 775}

    {784, -58, 132}

    72912

    Returns: 4

  44. {4,-6}

    {2,3}

    2

    Returns: 0

    Notice that -10 modulo 10 = 0.

  45. { 901, 492, 100 }

    { -6, -15, -39 }

    0

    Returns: 4

  46. { 2 }

    { -111 }

    0

    Returns: 9

  47. { 2 }

    { 1 }

    20

    Returns: 6

  48. { 2 }

    { 1 }

    64

    Returns: 6

  49. { 2 }

    { -100 }

    0

    Returns: 0

  50. { 1, 1 }

    { 1, 2 }

    0

    Returns: 1

  51. { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }

    { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

    654

    Returns: 5

  52. { 2 }

    { 1 }

    9999

    Returns: 8

  53. { 45, 23 }

    { 43, 55 }

    0

    Returns: 3

  54. { 901, 492, 100 }

    { -6, -15, -39 }

    1

    Returns: 5

  55. { -10, -10 }

    { 1, 1 }

    10000

    Returns: 0

  56. { 1 }

    { -1 }

    0

    Returns: 9

  57. { 0, 0, 0 }

    { 1, 2, 3 }

    99999

    Returns: 0

  58. { 2, 1 }

    { 9, 7 }

    0

    Returns: 9

  59. { 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000 }

    { 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000 }

    100000

    Returns: 0

  60. { 1, 1, 1 }

    { 9, 1, 1 }

    0

    Returns: 9

  61. { 34, 43 }

    { -199, 323 }

    0

    Returns: 1

  62. { 7 }

    { 1 }

    100000

    Returns: 1

  63. { -32, -34 }

    { -199, -32 }

    0

    Returns: 1

  64. { 2 }

    { 1 }

    108

    Returns: 6

  65. { 25, 143, -111, -432, -312, -999 }

    { -818, -13, -312, -823, -211, 987 }

    100000

    Returns: 8

  66. { -16 }

    { -16 }

    0

    Returns: 4

  67. { 25, 143, -123, -234, -345, -567 }

    { -12, -982, -345, 247, -232, -987 }

    100000

    Returns: 0

  68. { 10, 10 }

    { 10, 10 }

    0

    Returns: 0

  69. { 2 }

    { 2 }

    0

    Returns: 2

  70. { 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000 }

    { 1000, 1000, 1000, 1000, 999, 1000, 1000, 1000, 1000, 1000 }

    100000

    Returns: 0

  71. { 1, 1 }

    { 10, 10 }

    1

    Returns: 0

  72. { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

    { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

    3

    Returns: 4

  73. { 1, 2, 3 }

    { -1, -10, -2 }

    1

    Returns: 0

  74. { 1, 1 }

    { 12, 12 }

    1

    Returns: 2

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: