Facebook Pixel

Citadel OA | Prime Factor Visitation | Citadel Online Assessment Question

Alex entered a room with some fancy lights arranged in a row which were either on or off. Alex had a list of numbers and worked through each number on that list in order. For each number, Alex visited the bulbs at positions which were a multiple of the prime factors of the chosen number. Whenever a bulb was visited, its state was flipped. Determine the final state of each bulb after the numbers on the list were processed.

Note: this problem use 1-based indices.

Relevant Citadel OA Problems:

Input & Output
Input
states — an array of n integers that denote the initial states of each bulb
numbers — an array of m integers that denote the initial states of each bulb
Output
an array of integers denoting the final states
Example
Input
states = [1,1,0,0,1,1,0,1,1,1]
numbers = [3,4,15]
Output
[1,0,0,1,0,0,0,0,1,1]
Explanation

Initial state:

[1,1,0,0,1,1,0,1,1,1]

numbers[0]=3, there is one prime factor (3). After the states are changed, affected bulbs in bold:

[1,1,1,0,1,0,0,1,0,1]

numbers[0]=4, there is one prime factor (2). After the states are changed, affected bulbs in bold:

[1,0,1,1,1,1,0,0,0,0]

numbers[0]=15, the prime factors (3,5). After the states are changed, affected bulbs in bold:

[1,0,0,1,1,0,0,0,1,0]

[1,0,0,1,0,0,0,0,1,1]

Constraints
  • 1<=n<=10^5
  • 1<=m<=10^5
  • 0<=states[i]<=1
  • 1<=numbers[i]<=2*10^5

Try it yourself

Invest in Yourself
Your new job is waiting. 83% of people that complete the program get a job offer. Unlock unlimited access to all content and features.
Go Pro