Encuentre la secuencia inicial que produce una array dada por incrementos cíclicos hasta el índice P

Dada una array arr[] que consta de N elementos y un número entero P , la tarea es encontrar la array inicial a partir de la cual se produce la array dada mediante las siguientes operaciones: 

• Se selecciona un elemento arr[i] de la array inicial. El i ^-ésimo índice se reduce a 0 .
• Los índices arr[i] aumentan en 1 de manera cíclica, de modo que el último índice que se incrementa es P .

Ejemplos: 

Entrada: arr[] = {4, 3, 1, 6}, P = 4 
Salida: 3 2 5 4 
Explicación: 
El elemento arr[2] se elige de la array inicial. Las siguientes operaciones arr[i] modifican la array dada en la siguiente secuencia: 
{3, 2, 0, 4} -> {3, 2, 0, 5} -> {4, 2, 0, 5} -> { 4, 3, 0, 5} -> {4, 3, 1, 5} -> {4, 3, 1, 6}
Entrada: arr[] = {3, 2, 0, 2, 7}, P = 2 
Salida: 2 1 4 1 6 
 

Enfoque: el problema anterior se puede resolver siguiendo los pasos a continuación:  

1. Encuentre el elemento mínimo en la array y reste min – 1 de cada índice.
2. Ahora comience a restar 1 del (P – 1) ^ésimo índice y repita para todos los índices de la izquierda de manera cíclica hasta que un índice se convierta en 0.
3. Agregue el número de operaciones a ese índice.
4. El estado actual de arr[] da el estado inicial requerido. Imprime la array.

A continuación se muestra la implementación del enfoque anterior: 

// C++ program to implement the
// above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to generate and return the
// required initial arrangement
void findArray(int* a,
               int n,
               int P)
{
    // Store the minimum element
    // in the array
    int mi = *min_element(a, a + n);
 
    // Store the number of increments
    int ctr = 0;
    mi = max(0, mi - 1);
 
    // Subtract mi - 1 from every index
    for (int i = 0; i < n; i++) {
 
        a[i] -= mi;
 
        ctr += mi;
    }
 
    // Start from the last index which
    // had been incremented
    int i = P - 1;
 
    // Stores the index chosen to
    // distribute its element
    int start = -1;
 
    // Traverse the array cyclically and
    // find the index whose element was
    // distributed
    while (1) {
 
        // If any index has its
        // value reduced to 0
        if (a[i] == 0) {
 
            // Index whose element was
            // distributed
            start = i;
 
            break;
        }
 
        a[i] -= 1;
        ctr += 1;
        i = (i - 1 + n) % n;
    }
 
    // Store the number of increments
    // at the starting index
    a[start] = ctr;
 
    // Print the original array
    for (int i = 0; i < n; i++) {
        cout << a[i] << ", ";
    }
}
 
// Driver Code
int main()
{
    int N = 5;
    int P = 2;
 
    int arr[] = { 3, 2, 0, 2, 7 };
 
    findArray(arr, N, P);
 
    return 0;
}

// Java program to implement the
// above approach
import java.util.*;
 
