Ninja And The Strictly Increasing Array

Moderate
0/80
Average time to solve is 23m
profile
Contributed by
3 upvotes
Asked in company
Amazon

Problem statement

Ninja is a brilliant student in the class, so his teacher assigned him a problem.

He has been given an array ‘A’ containing positive integers ‘N’ integers.

He has also been given another array ‘B’ of size ‘N’ initially filled with 0’s at all the positions.

Now, In one move, Ninja can update any ‘B[i]’ as ‘B[i] - A[i]’ or as ‘B[i] + A[i]’, and he has been asked to find the minimum number of moves to make this array ‘B’ strictly increasing.

Your task is to help Ninja and print the minimum number of the above moves to make the array ‘B’ strictly increase.

Example :
Input: ‘N’ = 5, ‘A’ = [1, 2, 3, 4, 5]
Output: 4

Initially, array ‘B = [0, 0, 0, 0, 0], we will perform the following sequence of moves:
‘B[0] = B[0] - A[0]’ 
‘B[2] = B[2] + A[2]’ 
‘B[3] = B[3] + A[3]’ 
‘B[4] = B[4] + A[4]’ 
 After these moves, the updated array will be [-1, 0, 3, 4, 5], and this is the minimum possible number of moves to make this array strictly increase. 
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line contains a single integer ‘T’ denoting the number of test cases, then the test case follows.

For each test case, the first line will contain the integer ‘N’, the number of elements in the arrays ‘A’.
The second line will contain ‘N’ spaced integers i.e., the elements of the array 'A'. 
Output Format:
For each test case, return the minimum number of the moves needed to make the array ‘B’ strictly increasing.
Note:
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints:
1 ≤ T ≤ 10
2 ≤ N ≤ 10^3
1 ≤ A[i] ≤ 10^9
It is guaranteed that the sum of 'N' is ≤ 10^3 over all test cases.

Time limit: 1 sec
Sample Input 1:
2
2
2 2
7
1 2 1 2 1 2 1
Sample Output 1:
1
10
Explanation For Sample Input 1:
For test case 1:
Initially, the array ‘B’ = [0, 0] by one move, we can make it [0, 2], and hence the answer is 1.

For test case 2:
Initially, the array ‘B’ = [0, 0, 0, 0, 0, 0, 0] by 10 moves we can make it [−3, −2, −1, 0, 1, 2,  3], and hence the answer is 10. Here 10 is the minimum possible number of moves needed to make this array strictly increasing.
Sample Input 2:
2
4
2 4 1 1
6
2 1 4 1 3 5
Sample Output 2 :
4
5
Hint

Can you fix the position of 0?

Approaches (1)
Greedy Approach

Approach

 

Initially, the array 'B' has all elements set to 0, and it's better to have 0 in the final array. As the final array is strictly increasing, there will be only one 0 in this array.

 

Now we know that there will be 0 in the final array. If we fix the position of the 0, we will set the other values greedily: find the smallest value for each element, which is bigger than the previous one, and similarly before that element.
 

We will check this for all positions; we can calculate the answer in O(n) time for each. The minimum of all these answers will be the final answer. This will be done in O(n^2) complexity.
 

Algorithm:
 

  • Initialize a variable ‘ans = INT_MAX’
  • Iterate from 0 to ‘N’ with variable ‘i’
    • Initialize a variable ‘cur = 0’
    • Initialize a variable ‘temp = 0’ and iterate from ‘i + 1’ to ‘N’ with variable ‘j’
      • Update ‘cur’ as cur += (temp / a[j]) + 1 and ‘temp’ as ‘temp = (temp / a[j] + 1) * a[j]’
    • Set ‘temp = 0’ and reverse iterate from ‘i - 1’ to ‘0’ with variable ‘j’
      • Update ‘cur’ as ‘cur += (temp / a[j]) + 1’ and ‘temp’ as ‘temp = (temp / a[j] + 1) * 1LL * a[j]’
    • Update ‘ans = min(ans, cur)’
  • Return ‘ans’.
Time Complexity

O(N^2), where ‘N’ is the length of the array ‘A’.

 

As we are iterating over the array ‘A’ in 2 nested loops, both running ‘N’ times.

 

Hence, the time complexity is O(N^2).

Space Complexity

O(1).
 

As we are using constant extra space.

 

Hence, the space complexity is O(1).

Code Solution
(100% EXP penalty)
Ninja And The Strictly Increasing Array
Full screen
Console