City Infection Number
Reported by candidates from Arcesium's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The classic way to lose this Arcesium question from July 2025 is to simulate the infection day by day, or to use n where the formula needs n-1. Either one burns your attempt. The row of cities is Pascal's triangle mod 2 in disguise, and the answer is a bit-manipulation shortcut. If you spot that, it's a ten-line function. If you don't, you're staring at a quadratic loop with huge numbers. StealthCoder sits invisibly on your screen during the live OA as a safety net if you blank on the pattern. Know the trick first, though, because it's short.
The problem
An infinite row of cities is indexed from 0. Each city is either healthy (0) or infected (1). On day 1, only city 0 is infected. For every later day, the state of city i is the XOR of the previous-day states of cities i - 1 and i. Treat city -1 as always healthy. After day n, interpret the city states as a binary number with city 0 as the least significant bit. Return that number modulo 10^9 + 7. Function infectedCitiesValue(n: int) → int Examples Example 1 n = 6 return = 51 The states from city 0 through city 5 are 1, 1, 0, 0, 1, 1. With city 0 as the least significant bit, the value is 1 + 2 + 16 + 32 = 51. Example 2 n = 1 return = 1 Only city 0 is infected on day 1. Constraints 1 <= n <= 10^6.
Reported by candidates. Source: FastPrep
Pattern and pitfall
Each day, state[i] = prev[i-1] XOR prev[i]. That's Pascal's rule mod 2, so after day n the state of city i is C(n-1, i) mod 2. Check n=6: row 5 is 1,5,10,10,5,1, which gives 1,1,0,0,1,1. Matches. By Lucas' theorem, C(m, i) is odd exactly when i is a submask of m, with m = n-1. The value is the sum of 2^i over all submasks i of m. That factors into a product over set bits j of m of (1 + 2^(2^j)), taken mod 10^9+7. Get each 2^(2^j) by squaring repeatedly. The pitfalls are using n instead of n-1 and simulating days with big integers. For n up to 10^6 you could also loop i from 0 to m and test (m & i) == i. If the Lucas step doesn't come to you under pressure, StealthCoder is the hedge during the live OA.
If this hits your live OA and you blank, StealthCoder solves it in seconds, invisible to the proctor.
You can drill City Infection Number cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who would have shipped this the night before his JPMorgan OA if he'd had it.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Arcesium's OA.
Arcesium reuses patterns across OAs. Built by an Amazon engineer who would have shipped this the night before his JPMorgan OA if he'd had it. Works on HackerRank, CodeSignal, CoderPad, and Karat.
City Infection Number FAQ
What's the trick in City Infection Number?+
The state after day n is row n-1 of Pascal's triangle mod 2. City i is infected exactly when i is a submask of n-1. So the answer is the sum of 2^i over submasks of n-1, taken mod 10^9+7. No day-by-day simulation is needed.
Why does the product formula work?+
Summing 2^i over all submasks of m means each set bit j of m is either included or not. Including it adds 2^(2^j) to the exponent sum. Independent choices multiply out as the product of (1 + 2^(2^j)). For m=5 that's (1+2)(1+16)=51.
What's the most common mistake?+
Two things. First, using n instead of n-1, since day 1 is row 0. Second, simulating each day with a big integer or array, which is quadratic and too slow for n up to 10^6. Check your formula against n=1 giving 1 and n=6 giving 51 before submitting.
Can I just brute force it with n up to 10^6?+
A direct day-by-day simulation is O(n^2) and won't survive. But a single loop over i from 0 to n-1, checking (m & i) == i and adding 2^i mod p with a running power, is O(n) and fine. The product formula is O(log n), which is cleaner.
How do I prepare for this in 48 hours?+
Work out Pascal's triangle mod 2 by hand for a few rows and see the Sierpinski pattern. Learn the Lucas submask fact and modular exponentiation by squaring. Then write the function and test it on n=1 and n=6. That covers the whole problem, and it's an evening of work.