class GFG{
 
// Function to generate and return the
// required initial arrangement
static void findArray(int []a, int n,
                               int P)
{
     
    // Store the minimum element
    // in the array
    int mi = Arrays.stream(a).min().getAsInt();
 
    // Store the number of increments
    int ctr = 0;
    mi = Math.max(0, mi - 1);
 
    // Subtract mi - 1 from every index
    for(int i = 0; i < n; i++)
    {
        a[i] -= mi;
        ctr += mi;
    }
 
    // Start from the last index which
    // had been incremented
    int i = P - 1;
 
    // Stores the index chosen to
    // distribute its element
    int start = -1;
 
    // Traverse the array cyclically and
    // find the index whose element was
    // distributed
    while (true)
    {
 
        // If any index has its
        // value reduced to 0
        if (a[i] == 0)
        {
 
            // Index whose element was
            // distributed
            start = i;
            break;
        }
        a[i] -= 1;
        ctr += 1;
        i = (i - 1 + n) % n;
    }
 
    // Store the number of increments
    // at the starting index
    a[start] = ctr;
 
    // Print the original array
    for(i = 0; i < n; i++)
    {
        System.out.print(a[i] + ", ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 5;
    int P = 2;
    int arr[] = { 3, 2, 0, 2, 7 };
 
    findArray(arr, N, P);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program to implement
# the above approach
 
# Function to generate and return the
# required initial arrangement
def findArray(a, n, P):
 
    # Store the minimum element
    # in the array
    mi = min(a)
 
    # Store the number of increments
    ctr = 0
    mi = max(0, mi - 1)
 
    # Subtract mi - 1 from every index
    for i in range(n):
        a[i] -= mi
        ctr += mi
 
    # Start from the last index which
    # had been incremented
    i = P - 1
 
    # Stores the index chosen to
    # distribute its element
    start = -1
 
    # Traverse the array cyclically and
    # find the index whose element was
    # distributed
    while (1):
 
        # If any index has its
        # value reduced to 0
        if (a[i] == 0):
 
            # Index whose element was
            # distributed
            start = i
            break
 
        a[i] -= 1
        ctr += 1
        i = (i - 1 + n) % n
 
    # Store the number of increments
    # at the starting index
    a[start] = ctr
 
    # Print the original array
    print(*a, sep = ', ')
 
# Driver Code
if __name__ == '__main__':
 
    N = 5
    P = 2
 
    arr = [ 3, 2, 0, 2, 7 ]
 
    findArray(arr, N, P)
 
# This code is contributed by himanshu77

// C# program to implement the
// above approach
using System;
using System.Linq;
class GFG{
 
// Function to generate and return the
// required initial arrangement
static void findArray(int []a, int n,
                               int P)
{
     
    // Store the minimum element
    // in the array
    int mi = a.Min();
 
    // Store the number of increments
    int ctr = 0;
    mi = Math.Max(0, mi - 1);
 
    // Subtract mi - 1 from every index
    int i;
    for(i = 0; i < n; i++)
    {
        a[i] -= mi;
        ctr += mi;
    }
 
    // Start from the last index which
    // had been incremented
     i = P - 1;
 
    // Stores the index chosen to
    // distribute its element
    int start = -1;
 
    // Traverse the array cyclically and
    // find the index whose element was
    // distributed
    while (true)
    {
 
        // If any index has its
        // value reduced to 0
        if (a[i] == 0)
        {
 
            // Index whose element was
            // distributed
            start = i;
            break;
        }
        a[i] -= 1;
        ctr += 1;
        i = (i - 1 + n) % n;
    }
 
    // Store the number of increments
    // at the starting index
    a[start] = ctr;
 
    // Print the original array
    for(i = 0; i < n; i++)
    {
        Console.Write(a[i] + ", ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 5;
    int P = 2;
    int []arr = { 3, 2, 0, 2, 7 };
 
    findArray(arr, N, P);
}
}
 
// This code is contributed by Rohit_ranjan

<script>
// Javascript implementation for the above approach
 
// Function to generate and return the
// required initial arrangement
function findArray(a, n, P)
{
     
    // Store the minimum element
    // in the array
    let mi = Math.min(...a);
 
    // Store the number of increments
    let ctr = 0;
    mi = Math.max(0, mi - 1);
 
    // Subtract mi - 1 from every index
    for(let i = 0; i < n; i++)
    {
        a[i] -= mi;
        ctr += mi;
    }
 
    // Start from the last index which
    // had been incremented
    let i = P - 1;
 
    // Stores the index chosen to
    // distribute its element
    let start = -1;
 
    // Traverse the array cyclically and
    // find the index whose element was
    // distributed
    while (true)
    {
 
        // If any index has its
        // value reduced to 0
        if (a[i] == 0)
        {
 
            // Index whose element was
            // distributed
            start = i;
            break;
        }
        a[i] -= 1;
        ctr += 1;
        i = (i - 1 + n) % n;
    }
 
    // Store the number of increments
    // at the starting index
    a[start] = ctr;
 
    // Print the original array
    for(i = 0; i < n; i++)
    {
        document.write(a[i] + ", ");
    }
}
 
    // Driver Code
     
    let N = 5;
    let P = 2;
    let arr = [ 3, 2, 0, 2, 7 ];
 
    findArray(arr, N, P);
         
</script>

2, 1, 4, 1, 6,

Complejidad temporal: O(N)  
Espacio auxiliar: O(1)