Calculate the Sum After Range Toggles
Updated
Problem statement
A row contains n switches numbered from 1 to n. Every switch is initially off.
Each pair [left, right] in operations toggles every switch in that inclusive interval: off becomes on, and on becomes off.
Apply all operations and return the sum of the indices of the switches that are on at the end.
For this exercise, assume n is the number of switches and operations.length is the number of operations. If the operation list is empty, return 0.
Function
calculateTheSum(n: int, operations: int[][]) → intExamples
Example 1
n = 7operations = [[1,4],[2,6],[1,6]]return = 9After [1,4], switches 1, 2, 3, 4 are on. After [2,6], switches 1, 5, 6 are on. After [1,6], only switches 2, 3, 4 are on, so the sum is 2 + 3 + 4 = 9.
Example 2
n = 5operations = [[1,5]]return = 15The only operation turns on every switch. The sum is 1 + 2 + 3 + 4 + 5 = 15.
Example 3
n = 5operations = [[1,3],[1,3]]return = 0Every switch in [1,3] is toggled twice and returns to off. The other switches stay off, so the sum is 0.
Example 4
n = 4operations = []return = 0No operation changes any switch. Every switch remains off, so the sum is 0.
Constraints
- For this exercise, assume
1 <= n <= 50000. - For this exercise, assume
0 <= operations.length <= 10^5. - Each operation contains exactly two integer indices and satisfies
1 <= left <= right <= n. - The returned sum fits in a signed
32-bit integer under these bounds.
Similar questions at other companies
- Count Subarrays with a Perfect-Square ProductMicrosoft · OAMicrosoft interview questions
- Count Subarrays With Given XORInMobi · OAInMobi interview questions
- Earliest Time to Schedule a MeetingMathWorks · OAMathWorks interview questions
- Earliest Meeting Start on a 24-Hour ClockIMC Trading · OAIMC Trading interview questions
- Minimize the Maximum Array ElementChubb · OAChubb interview questions
- Minimum Power-of-Two Removal OperationsIBM · OAIBM interview questions
- Optimal TransferSnowflake · OASnowflake interview questions
- Count Attack Vectors by Divisor RangeVisa · OAVisa interview questions
- Smallest Most-Lit Street PositionHudson River Trading · OAHudson River Trading interview questions
- Vehicle Builds for Required Terrain (Game Adaptation)Roblox · OARoblox interview questions