We are given an integer N, representing the size of array (Array numbered from 1 to N). Initially, each element of the array is 0.
Now we have to perform T transformations and output the entire transformed array at the end.
Description of each transformation:
Given two integer x and y. For subarray, from 1 to x, we find the minimum element and increment it by one. If there are many elements with the same minimum value, we choose the element with a lower index value. We perform this operation y times.
Sample Input :
7
1
3 5
Sample Output:
2 2 1 0 0 0 0
Explanation:
For N =7, initially array is 0 0 0 0 0 0 0.
For 1 transform say x=3, y=5.
After 1st transformation : 1 0 0 0 0 0 0. (minimum element from 1 to 3 subarray is 0 and minimum index of it is 1).
After 2nd transformation : 1 1 0 0 0 0 0
After 3rd transformation : 1 1 1 0 0 0 0
After 4th transformation : 2 1 1 0 0 0 0
After 5th transformation : 2 2 1 0 0 0 0
Now the problem is, if we apply another transformation, then how can modify the array accordingly? Couldn’t think of anything except the brute force method.
How can we solve this optimally? What will be its time complexity?
Suppose if Y % X == 0 then all of your values from index 1 to X would be equal to Y/X so you can just directly print the array.
Otherwise:
Fill values for all values from index 1 to X = Y / X. The remaining values to be added would be Y % X. Simply add them in the present index while decrementing the value of Y%X. So in short the problem is O(n) that too looping while printing. Example1:
N = 6, Y = 12, X = 4
Your array directly would be 3 3 3 3 0 0 since Y % X == 0 Example2:
N = 6, Y = 12, X = 5
Fill values for Y / X from 1 to 5 i.e. 2 2 2 2 2 0
Left value i.e. Y % X = 2 directly add from index 1 to whenever Y % X != 0 i.e. final array 3 3 2 2 2 0.
Ok, So it is pretty clear from the problem statement that we only need to worry about elements from index 1 to X, rest will be 0s ( i.e N-X 0s )
We have three cases to consider:
Y = X : In this case, each element in the subarray will be incremented by 1 and we stop.
Y < X : In this case only elements from 1 to Y are incremented by 1 and we stop.
Y > X : In this case we Increment each element in the subarray by 1, subtract X from Y (i.e Y = Y - X), and we repeat this procedure with updated value of Y (till case 1 or 2 is encountered)
Now, We are only making increments of 1.
Which means we can calculate a value a base value achieved by recurring over Case 3 by:
Base_value = Y/X;
and update Y as
Y = Y % X;
Now we know that Y will be less than X ( i.e Y < X ), we can simply traverse over elements 1 to Y and add 1 to them and print.
Time complexity: In worst case, X is equal to N and Y is equal to N-1, therefore we have to traverse all elements at least once. Therefore it of order O(N), Linear Time.
Pseudo Code:
input (N,X,Y)
Base_Value = Y/X
Y = Y%X
For i in range(1:N):
if ( i less than or equal to Y ):
print(Base_Value + 1)
else if ( i less than or equal to X ):
print(Base_Value)
else
print(0)
If you have any Questions about this, Please free to ask
Yeah, i figured that out. But the thing is there are T transformations possible. So it means there can be a lot of transformations on
3 3 3 3 0 0 (in example 1) as well. How do we go doing it??
For instance the next transformation can be x=7 and y=8.
Then on first transformation : 3 3 3 3 1 0
2nd one : 3 3 3 3 1 1
3rd one : 3 3 3 3 2 1
4th one : 3 3 3 3 2 2
5th one : 3 3 3 3 3 2
6th one : 3 3 3 3 3 3
7th one : 4 3 3 3 3 3
8th one : 4 4 3 3 3 3
There can be T values of x and y. Here is the main problem.
Didn’t really get you. Elaborate. But if in case you mean by handling T transformations using same array once instead of recreating copy of previous array transformation, you could follow some offline mode and sort the transformation queries based on size of X and size Y and print accordingly. That would be faster.
This will be valid for the first transformation only. But for T transforms, we will get T values of x and y. And all these transformations will happen on the same array(for the same N, I mean).
E.g
6(=N)
2 (= T transformations)
4 12 (1st transformation for x=4,y=12)
7 8 (2nd transformation for x=7, y=8)
Output will be :
4 4 3 3 3 3
Explanation:
After 1st transformation array would have become, 3 3 3 3 0 0
After second transformation, array will become, 4 4 3 3 3 3
You can see my comment on the above answer, and it will make things clearer about how we achieved 4 4 3 3 3 3.
I meant that we have to perform T transforms for the same value of n. (or the same array in other words).
So input is something like :
6(=n)
2 (=number of transforms)
4 12 (x=4 and y=12)
7 8 (x=7 and y=8)
Output :
4 4 3 3 3 3
In the above comment, I just wanted to show how we will get there after another transformation. But the problem is, there are T transformations. How to get the final array elements?
