Find the index in a circular array from which prefix sum is always non-negative

Find the index in a circular array from which prefix sum is always non-negative

Given a circular array arr[] consisting of N integers, the task is to find the starting index of the circular array such that the prefix sum from that index is always non-negative. If there exists no such index, then print “-1”.

Examples:

Input: arr[] = {3, -6, 7, -1, -4, 5, -1}
Output: 2
Explanation:
Consider the index 2 from where the prefix sum of the given circular array is being calculated, then the prefix sum is given by {9, 3, 7, 6, 2, 7, 6}

Input: arr[] = {3, -5, -1}
Output: -1

Approach: The given problem can be solved based on the following observations:

Follow the steps to solve the problem:

• Initialize a variable, say sum as 0, that stores the sum of array elements.
• Initialize a variable, say in as 0 that stores the starting index for the circular traversal.
• Initialize a variable, say min as INT_MAX that stores the minimum prefix sum of the array arr[].
• Traverse the given array and perform the following steps:
  • Update the value of sum as the sum of sum and the current element arr[i].
  • If the value of sum is less than min, then update the min as sum and in as (i + 1).
• If the sum of the array is negative, then print -1. Otherwise, print the value of (in % N) as the resultant possible index.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    int startingPoint(int A[], int N) {          int sum = 0;             int in = 0;                  int min = INT_MAX;             for (int i = 0; i < N; i++) {                     sum += A[i];                     if (sum < min) {                                          min = sum;                             in = i + 1;         }     }                  if (sum < 0) {         return -1;     }        return in % N; }    int main() {     int arr[] = { 3, -6, 7, -4, -4, 6, -1 };     int N = (sizeof(arr) / sizeof(arr[0]));     cout << startingPoint(arr, N);        return 0; }

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

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets