Sort the elements by minimum number of operations

Given two positive integer arrays X[] and Y[] of size N, Where all elements of X[] are distinct. Considering all the elements of X[] are lying side by side initially on a line, the task is to find the minimum number of operations required such that elements in X[] becomes in increasing order where in one operation you can increase each element of X[] by their respective values index in Y[] (first element of X[] element can be incremented by the first element of Y[] or position of the second element of X[] can be incremented by the second element of Y[] or so on….).

Examples:

Input: N = 3, X[] = {3, 2, 1}, Y[] = {1, 1, 1}
Output: 6
Explanation: According to the problem statement:

• X[1] = 3, It’s position can be incremented by Y[1] = 1.
• X[2] = 2, It’s position can be incremented by Y[2] = 1.
• X[3] = 1, It’s position can be incremented by Y[3] = 1.
• Operations:
  • In two operations, X[2] = 2, incremented its position by Y[2] = 1 in each operation from position 1 to 2 and then 2 to 3 by using operations one by one.
  • In four operations, X[1] = 3, incremented its position by Y[1] = 1 in each operation from position 0 to 1, 1 to 2, 2 to 3 and then 3 to 4 in last operation. Each operation is performed one by one.
  • Now, It can be verified that all the elements of X[] are in sorted order of their values, for this case Minimum number of operations are=2 + 4 = 6, Which is minimum possible.     

Teset case 1

  

Input: N = 4, X[] = {2, 1, 4, 3}, Y[] = {4, 1, 2, 4}
Output: 5
Explanation: According to the problem statement:

•  X[1] = 2, It’s position can be incremented by Y[1] = 4.
•  X[2] = 1, It’s position can be incremented by Y[2] = 1.
•  X[3] = 4, It’s position can be incremented by Y[3] = 2.
•  X[4] = 3, It’s position can be incremented by Y[4] = 4.
• Operations:
  • In one operation, X[4] = 3, incremented its position by Y[4] = 4, in each operation from position 3 to 7.
  • In one operation, X[1] = 2, incremented its position by Y[1] = 4 in each operation from position 0 to 3.
  • In three operations, X[3] = 4, incremented its position by Y[3] = 2 in each operation from position 2 to 4, 4 to 6 and then 6 to 8 in each operation one by one.
  • Therefore, Total minimum number of operations for this case are= 1 + 1 + 3 = 5. It can be verified that all the elements of X[] are in sorted order of their values after performing above operations.

Test case 2

Approach: Implement the idea below to solve the problem

The problem is observation based and can be solve by using Greedy Technique. The basic idea of the problem is that, we have to choose optimal element to increment it’s position in ach operation.        

Steps were taken to solve the problem:

• Create two arrays positions[] and temp_length[] of length N for storing positions and temporary lengths of elements of X[].
• Create integer variable operations and initialize it equal to 0.
• Initialize positions[] with positions[X[i] – 1] = i,   by using a loop from i=0 to less than N.
• Initialize temp_length[] with temp_lengthX[i] – 1] = Y[i],  by using a loop from i=0 to less than N.
• Iterate from i = 1 to less than N using loops and follow the below-mentioned steps under the scope of the loop:
  • While(position[i] ≤ position[i-1]), till then position[i] += temp_length[i] and operations++.  
• Return operations.  

Below is the code to implement the approach:

Time Complexity: O(N)
Auxiliary Space: O(N)

Given two positive integer arrays X[] and Y[] of size N, Where all elements of X[] are distinct. Considering all the elements of X[] are lying side by side initially on a line, the task is to find the minimum number of operations required such that elements in X[] becomes in increasing order where in one operation you can increase each element of X[] by their respective values index in Y[] (first element of X[] element can be incremented by the first element of Y[] or position of the second element of X[] can be incremented by the second element of Y[] or so on….).

Examples:

Input: N = 3, X[] = {3, 2, 1}, Y[] = {1, 1, 1}
Output: 6
Explanation: According to the problem statement:

• X[1] = 3, It’s position can be incremented by Y[1] = 1.
• X[2] = 2, It’s position can be incremented by Y[2] = 1.
• X[3] = 1, It’s position can be incremented by Y[3] = 1.
• Operations:
  • In two operations, X[2] = 2, incremented its position by Y[2] = 1 in each operation from position 1 to 2 and then 2 to 3 by using operations one by one.
  • In four operations, X[1] = 3, incremented its position by Y[1] = 1 in each operation from position 0 to 1, 1 to 2, 2 to 3 and then 3 to 4 in last operation. Each operation is performed one by one.
  • Now, It can be verified that all the elements of X[] are in sorted order of their values, for this case Minimum number of operations are=2 + 4 = 6, Which is minimum possible.     

Teset case 1

  

Input: N = 4, X[] = {2, 1, 4, 3}, Y[] = {4, 1, 2, 4}
Output: 5
Explanation: According to the problem statement:

•  X[1] = 2, It’s position can be incremented by Y[1] = 4.
•  X[2] = 1, It’s position can be incremented by Y[2] = 1.
•  X[3] = 4, It’s position can be incremented by Y[3] = 2.
•  X[4] = 3, It’s position can be incremented by Y[4] = 4.
• Operations:
  • In one operation, X[4] = 3, incremented its position by Y[4] = 4, in each operation from position 3 to 7.
  • In one operation, X[1] = 2, incremented its position by Y[1] = 4 in each operation from position 0 to 3.
  • In three operations, X[3] = 4, incremented its position by Y[3] = 2 in each operation from position 2 to 4, 4 to 6 and then 6 to 8 in each operation one by one.
  • Therefore, Total minimum number of operations for this case are= 1 + 1 + 3 = 5. It can be verified that all the elements of X[] are in sorted order of their values after performing above operations.

Test case 2

Approach: Implement the idea below to solve the problem

The problem is observation based and can be solve by using Greedy Technique. The basic idea of the problem is that, we have to choose optimal element to increment it’s position in ach operation.        

Steps were taken to solve the problem:

• Create two arrays positions[] and temp_length[] of length N for storing positions and temporary lengths of elements of X[].
• Create integer variable operations and initialize it equal to 0.
• Initialize positions[] with positions[X[i] – 1] = i,   by using a loop from i=0 to less than N.
• Initialize temp_length[] with temp_lengthX[i] – 1] = Y[i],  by using a loop from i=0 to less than N.
• Iterate from i = 1 to less than N using loops and follow the below-mentioned steps under the scope of the loop:
  • While(position[i] ≤ position[i-1]), till then position[i] += temp_length[i] and operations++.  
• Return operations.  

Below is the code to implement the approach:

Time Complexity: O(N)
Auxiliary Space: O(N)