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

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

Infosys logoInfosys● HardFULLTIMEOA
QuestionFunctionExamplesConstraints

Problem statement

Source note: This practice version is about a 65% match to the available source. The sequence alphabet, placement costs, modulo-four acceptance rule, and restriction on placing C in state three come directly from the source. The original output modulus, reliable upper bound for n, function signature, and examples were not shown, so FastPrep filled them in consistently and used a large bound that makes the source-reported matrix-exponentiation requirement meaningful.

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

  • Swap Two Gender ValuesPHONE SCREEN · Seen Oct 2026
  • Count Equal-Distinct Character PartitionsOA · Seen Oct 2026
  • Maximize the Even-Odd Index Product GapONSITE INTERVIEW · Seen Oct 2026
All Infosys interview questionsSee Infosys hiring insights
Saved
class Solution {
    public int countAcceptedSequences(long n) {
        // write your code here
    }
}
Checking account…