Given an array arr[] consisting of N elements and an integer P, the task is to find the initial array from which given arr[] is produced by the following operations:
- An element arr[i] from the initial array is selected. The ith index is reduced to 0.
- arr[i] indices are increased by 1 in a cyclic manner such that the last index to be incremented is P.
Examples:
Input: arr[] = {4, 3, 1, 6}, P = 4
Output: 3 2 5 4
Explanation:
The element arr[2] is chosen from the initial array. The following arr[i] operations modifies the given array in the following sequence:
{3, 2, 0, 4} -> {3, 2, 0, 5} -> {4, 2, 0, 5} -> {4, 3, 0, 5} -> {4, 3, 1, 5} -> {4, 3, 1, 6}
Input: arr[] = {3, 2, 0, 2, 7}, P = 2
Output: 2 1 4 1 6
Approach: The above problem can be solved using the below steps:
- Find the minimum element in the array and subtract min – 1 from every index.
- Now start subtracting 1 from the (P – 1)th index and repeat for all indices on the left in a cyclic manner until an index becomes 0.
- Add the number of operations to that index.
- The current state of arr[] gives the required initial state. Print the array.
Below is the implementation of the above approach:
C++
// C++ program to implement the// above approach#include <bits/stdc++.h>using namespace std;// Function to generate and return the// required initial arrangementvoid 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 Codeint main(){ int N = 5; int P = 2; int arr[] = { 3, 2, 0, 2, 7 }; findArray(arr, N, P); return 0;} |
Java
// Java program to implement the// above approachimport java.util.*;class GFG{// Function to generate and return the// required initial arrangementstatic 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 Codepublic 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
# Python3 program to implement# the above approach# Function to generate and return the# required initial arrangementdef 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 Codeif __name__ == '__main__': N = 5 P = 2 arr = [ 3, 2, 0, 2, 7 ] findArray(arr, N, P)# This code is contributed by himanshu77 |
C#
// C# program to implement the// above approachusing System;using System.Linq;class GFG{// Function to generate and return the// required initial arrangementstatic 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 Codepublic 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 |
Javascript
<script>// Javascript implementation for the above approach// Function to generate and return the// required initial arrangementfunction 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> |
Output:
2, 1, 4, 1, 6,
Time Complexity: O(N)
Auxiliary Space: O(1)
