Hey! Is someone who can help me solve this faster than O(N^2)? The problem: initially we have an array V1 of size N with the numbers from 1 to N ordered. ↵
↵
Example: N = 4; V1 = {1, 2, 3, 4}. ↵
↵
We have a second array of N numbers, let's say V2 = {3, 2, 0, 1}. For each position 'i' from right to left, we will apply the operation "move right the element V1[i] with V2[i] positions.↵
↵
We have 4 operations {3, 2, 0, 1}. Apply i = 3, so V1 will be {1, 2, 3, 4}; further we apply i = 2 (V2[2] = 0 so V1[2] stays);↵
we apply i = 1, so we move the element '2' with 2 positions right in V1 (the array becomes {1, 3, 4, 2}. Finally we apply i = 0 so V1 becomes {3, 4, 2, 1}. ↵
↵
Any idea? Thank you!
↵
Example: N = 4; V1 = {1, 2, 3, 4}. ↵
↵
We have a second array of N numbers, let's say V2 = {3, 2, 0, 1}. For each position 'i' from right to left, we will apply the operation "move right the element V1[i] with V2[i] positions.↵
↵
We have 4 operations {3, 2, 0, 1}. Apply i = 3, so V1 will be {1, 2, 3, 4}; further we apply i = 2 (V2[2] = 0 so V1[2] stays);↵
we apply i = 1, so we move the element '2' with 2 positions right in V1 (the array becomes {1, 3, 4, 2}. Finally we apply i = 0 so V1 becomes {3, 4, 2, 1}. ↵
↵
Any idea? Thank you!
