Find all indices of Array having prefix sum greater than suffix sum
Given an array arr[] of N integers, the task is to divide find all the indices such that prefix sum (i.e. sum of elements in range [0, i)) is greater than the suffix sum (elements in the range [i, N-1])
Examples:
Input: arr = [10, -3, 4, 6]
Output: [1, 3]
Explanation: Consider index 1. Prefix sum = 10, suffix sum = 7, i.e. (10 > 7)
Consider index 3. Prefix sum = 11, suffix sum = 6, i.e(11 > 6)Input: arr = [-2, -3, -4, 10]
Output: []
Explanation: There is no index such that prefix sum is greater than suffix sum.
Naive Approach: The basic idea is to consider each index and calculate the prefix and suffix sum for that index. If the prefix sum is greater than the suffix sum, then insert this index into the answer.
Algorithm:
- Initialize an empty list named ‘ans’ to store the valid indices.
- Iterate through each index i from 0 to n-2, where n is the size of the input array ‘arr’.
- Calculate the left sum and right sum of the input array ‘arr’.
- The left sum is the sum of all elements from the 0th index to the ith index inclusive.
- The right sum is the sum of all elements from the (i+1)th index to the (n-1)th index inclusive.
- Check if the left sum is greater than the right sum, then append the index i+1 to the ‘ans’ list.
- Return the ‘ans’ list containing all valid indices.
Note: The algorithm assumes that the input array ‘arr’ contains at least two elements. If the size of the input array is less than 2, the function will return an empty list.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the valid indices vector< int > solve(vector< int >& arr) { vector< int > ans; // Total_size of the array int size = arr.size(); // Upto second last index for ( int idx = 0; idx < size - 1; ++idx) { int left_sum = 0; int right_sum = 0; // Calculate left sum for ( int left_idx = 0; left_idx < idx + 1; ++left_idx) { left_sum += arr[left_idx]; } // Calculate right sum for ( int right_idx = idx + 1; right_idx < size; ++right_idx) { right_sum += arr[right_idx]; } // Check condition if (left_sum > right_sum) ans.push_back(idx + 1); } return ans; } // Driver code int main() { vector< int > arr = { 10, -3, 4, 6 }; vector< int > ans = solve(arr); for ( auto x : ans) cout << x << " " ; return 0; } // This code is contributed by Pushpesh Raj |
Java
/*package whatever //do not write package name here */ import java.io.*; import java.util.ArrayList; import java.util.Arrays; class GFG { // Function to find the valid indices public static ArrayList<Integer>solve(ArrayList<Integer>arr) { ArrayList<Integer>ans = new ArrayList<Integer>(); // Total_size of the array int size = arr.size(); // Upto second last index for ( int idx = 0 ; idx < size - 1 ; ++idx) { int left_sum = 0 ; int right_sum = 0 ; // Calculate left sum for ( int left_idx = 0 ; left_idx < idx + 1 ;++left_idx) { left_sum += arr.get(left_idx); } // Calculate right sum for ( int right_idx = idx + 1 ; right_idx < size; ++right_idx) { right_sum += arr.get(right_idx); } // Check condition if (left_sum > right_sum) ans.add(idx + 1 ); } return ans; } public static void main (String[] args) { // Given Input ArrayList<Integer>arr = new ArrayList<Integer>(Arrays.asList( 10 , - 3 , 4 , 6 )); ArrayList<Integer>ans = solve(arr); for ( int x : ans){ System.out.print(x); System.out.print( " " ); } } } // This code is contributed by shinjanpatra |
Python3
# Python code to implement the above approach class Solution: # Function to find the indices def solve( self , arr): ans = [] # Total_size of the array size = len (arr) # Upto second last index for idx in range (size - 1 ): left_sum = 0 right_sum = 0 # Calculate left sum for left_idx in range (idx + 1 ): left_sum + = arr[left_idx] # Calculate right sum for right_idx in range (idx + 1 , size, 1 ): right_sum + = arr[right_idx] # check condition if (left_sum > right_sum): ans.append(idx + 1 ) return (ans) # Driver code if __name__ = = '__main__' : obj = Solution() arr = [ 10 , - 3 , 4 , 6 ] ans = obj.solve(arr) for x in ans: print (x, end = " " ) |
C#
// C# program to implement above approach using System; using System.Collections.Generic; class GFG { // Function to find the valid indices public static List< int > solve(List< int > arr) { List< int > ans = new List< int >(); // Total_size of the array int size = arr.Count; // Upto second last index for ( int idx = 0 ; idx < size - 1 ; ++idx) { int left_sum = 0; int right_sum = 0; // Calculate left sum for ( int left_idx = 0 ; left_idx < idx + 1 ; ++left_idx) { left_sum += arr[left_idx]; } // Calculate right sum for ( int right_idx = idx + 1 ; right_idx < size ; ++right_idx) { right_sum += arr[right_idx]; } // Check condition if (left_sum > right_sum){ ans.Add(idx+1); } } return ans; } // Driver Code public static void Main( string [] args) { // Input Array List< int > arr = new List< int >{ 10, -3, 4, 6 }; List< int > ans = solve(arr); foreach ( var x in ans){ Console.Write(x + " " ); } } } // This code is contributed by subhamgoyal2014. |
Javascript
<script> // JavaScript code to implement the above approach // Function to find the indices function solve(arr){ let ans = [] // Total_size of the array let size = arr.length // Upto second last index for (let idx = 0; idx < size - 1; idx++){ let left_sum = 0 let right_sum = 0 // Calculate left sum for (let left_idx = 0; left_idx < idx + 1; left_idx++) left_sum += arr[left_idx] // Calculate right sum for (let right_idx = idx + 1; right_idx < size; right_idx++) right_sum += arr[right_idx] // check condition if (left_sum > right_sum) ans.push(idx + 1) } return ans } // Driver code let arr = [10, -3, 4, 6] let ans = solve(arr) for (let x of ans) document.write(x, " " ) // This code is contributed by shinjanpatra </script> |
1 3
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The idea is to calculate the overall sum of the given array and traverse over the array and keep calculating the prefix sum into some variable and suffix sum can be calculate by using formula suffix sum = totalSum – prefix sum. Then check if the prefix sum is equals to the suffix sum or not. If it is equal then keep storing into some data structure for result.
Follow the steps below to implement the above idea:
- Calculate the overall sum in total_sum variable.
- Iterate over the given array arr and following the steps below:
- Keep adding the current element into left_sum variable for prefix sum.
- Calculate suffix sum using formula right_sum= total_sum- left_sum.
- Check if the left_sumis greater than the suffixSum:
- If greater, then store the current index into ansarray.
- Return the ans array.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the valid indices vector< int > solve(vector< int >& arr) { vector< int > ans; // Total_size of the array int size = arr.size(); int left_sum = 0; int total_sum = 0; for ( auto dt : arr) total_sum += dt; // Upto second last index for ( int idx = 0; idx < size - 1; ++idx) { // Add current element to // left_sum left_sum += arr[idx]; // Calculate right_sum int right_sum = total_sum - left_sum; // Check condition if (left_sum > right_sum) ans.push_back(idx + 1); } return (ans); } // Driver code int main() { vector< int > arr = { 10, -3, 4, 6 }; vector< int > ans = solve(arr); for ( auto x : ans) cout << x << " " ; return 0; } // This code is contributed by rakeshsahnis |
Java
// Java code to implement the approach import java.util.*; class GFG { // Function to find the valid indices static List<Integer> solve( int arr[]) { List<Integer> ans = new ArrayList<Integer>(); // Total_size of the array int size = arr.length; int left_sum = 0 ; int total_sum = 0 ; for ( int i = 0 ; i < size; i++){ total_sum += arr[i]; } // Upto second last index for ( int idx = 0 ; idx < size - 1 ; ++idx) { // Add current element to // left_sum left_sum += arr[idx]; // Calculate right_sum int right_sum = total_sum - left_sum; // Check condition if (left_sum > right_sum) ans.add(idx + 1 ); } return ans; } // Driver code public static void main (String[] args) { int arr[] = { 10 , - 3 , 4 , 6 }; List<Integer> ans = solve(arr); for (Integer x : ans) System.out.print(x + " " ); } } // This code is contributed by hrithikgarg03188. |
Python3
# Python code to implement the approach class Solution: # Function to find the valid indices def solve( self , arr): ans = [] # Total_size of the array size = len (arr) left_sum = 0 total_sum = sum (arr) # Upto second last index for idx in range (size - 1 ): # Add current element to # left_sum left_sum + = arr[idx] # Calculate right_sum right_sum = total_sum - left_sum # Check condition if (left_sum > right_sum): ans.append(idx + 1 ) return (ans) # Driver code if __name__ = = '__main__' : obj = Solution() arr = [ 10 , - 3 , 4 , 6 ] ans = obj.solve(arr) for x in ans: print (x, end = " " ) |
C#
// C# code to implement the approach using System; using System.Collections; class GFG { // Function to find the valid indices static ArrayList solve( int [] arr) { ArrayList ans = new ArrayList(); // Total_size of the array int size = arr.Length; int left_sum = 0; int total_sum = 0; for ( int i = 0; i < size; i++) { total_sum += arr[i]; } // Upto second last index for ( int idx = 0; idx < size - 1; ++idx) { // Add current element to // left_sum left_sum += arr[idx]; // Calculate right_sum int right_sum = total_sum - left_sum; // Check condition if (left_sum > right_sum) ans.Add(idx + 1); } return ans; } // Driver code public static void Main() { int [] arr = { 10, -3, 4, 6 }; ArrayList ans = solve(arr); foreach ( int x in ans) Console.Write(x + " " ); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the valid indices function solve(arr) { let ans = new Array(); // Total_size of the array let size = arr.length; let left_sum = 0; let total_sum = 0; for (let i = 0; i < size; i++){ total_sum += arr[i]; } // Upto second last index for (let idx = 0; idx < size - 1; ++idx) { // Add current element to // left_sum left_sum += arr[idx]; // Calculate right_sum let right_sum = total_sum - left_sum; // Check condition if (left_sum > right_sum) ans.push(idx + 1); } return ans; } // Driver Code let arr = [10, -3, 4, 6 ]; let ans = solve(arr); for (let x in ans){ document.write(ans[x] + " " ); } // This code is contributed by code_hunt. </script> |
1 3
Time Complexity: O(N), Where N is the size of the given array
Auxiliary Space: O(N)
Contact Us