FastPrep
Problem · Array

Prime Factor Visitation

Learn this problem
● MediumMaven Securities logoMaven SecuritiesINTERNOA

Problem statement

Alex has a row of light bulbs that are initially either on or off. 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:

  1. Find its distinct prime factors.
  2. For every such factor p, flip each bulb whose 1-based position is a multiple of p.

A factor is used only once for one value, even when it appears repeatedly in that value's prime factorization. The same factor may be processed again for another value in numbers, causing its bulbs to flip again.

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

Function

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

Examples

Example 1

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 final states are [1,0,0,1,0,0,0,0,1,1].

Constraints

  • 1 <= states.length <= 10^5
  • 1 <= numbers.length <= 10^5
  • Each states[i] is either 0 or 1.
  • 1 <= numbers[i] <= 10^5

More Maven Securities problems

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