FastPrep
Problem · Array

Prime Factor Visitation

Learn this problem
● MediumCitadel logoCitadelFULLTIMEOA

Problem statement

A row contains n bulbs. The bulb at 1-based position i has state states[i - 1], where 0 means off and 1 means on.

Process the values in numbers from left to right. For each value x:

  1. Find the distinct prime factors of x.
  2. For every such factor p, flip every bulb whose 1-based position is a multiple of p: p, 2p, 3p, and so on while the position is at most n.

Each occurrence of a prime factor is processed independently. If the same factor appears for multiple values in numbers, its affected bulbs are flipped again each time.

Return the final state of every bulb after all values have been processed.

Function

lightsBulbs(states: int[], numbers: int[]) → int[]

Examples

Example 1

states = [0, 1, 1, 0, 1, 1, 0, 1, 1, 1]numbers = [3, 8, 6]return = [0, 1, 1, 0, 1, 1, 0, 1, 1, 1]

The distinct prime-factor sets are {3}, {2}, and {2, 3}. Across the full list, the multiples of 2 are flipped twice and the multiples of 3 are flipped twice. Every affected bulb therefore returns to its initial state.

Example 2

states = [1, 1, 0, 0, 1, 1, 0, 1, 1, 1]numbers = [3, 4, 15]return = [1, 0, 0, 1, 0, 0, 0, 0, 1, 1]

The distinct prime factors are {3} for 3, {2} for 4, and {3, 5} for 15.

  • Factor 3 flips positions 3, 6, and 9.
  • Factor 2 flips positions 2, 4, 6, 8, and 10.
  • The final value 15 flips multiples of 3, then multiples of 5.

The resulting states are [1, 0, 0, 1, 0, 0, 0, 0, 1, 1].

Constraints

  • 1 ≤ states.length ≤ 10^5
  • 1 ≤ numbers.length ≤ 10^5
  • states[i] is either 0 or 1.
  • 1 ≤ numbers[i] ≤ 10^9

More Citadel problems

drafts saved locally
public int[] lightsBulbs(int[] states, int[] numbers) {
    // Write your code here
}
states[0, 1, 1, 0, 1, 1, 0, 1, 1, 1]
numbers[3, 8, 6]
expected[0, 1, 1, 0, 1, 1, 0, 1, 1, 1]
checking account