FastPrep
Problem · Dynamic Programming

Count Valid A-B-C Sequences Under a Modulo-Four Rule

Learn this problem
● Hardinfosys logoinfosysFULLTIMEOA

Problem statement

Build a sequence of length n using the characters A, B, and C. Start with a total cost of zero.

  • Placing A increases the total cost by 1.
  • Placing B or C increases the total cost by 0.
  • If the current total cost is congruent to 3 modulo 4, you may not place C next.

A completed sequence is accepted when its final total cost is divisible by 4.

Return the number of accepted sequences of length n, modulo 1000000007.

Function

countAcceptedSequences(n: long) → int

Examples

Example 1

n = 1return = 2

The accepted sequences are B and C. The sequence A finishes with cost one.

Example 2

n = 4return = 17

A four-state dynamic program for the current cost modulo four contains [17,32,24,7] sequences after four placements, so 17 finish in the accepted state.

Example 3

n = 10return = 9104

Applying the same four-state transition ten times leaves 9104 sequences in residue state zero.

Constraints

  • 1 <= n <= 1000000000000000000
  • Return the answer modulo 1000000007.

More infosys problems

drafts saved locally
public int countAcceptedSequences(long n) {
    // write your code here
}
n1
expected2
checking account