Find any valid sequence of magic operations so that all the cards face upwards.
EXPLANATION:
The only observation for this problem required is that the magic operation on the rightmost card affects only itself and not any other card.
So, we simply do a linear scan from left to right and whenever we encounter a card facing down, we perform the magic operation on it. This solution will tak atmost O(n) steps as we can perform the magic operation on all the elements in the worst case. As per the constraints, k >= n, so the above solution will work.
We must do binary search in this question by comparing each element with its consecutive element.We must not do anything if its a positive no. but if its a negative no. there will be two cases-
the first element is negative and the second one is also negative.
the first element is negative and the second one is positive.
In the first case,the magic operation will make them both positive and so while doing binary search whenever we will encounter consecutive negative number , we will jump onto the next no. by leaving this pair.
In the second case,the magic operation will make the negative no. into positive and vice versa.
And therefore we must swap these nos. until we get another negative no. in the array.
And thus storing their position in some variable.