- https://www.hackerrank.com/challenges/crush/forum/comments/255515
- https://www.hackerrank.com/challenges/crush/forum
- https://www.hackerrank.com/challenges/crush/problem
Problem
Given an array of ten elements [0,0,0,0,0,0,0,0,0,0].
Let’s say we are to apply an update to a certain range of indexes…say from a (index 2) to b (index 6), we want to add k (10) to all elements.
so
[0,0,0+10,0+10,0+10,0+10,0+10,0,0,0]
Let’s denote iteration from a to b as m, this would be O(m) time.
If we were to apply n updates, then we’d end up n * O(m) or O(m*n)
If m or n is huge, then we’d have a performance problem, as it could get close to O(n^2).
How to Solve
So the thing we’re trying to do is to figure out how to express the idea that we want to add a number k from a to b in better running time. Our tactic involves two steps:
1) Assign indices O(x)
2) Calculate sum O(y)
Total running time is O(x+y)
Step One
Use +k and -k at indexes to denote the change
[0, 0, 0(+10), 0, 0, 0, 0(-10), 0, 0, 0]
With our original array, we use +k at index 2 and -k and index (5+1) to show what we want to add k (10) to all the numbers from index 2 to 5.
The assignment of k is O(2), which is O(1).
But, since there are x updates, and we need to assign k indices for all the updates.
so the running time will be O(x) for x updates.
Step Two
Once all the indices have been assigned, we iterate and use a summation to assign all the numbers.
Using initial sum = 0, we add a[0] to sum
a[0] = 0;
a[1] = a[1] + a[0] = 0 + 0 = 0;
a[2] = a[2] + a[1] = 10 (k) + 0 = 10
a[3] = a[3] + a[2] = 0 + 10 = 10
a[4] = a[4] + a[3] = 0 + 10 = 10
a[5] = a[5] + a[4] = 0 + 10 = 10
a[6] = a[6] + a[5] = -10 (-k) + 10 = 0
a[7] = a[7] + a[6] = 0 + 0 = 0
[0, 0, 10, 10, 10, 10, 0, 0]
To do the sum, its O(y) where y is the number of elements, since we need to iterate from 0 to length – 1.
Thus, two steps of indices assignment at O(x) and then the sum at O(y) will give
O(x) + O(y) or O(x+y).
Example
One query:
[2, 5, 100]
initial array:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
step 1 – assign indices:
[0, 0, 100, 0, 0, 0, -100, 0, 0, 0]
step 2 – summation:
sum = 0,
a[0] = a[0] + sum = 0 + 0 = 0
a[1] = a[1] + a[0] = 0
a[2] = a[2] + a[1] = 100 + 0 = 100
a[3] = a[3] + a[2] = 0 + 100 = 100
a[4] = a[4] + a[3] = 0 + 100 = 100
a[5] = a[5] + a[4] = 0 + 100 = 100
a[6] = a[6] + a[5] = -100 + 100 = 0
a[7] = a[7] + a[6] = 0 + 0 = 0
a[8] = a[8] + a[7] = 0 + 0 = 0
a[9] = a[9] + a[8] = 0 + 0 = 0
[0, 0, 100, 100, 100, 100, 0, 0, 0, 0]
Two queries:
[2, 5, 100]
[3, 4, 50]
initial array:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Step 1 – assign indices:
[0, 0, 100, 0, 0, 0, -100, 0, 0, 0]
[0, 0, 0, 50, 0, -50, -0, 0, 0, 0]
We can add them together like so:
[0, 0, 100, 50, 0, -50, -100, 0, 0, 0]
Step 2 – summation:
sum = 0,
a[0] = a[0] + sum = 0 + 0 = 0
a[1] = a[1] + a[0] = 0
a[2] = a[2] + a[1] = 100 + 0 = 100
a[3] = a[3] + a[2] = 50 + 100 = 150
a[4] = a[4] + a[3] = 0 + 150 = 150
a[5] = a[5] + a[4] = -50 + 150 = 100
a[6] = a[6] + a[5] = -100 + 100 = 0
a[7] = a[7] + a[6] = 0 + 0 = 0
a[8] = a[8] + a[7] = 0 + 0 = 0
a[9] = a[9] + a[8] = 0 + 0 = 0
[0, 0, 100, 150, 150, 100, 0, 0, 0, 0]
Let’s verify by hand.
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
add 100 from 2 to 5
[0, 0, 100, 100, 100, 100, 0, 0, 0, 0]
add 50 from 3 to 4
[0, 0, 100, 150, 150, 100, 0, 0, 0, 0]
So our results match.
Let’s try one last example:
1) assign their indices first:
[0 0 0 100 0 -100 0 0 0] [3 4 100]
[0 0 100 0 0 0 -100 0 0] [2 5 100]
[0 100 0 -100 0 0 0 0 0] [1 2 100]
Because we have multiple operations, let’s group them together
[0 100 100 0 0 -100 -100 0 0]
2) calculate their summation
sum = 0,
a[0] = a[0] + sum = 0 + 0 = 0
a[1] = a[1] + a[0] = 100 + 0 = 100
a[2] = a[2] + a[1] = 100 + 100 = 200
a[3] = a[3] + a[2] = 0 + 200 = 200
a[4] = a[4] + a[3] = 0 + 200 = 200
a[5] = a[5] + a[4] = -100 + 200 = 100
a[6] = a[6] + a[5] = -100 + 100 = 0
a[7] = a[7] + a[6] = 0 + 0 = 0
a[8] = a[8] + a[7] = 0 + 0 = 0
[0 100 200 200 200 100 0 0 0]