# Minimum number of decrements by 1 required to reduce all elements of a circular array to 0

Given an circular array **arr[]** consisting of **N** integers, the task is to find the minimum number of operations to reduce all elements of a circular array to **0**. In each operation, reduce the current element by **1** (*starting from the first element*) and move to the next element.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:arr[] = {2, 0, 2}Output:6Explanation:

Following are the operations performed:

- Reduce the array element arr[0] by 1 modifies the array to {
1, 0, 2} and move to the next element arr[1].- Do nothing and move to the next element i.e., arr[2].
- Reduce the array element arr[2] by 1 modifies the array to {1, 0,
1} and move to the next element arr[0].- Reduce the array element arr[0] by 1 modifies the array to {
0, 0, 1} and move to the next element arr[1].- Do nothing and move to the next element i.e., arr[2].
- Reduce the array element arr[2] by 1 modifies the array to {0, 0,
0} and move to the next element arr[0].After the above operations, all the array elements of the circular array has been reduced to 0. Therefore, the minimum number of operations required is 6.

Input:arr[] = {0, 3, 1, 3, 2}Output:14

**Naive Approach:** The simplest approach to solve the given problem is to traverse the given array in a circular order by performing the given operations until all the array elements is **0** and keep the track of count of operations performed. After completing the above steps, print the number of operations performed.

**Time Complexity:** O(N*M), where **M** is the *maximum element of the array**.***Auxiliary Space:** O(1)

**Efficient Approach:** The above approach can also be optimized by finding the last index of the maximum array element and find the minimum number of operations required accordingly. Follow the steps below to solve the problem:

- Initialize two variables, say
**pos**and**M**that stores the last index of the maximum element and maximum element respectively. - Traverse the given array using the variable
**i**and if the value of**arr[i]**is at least**M**, then modify the value of**M**as**arr[i]**and**pos**as**i**. - After completing the above steps, print the value of
**(mx – 1)*N + pos +1**as the resultant minimum number of steps.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find minimum operation` `// require to make all elements 0` `void` `minimumOperations(` `int` `arr[], ` `int` `N)` `{` ` ` `// Stores the maximum element and` ` ` `// its position in the array` ` ` `int` `mx = 0, pos = 0;` ` ` `// Traverse the array` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `// Update the maximum element` ` ` `// and its index` ` ` `if` `(arr[i] >= mx) {` ` ` `mx = arr[i];` ` ` `pos = i;` ` ` `}` ` ` `}` ` ` `// Print the minimum number of` ` ` `// operations required` ` ` `cout << (mx - 1) * N + pos + 1;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `arr[] = { 2, 0, 2 };` ` ` `int` `N = ` `sizeof` `(arr) / ` `sizeof` `(arr[0]);` ` ` `minimumOperations(arr, N);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.io.*;` `class` `GFG {` ` ` `// Function to find minimum operation` ` ` `// require to make all elements 0` ` ` `static` `void` `minimumOperations(` `int` `arr[], ` `int` `N)` ` ` `{` ` ` `// Stores the maximum element and` ` ` `// its position in the array` ` ` `int` `mx = ` `0` `, pos = ` `0` `;` ` ` `// Traverse the array` ` ` `for` `(` `int` `i = ` `0` `; i < N; i++) {` ` ` `// Update the maximum element` ` ` `// and its index` ` ` `if` `(arr[i] >= mx) {` ` ` `mx = arr[i];` ` ` `pos = i;` ` ` `}` ` ` `}` ` ` `// Print the minimum number of` ` ` `// operations required` ` ` `System.out.println((mx - ` `1` `) * N + pos + ` `1` `);` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main (String[] args)` ` ` `{` ` ` `int` `arr[] = { ` `2` `, ` `0` `, ` `2` `};` ` ` `int` `N = arr.length;` ` ` `minimumOperations(arr, N);` ` ` `}` `}` `// This code is contributed by Potta Lokesh` |

## Python3

`# Python3 program for the above approach` `# Function to find minimum operation` `# require to make all elements 0` `def` `minimumOperations(arr, N):` ` ` ` ` `# Stores the maximum element and` ` ` `# its position in the array` ` ` `mx ` `=` `0` ` ` `pos ` `=` `0` ` ` `# Traverse the array` ` ` `for` `i ` `in` `range` `(N):` ` ` ` ` `# Update the maximum element` ` ` `# and its index` ` ` `if` `(arr[i] >` `=` `mx):` ` ` `mx ` `=` `arr[i]` ` ` `pos ` `=` `i` ` ` `# Print the minimum number of` ` ` `# operations required` ` ` `print` `((mx ` `-` `1` `) ` `*` `N ` `+` `pos ` `+` `1` `)` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` ` ` `arr ` `=` `[ ` `2` `, ` `0` `, ` `2` `]` ` ` `N ` `=` `len` `(arr)` ` ` ` ` `minimumOperations(arr, N)` `# This code is contributed by SURENDRA_GANGWAR` |

## C#

`// C# program for the above approach` `using` `System;` `class` `GFG{` ` ` `// Function to find minimum operation` ` ` `// require to make all elements 0` ` ` `static` `void` `minimumOperations(` `int` `[] arr, ` `int` `N)` ` ` `{` ` ` `// Stores the maximum element and` ` ` `// its position in the array` ` ` `int` `mx = 0, pos = 0;` ` ` `// Traverse the array` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `// Update the maximum element` ` ` `// and its index` ` ` `if` `(arr[i] >= mx) {` ` ` `mx = arr[i];` ` ` `pos = i;` ` ` `}` ` ` `}` ` ` `// Print the minimum number of` ` ` `// operations required` ` ` `Console.Write((mx - 1) * N + pos + 1);` ` ` `}` `// Driver Code` `public` `static` `void` `Main()` `{` ` ` `int` `[] arr = { 2, 0, 2 };` ` ` `int` `N = arr.Length;` ` ` `minimumOperations(arr, N);` `}` `}` `// This code is contributed by splevel62.` |

## Javascript

`<script>` `// JavaScript code for above approach` ` ` `// Function to find minimum operation` ` ` `// require to make all elements 0` ` ` `function` `minimumOperations(arr, N)` ` ` `{` ` ` `// Stores the maximum element and` ` ` `// its position in the array` ` ` `let mx = 0, pos = 0;` ` ` `// Traverse the array` ` ` `for` `(let i = 0; i < N; i++) {` ` ` `// Update the maximum element` ` ` `// and its index` ` ` `if` `(arr[i] >= mx) {` ` ` `mx = arr[i];` ` ` `pos = i;` ` ` `}` ` ` `}` ` ` `// Print the minimum number of` ` ` `// operations required` ` ` `document.write((mx - 1) * N + pos + 1);` ` ` `}` `// Driver Code` ` ` `let arr = [ 2, 0, 2 ];` ` ` `let N = arr.length;` ` ` `minimumOperations(arr, N);` ` ` ` ` `// This code is contributed by sanjoy_62.` `</script>` |

**Output:**

6

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