Reconstruct the array by replacing arr[i] with (arr[i-1]+1) % M

Given an array of N elements and an integer M. Now, the array is modified by replacing some of the array elements with -1. The task is to print the original array.

The elements in the orginal array are related as, for every index i, a[i] = (a[i-1]+1)% M.

It is guaranteed that there is one non zero value in the array.

Examples:

Input: arr[] = {5, -1, -1, 1, 2, 3}, M = 7
Output: 5 6 0 1 2 3
M = 7, so value at index 2 should be (5+1) % 7 = 6
value at index 3 should be (6+1) % 7 = 0

Input: arr[] = {5, -1, 7, -1, 9, 0}, M = 10
Output: 5 6 7 8 9 0

Approach: First find the index of the non negative value index i. Then simply go in two directions i.e. From i-1 to 0 and i+1 to n.

For index i-1 the value can be calculated by (a[i+1]-1+m)%m because (a – b) mod p = ((a mod p – b mod p) + p) mod p.

For indexes i+1 the values can be calculated by (a[i-1]+1)%m.

Below is the implementation of the above approach:

C++

// C++ implemenatation of above approach  #include <bits/stdc++.h>  using namespace std;     void construct(int n, int m, int a[]) {     int ind = 0;        // Finding the index which is not -1     for (int i = 0; i < n; i++)     {         if (a[i] != -1)          {             ind = i;             break;         }     }            // Calculating the values of      // the indexes ind-1 to 0     for (int i = ind - 1; i > -1; i--)     {         if (a[i] == -1)             a[i] = (a[i + 1] - 1 + m) % m;     }            // Calculating the values of     // the indexes ind + 1 to n     for (int i = ind + 1; i < n; i++)      {         if (a[i] == -1)             a[i] = (a[i - 1] + 1) % m;     }     for (int i = 0; i < n; i++)     {         cout<< a[i] << " ";     }    }    // Driver code int main()  {         int n = 6, m = 7;     int a[] = { 5, -1, -1, 1, 2, 3 };     construct(n, m, a);     return 0;  }     // This code is contributed by 29AjayKumar

Java

// Java implementation of the above approach class GFG  {     static void construct(int n, int m, int[] a)     {         int ind = 0;            // Finding the index which is not -1         for (int i = 0; i < n; i++)         {             if (a[i] != -1)              {                 ind = i;                 break;             }         }                    // Calculating the values of          // the indexes ind-1 to 0         for (int i = ind - 1; i > -1; i--)         {             if (a[i] == -1)                 a[i] = (a[i + 1] - 1 + m) % m;         }                    // Calculating the values of         // the indexes ind + 1 to n         for (int i = ind + 1; i < n; i++)          {             if (a[i] == -1)                 a[i] = (a[i - 1] + 1) % m;         }         for (int i = 0; i < n; i++)         {             System.out.print(a[i] + " ");         }        }        // Driver code     public static void main(String[] args)      {         int n = 6, m = 7;         int[] a = { 5, -1, -1, 1, 2, 3 };         construct(n, m, a);     } }    // This code is contributed

Python3

# Python implementation of the above approach def construct(n, m, a):     ind = 0        # Finding the index which is not -1     for i in range(n):         if (a[i]!=-1):             ind = i             break        # Calculating the values of the indexes ind-1 to 0     for i in range(ind-1, -1, -1):         if (a[i]==-1):             a[i]=(a[i + 1]-1 + m)% m        # Calculating the values of the indexes ind + 1 to n     for i in range(ind + 1, n):         if(a[i]==-1):             a[i]=(a[i-1]+1)% m     print(*a)    # Driver code n, m = 6, 7 a =[5, -1, -1, 1, 2, 3] construct(n, m, a)

C#

// C# implementation of the above approach using System;    class GFG  {     static void construct(int n, int m, int[] a)     {         int ind = 0;            // Finding the index which is not -1         for (int i = 0; i < n; i++)         {             if (a[i] != -1)              {                 ind = i;                 break;             }         }                    // Calculating the values of          // the indexes ind-1 to 0         for (int i = ind - 1; i > -1; i--)         {             if (a[i] == -1)                 a[i] = (a[i + 1] - 1 + m) % m;         }                    // Calculating the values of         // the indexes ind + 1 to n         for (int i = ind + 1; i < n; i++)          {             if (a[i] == -1)                 a[i] = (a[i - 1] + 1) % m;         }         for (int i = 0; i < n; i++)         {             Console.Write(a[i] + " ");         }        }        // Driver code     public static void Main(String[] args)      {         int n = 6, m = 7;         int[] a = { 5, -1, -1, 1, 2, 3 };         construct(n, m, a);     } }    // This code is contributed

Output:

5 6 0 1 2 3