- array-range-queries, Arrays, Mathematical

Minimum absolute value of (K – arr[i]) for all possible values of K over the range [0, N – 1]

Minimum absolute value of (K – arr[i]) for all possible values of K over the range [0, N – 1]Given a positive integer N and a sorted array arr[] consisting of M integers, the task is to find the minimum absolute value of (K – arr[i]) for all possible values of K over the range [0, N – 1].   Examples:Input: N = 5, arr[] = {0, 4}Output: 0 1 2 1 0Explanation:Below are the possible minimum value for all possible values of K over the range [0, N – 1]:K = 0: The minimum value of abs(K – arr[i]) is obtained by considering arr[i] as 0. Therefore, the value is abs(0 – 0) = 0.K = 1: The minimum value of abs(K – arr[i]) is obtained by considering arr[i] as 0. Therefore, the value is abs(1 – 0) = 1.K = 2: The minimum value of abs(K – arr[i]) is obtained by considering arr[i] as 0. Therefore, the value is abs(2 – 0) = 2.K = 3: The minimum value of abs(K – arr[i]) is obtained by considering arr[i] as 4. Therefore, the value is abs(3 – 4) = 1.K = 4: The minimum value of abs(K – arr[i]) is obtained by considering arr[i] as 4. Therefore, the value is abs(4 – 4) = 0.Input: N = 6, arr[] = {0, 1, 4, 5}Output: 0 0 1 1 0 0Approach: The given problem can be solved by choosing the value from the array which is just greater or smaller than the current value of K. Follow the steps below to solve the problem:Initialize a variable, say ind as 0, and a variable, say prev to arr[0] that stores the previously assigned value.Iterate over the range [0, N – 1] using the variable K and perform the following steps:Initialize a variable, say distance to store the minimum absolute value of (K – arr[i]).If the value of i is less than arr[0], then update the value of the distance to (arr[0] – i).Otherwise, if the value of i is at least prev, the value of (ind + 1) is less than the M and the value of i is at most arr[ind + 1], then perform the following steps:Update the value of distance to the minimum of (i – prev) and (arr[ind + 1] – i).If the value of i is equal to arr[ind + 1], then update the value of distance to 0, prev to arr[ind + 1], and increment the value of ind by 1.If the value of i is greater than prev, then update the value of distance to the (i – prev).After completing the above steps, print the value of distance as the minimum absolute value of (K – arr[i]) for the current value of K.Below is the implementation of the above approach:C++  #include using namespace std;  void minimumDistance(vector arr,                     int N){    int ind = 0;    int prev = arr[ind];    int s = arr.size();          for (int i = 0; i < N; i++) {                          int distance = INT_MAX;                          if (i < arr[0]) {            distance = arr[0] - i;        }                          else if (i >= prev && ind + 1 < s                 && i