Find all good indices in the given Array
Given an array A[] of integers. The task is to print all indices of this array such that after removing the ith element from the array, the array becomes a good array.
Note:
- An array is good if there is an element in the array that equals to the sum of all other elements.
- 1-based indexing is considered for the array.
Examples:
Input : A[] = { 8, 3, 5, 2 }
Output : 1 4
Explanation: A[] = [8, 3, 5, 2]
If you remove A[1], the array will look like [3, 5, 2] and it is good, since 5 = 3+2.
If you remove A[4], the array will look like [8, 3, 5] and it is good, since 8 = 3+5.
Hence the nice indices are 1 and 4.Input : A[] = { 2, 2, 2 }
Output : 1 2 3
Removing any element at any indices will make array good.
Approach:
- Create a hash of array A[] which store frequency of each element and a variable sum having sum of each element of A.
- Iterate the array, remove the element at index i for each .
- After removing an element the sum of remaining array is K, where K = sum – A[i].
- We have to find an element K/2 in the remaining array to make it good. Let K = K/2 for now.
- Now the remaining array will be good if and only if below conditions holds true.
- If A[i] == K and hash(K) > 1 OR If A[i] != K and hash(K) > 0.
- Print all such indices i.
Below is the implementation of above approach:
C++
// C++ program to find all good indices // in the given array #include <bits/stdc++.h> using namespace std; // Function to find all good indices // in the given array void niceIndices( int A[], int n) { int sum = 0; // hash to store frequency // of each element map< int , int > m; // Storing frequency of each element // and calculating sum simultaneously for ( int i = 0; i < n; ++i) { m[A[i]]++; sum += A[i]; } for ( int i = 0; i < n; ++i) { int k = sum - A[i]; if (k % 2 == 0) { k = k >> 1; // check if array is good after // removing i-th index element if (m.find(k) != m.end()) { if ((A[i] == k && m[k] > 1) || (A[i] != k)) // print good indices cout << (i + 1) << " " ; } } } } // Driver Code int main() { int A[] = { 8, 3, 5, 2 }; int n = sizeof (A) / sizeof (A[0]); niceIndices(A, n); return 0; } |
Java
// Java program to find all good indices // in the given array import java.util.*; class Solution { // Function to find all good indices // in the given array static void niceIndices( int A[], int n) { int sum = 0 ; // hash to store frequency // of each element Map<Integer, Integer> m= new HashMap<Integer, Integer>(); // Storing frequency of each element // and calculating sum simultaneously for ( int i = 0 ; i < n; ++i) { m.put(A[i],(m.get(A[i])== null )? 0 :m.get(A[i])+ 1 ); sum += A[i]; } for ( int i = 0 ; i < n; ++i) { int k = sum - A[i]; if (k % 2 == 0 ) { k = k >> 1 ; // check if array is good after // removing i-th index element if (m.containsKey(k)) { if ((A[i] == k && m.get(k) > 1 ) || (A[i] != k)) // print good indices System.out.print( (i + 1 ) + " " ); } } } } // Driver Code public static void main(String args[]) { int A[] = { 8 , 3 , 5 , 2 }; int n = A.length; niceIndices(A, n); } } //contributed by Arnab Kundu |
Python3
# Python3 program to find all good # indices in the given array from collections import defaultdict # Function to find all good indices # in the given array def niceIndices(A, n): Sum = 0 # hash to store frequency # of each element m = defaultdict( lambda : 0 ) # Storing frequency of each element # and calculating sum simultaneously for i in range (n): m[A[i]] + = 1 Sum + = A[i] for i in range (n): k = Sum - A[i] if k % 2 = = 0 : k = k >> 1 # check if array is good after # removing i-th index element if k in m: if ((A[i] = = k and m[k] > 1 ) or (A[i] ! = k)): # print good indices print ((i + 1 ), end = " " ) # Driver Code if __name__ = = "__main__" : A = [ 8 , 3 , 5 , 2 ] n = len (A) niceIndices(A, n) # This code is contributed by Rituraj Jain |
C#
// C# program to find all good indices // in the given array using System; using System.Collections.Generic; class GFG { // Function to find all good indices // in the given array static void niceIndices( int []A, int n) { int sum = 0; // hash to store frequency // of each element Dictionary< int , int > mp = new Dictionary< int , int >(); // Storing frequency of each element // and calculating sum simultaneously for ( int i = 0 ; i < n; i++) { if (mp.ContainsKey(A[i])) { var val = mp[A[i]]; mp.Remove(A[i]); mp.Add(A[i], val + 1); sum += A[i]; } else { mp.Add(A[i], 0); sum += A[i]; } } for ( int i = 0; i < n; ++i) { int k = sum - A[i]; if (k % 2 == 0) { k = k >> 1; // check if array is good after // removing i-th index element if (mp.ContainsKey(k)) { if ((A[i] == k && mp[k] > 1) || (A[i] != k)) // print good indices Console.Write( (i + 1) + " " ); } } } } // Driver Code public static void Main(String []args) { int []A = { 8, 3, 5, 2 }; int n = A.Length; niceIndices(A, n); } } /* This code is contributed by PrinciRaj1992 */ |
Javascript
<script> // Javascript program to find all good indices // in the given array // Function to find all good indices // in the given array function niceIndices(A, n) { var sum = 0; // hash to store frequency // of each element var m = new Map(); // Storing frequency of each element // and calculating sum simultaneously for ( var i = 0; i < n; ++i) { if (m.has(A[i])) m.set(A[i], m.get(A[i])+1) else m.set(A[i], 1) sum += A[i]; } for ( var i = 0; i < n; ++i) { var k = sum - A[i]; if (k % 2 == 0) { k = k >> 1; // check if array is good after // removing i-th index element if (m.has(k)) { if ((A[i] == k && m.get(k) > 1) || (A[i] != k)) // print good indices document.write(i + 1 + " " ); } } } } // Driver Code var A = [8, 3, 5, 2]; var n = A.length; niceIndices(A, n); // This code is contributed by importantly. </script> |
Output
1 4
Complexity Analysis:
- Time Complexity: O(N*log(N))
- Auxiliary Space: O(N)
Contact Us