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++
#include <bits/stdc++.h>
using namespace std;
void find_idx( int arr[], int n)
{
vector< int > answer;
int sum = 0;
for ( int i = n - 1; i >= 0; i--) {
if (sum == arr[i]) {
answer.push_back(i);
}
sum += arr[i];
}
if (answer.size() == 0) {
cout << "-1" ;
return ;
}
for ( int i = answer.size() - 1; i >= 0; i--)
cout << answer[i] << " " ;
}
int main()
{
int arr[] = { 36, 2, 17, 6, 6, 5 };
int n = sizeof (arr) / sizeof ( int );
find_idx(arr, n);
return 0;
}
|
Java
import java.util.*;
class GFG
{
static void find_idx( int arr[], int n)
{
Vector answer = new Vector();
int sum = 0 ;
for ( int i = n - 1 ; i >= 0 ; i--)
{
if (sum == arr[i])
{
answer.add(i);
}
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) + " " );
}
public static void main (String[] args)
{
int arr[] = { 36 , 2 , 17 , 6 , 6 , 5 };
int n = arr.length;
find_idx(arr, n);
}
}
|
Python3
def find_idx(arr, n):
answer = []
_sum = 0
for i in range (n - 1 , - 1 , - 1 ):
if (_sum = = arr[i]) :
answer.append(i)
_sum + = arr[i]
if ( len (answer) = = 0 ) :
print ( - 1 )
return
for i in range ( len (answer) - 1 , - 1 , - 1 ):
print (answer[i], end = " " )
arr = [ 36 , 2 , 17 , 6 , 6 , 5 ]
n = len (arr)
find_idx(arr, n)
|
C#
using System;
using System.Collections.Generic;
class GFG
{
static void find_idx( int [] arr, int n)
{
List< int > answer = new List< int >();
int sum = 0;
for ( int i = n - 1; i >= 0; i--)
{
if (sum == arr[i])
{
answer.Add(i);
}
sum += arr[i];
}
if (answer.Count == 0)
{
Console.WriteLine( "-1" );
return ;
}
for ( int i = answer.Count - 1; i >= 0; i--)
Console.Write(answer[i] + " " );
}
public static void Main (String[] args)
{
int [] arr = { 36, 2, 17, 6, 6, 5 };
int n = arr.Length;
find_idx(arr, n);
}
}
|
Javascript
<script>
function find_idx(arr, n) {
let answer = [];
let sum = 0;
for (let i = n - 1; i >= 0; i--) {
if (sum == arr[i]) {
answer.push(i);
}
sum += arr[i];
}
if (answer.length == 0) {
document.write( "-1" );
return ;
}
for (let i = answer.length - 1; i >= 0; i--)
document.write(answer[i] + " " );
}
let arr = [36, 2, 17, 6, 6, 5];
let n = arr.length;
find_idx(arr, n);
</script>
|
Time Complexity: O(n)
Auxiliary Space: O(n), where n is the size of the given array.
Our Approach is simple and we can reduce the space complexity from O(n) to O(1) that is constant space .
- 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.
C++
#include <bits/stdc++.h>
using namespace std;
void findIndexes( int arr[], int n) {
int total = 0;
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]) {
cout << i << " " ;
found = true ;
}
sum += arr[i];
}
if (!found) cout << "-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 ;
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++) {
if (arr[i] == total - sum - arr[i]) {
System.out.print(i + " " );
found = true ;
}
sum += arr[i];
}
if (!found) {
System.out.print( "-1" );
}
}
public static void main(String[] args) {
int [] arr = { 36 , 2 , 17 , 6 , 6 , 5 };
findIndexes(arr);
}
}
|
Python3
def find_indexes(arr):
total = sum (arr)
sum_val = 0
found = False
for i in range ( len (arr)):
if arr[i] = = total - sum_val - arr[i]:
print (i, end = " " )
found = True
sum_val + = arr[i]
if not found:
print ( "-1" )
if __name__ = = "__main__" :
arr = [ 36 , 2 , 17 , 6 , 6 , 5 ]
find_indexes(arr)
|
C#
using System;
class Program
{
static void FindIndexes( int [] arr, int n)
{
int total = 0;
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])
{
Console.Write(i + " " );
found = true ;
}
sum += arr[i];
}
if (!found)
{
Console.Write( "-1" );
}
}
static void Main( string [] args)
{
int [] arr = { 36, 2, 17, 6, 6, 5 };
int n = arr.Length;
FindIndexes(arr, n);
}
}
|
Javascript
function findIndexes(arr) {
let n = arr.length;
let total = 0;
for (let i = 0; i < n; i++) {
total += arr[i];
}
let sum = 0;
let found = false ;
for (let i = 0; i < n; i++) {
if (arr[i] === total - sum - arr[i]) {
process.stdout.write(i + " " );
found = true ;
}
sum += arr[i];
}
if (!found) {
process.stdout.write( "-1" );
}
}
function main() {
const arr = [36, 2, 17, 6, 6, 5];
findIndexes(arr);
}
main();
|
Time Complexity: O(n), where n is the size of the given array.
Space Complexity: O(1), no extra space is used .
Contact Us