Given an array arr[] of N positive integers. The task is to find the index of the elements which are equal to the sum of all succeeding elements. If no such element exists then print -1.
Examples:
Input: arr[] = { 36, 2, 17, 6, 6, 5 }
Output: 0 2
arr[0] = arr[1] + arr[2] + arr[3] + arr[4] + arr[5]
arr[2] = arr[3] + arr[4] + arr[5]
Input: arr[] = {7, 25, 17, 7}
Output: -1
Naive Approach:
Approach: While traversing the given array arr[] from last index, maintain a sum variable that stores the sum of elements traversed till now. Compare the sum with the current element arr[i]. If it is equal, push the index of this element into the answer vector. If the size of the answer vector in the end is 0 then print -1 else print its content.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to find the valid indicesvoid find_idx(int arr[], int n){ // Vector to store the indices vector<int> answer; // Initialise sum with 0 int sum = 0; // Starting from the last element for (int i = n - 1; i >= 0; i--) { // If sum till now is equal to // the current element if (sum == arr[i]) { answer.push_back(i); } // Add current element to the sum sum += arr[i]; } if (answer.size() == 0) { cout << "-1"; return; } for (int i = answer.size() - 1; i >= 0; i--) cout << answer[i] << " ";}// Driver codeint main(){ int arr[] = { 36, 2, 17, 6, 6, 5 }; int n = sizeof(arr) / sizeof(int); find_idx(arr, n); return 0;} |
Java
// Java implementation of the approach import java.util.*;class GFG { // Function to find the valid indices static void find_idx(int arr[], int n) { // Vector to store the indices Vector answer = new Vector(); // Initialise sum with 0 int sum = 0; // Starting from the last element for (int i = n - 1; i >= 0; i--) { // If sum till now is equal to // the current element if (sum == arr[i]) { answer.add(i); } // Add current element to the sum sum += arr[i]; } if (answer.size() == 0) { System.out.println("-1"); return; } for (int i = answer.size() - 1; i >= 0; i--) System.out.print(answer.get(i) + " "); } // Driver code public static void main (String[] args) { int arr[] = { 36, 2, 17, 6, 6, 5 }; int n = arr.length; find_idx(arr, n); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach # Function to find the valid indices def find_idx(arr, n): # List to store the indices answer=[] # Initialise sum with 0 _sum = 0 # Starting from the last element for i in range(n - 1, -1, -1): # If sum till now is equal to # the current element if (_sum == arr[i]) : answer.append(i) # Add current element to the sum _sum += arr[i] if (len(answer) == 0) : print(-1) return for i in range(len(answer) - 1, -1, -1): print(answer[i], end = " ") # Driver code arr = [ 36, 2, 17, 6, 6, 5 ] n = len(arr) find_idx(arr, n)# This code is contributed by# divyamohan123 |
C#
// C# implementation of the approach using System;using System.Collections.Generic;class GFG { // Function to find the valid indices static void find_idx(int[] arr, int n) { // List to store the indices List<int> answer = new List<int>(); // Initialise sum with 0 int sum = 0; // Starting from the last element for (int i = n - 1; i >= 0; i--) { // If sum till now is equal to // the current element if (sum == arr[i]) { answer.Add(i); } // Add current element to the sum sum += arr[i]; } if (answer.Count == 0) { Console.WriteLine("-1"); return; } for (int i = answer.Count - 1; i >= 0; i--) Console.Write(answer[i] + " "); } // Driver code public static void Main (String[] args) { int[] arr = { 36, 2, 17, 6, 6, 5 }; int n = arr.Length; find_idx(arr, n); } }// This code is contributed by Ashutosh450 |
Javascript
<script>// Javascript implementation of the approach// Function to find the valid indicesfunction find_idx(arr, n) { // Vector to store the indices let answer = []; // Initialise sum with 0 let sum = 0; // Starting from the last element for (let i = n - 1; i >= 0; i--) { // If sum till now is equal to // the current element if (sum == arr[i]) { answer.push(i); } // Add current element to the sum sum += arr[i]; } if (answer.length == 0) { document.write("-1"); return; } for (let i = answer.length - 1; i >= 0; i--) document.write(answer[i] + " ");}// Driver codelet arr = [36, 2, 17, 6, 6, 5];let n = arr.length;find_idx(arr, n);// This code is contributed by gfgking</script> |
Output
0 2
Time Complexity: O(n)
Auxiliary Space: O(n), where n is the size of the given array.
Efficient Approach:
Our Approach is simple and we can reduce the space complexity from O(n) to O(1) that is constant space .
Approach:
- Calculate the total sum of the array by using a for loop.
- Initialize a variable sum = 0 and a boolean variable found to false.
- Traverse the array from start to end.
- For each element, check if it is equal to the sum of all the succeeding elements and the remaining elements.
a. If the condition is true, print the index of the current element and set found to true.
b. Update the sum variable to include the current element. - If no element is found, then print -1.
Implementation:
C++
#include <bits/stdc++.h>using namespace std;void findIndexes(int arr[], int n) { int total = 0; // calculate total sum of array for(int i=0;i<n;i++) { total+=arr[i]; } int sum = 0; bool found = false; for (int i = 0; i < n; i++) { if (arr[i] == total - sum - arr[i]) { // check if current element is equal to sum of succeeding elements cout << i << " "; found = true; } sum += arr[i]; // updatesum } if (!found) cout << "-1"; // if no element found, print -1}int main() { int arr[] = { 36, 2, 17, 6, 6, 5 }; int n = sizeof(arr) / sizeof(arr[0]); findIndexes(arr, n); return 0;} |
Java
public class Main { public static void findIndexes(int[] arr) { int total = 0; // Calculate the total sum of the array for (int i = 0; i < arr.length; i++) { total += arr[i]; } int sum = 0; boolean found = false; for (int i = 0; i < arr.length; i++) { // Check if the current element is equal to the sum of succeeding elements if (arr[i] == total - sum - arr[i]) { System.out.print(i + " "); found = true; } sum += arr[i]; // Update the sum } if (!found) { System.out.print("-1"); // If no element found, print -1 } } public static void main(String[] args) { int[] arr = { 36, 2, 17, 6, 6, 5 }; findIndexes(arr); }} |
C#
using System;class Program{ static void FindIndexes(int[] arr, int n) { int total = 0; // Calculate the total sum of the array for (int i = 0; i < n; i++) { total += arr[i]; } int sum = 0; bool found = false; for (int i = 0; i < n; i++) { if (arr[i] == total - sum - arr[i]) { // Check if the current element is equal to the sum of succeeding elements Console.Write(i + " "); found = true; } sum += arr[i]; // Update the sum } if (!found) { Console.Write("-1"); // If no element is found, print -1 } } static void Main(string[] args) { int[] arr = { 36, 2, 17, 6, 6, 5 }; int n = arr.Length; FindIndexes(arr, n); }} |
Output
0 2
Time Complexity: O(n), where n is the size of the given array.
Space Complexity: O(1), no extra space is used .
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
