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:

• Triplets
• Ways to Sum
• Consecutive Sum
• Disk Space Analysis
• Do They Belong?
• Global Maximum
• Initial Public Offering
• Inversions
• Portfolio Balances
• Prime Factor Visitation
• Profit Targets
• Sprint Training
• Throttling Gateway
• Birthday Card Collection

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

Examples

Example 1:

Input:

1states = [1,1,0,0,1,1,0,1,1,1]
2numbers = [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

Solution