Given an array arr[] consisting of N integers and an integer K, the task is to find the number of times the absolute difference between the sum of elements at odd and even indices is K after removing any one element at a time from the given array.
Examples:
Input: arr[] = {2, 4, 2}, K = 2
Output: 2
Explanation:
- Removing arr[0] modifies arr[] to {4, 2}. Therefore, difference between sum of odd and even-indexed elements is 2.
- Removing arr[1] modifies arr[] to {2, 2}. Therefore, difference between sum of odd and even-indexed elements is 0.
- Removing arr[2] modifies arr[] to {2, 4}. Therefore, difference between sum of odd and even-indexed elements is 2.
Therefore, number of times the difference of sum of element at odd and even index is 2 is 2.
Input: arr[] = { 1, 1, 1, 1, 1 }, K = 0
Output: 5
Naive Approach: The simplest approach is to remove every array element one by one and after each removal, check if the absolute difference between the sum of elements at odd and even indices is K or not. If found to be true, then increment count. After complete traversal of the array, print the value of count.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use Prefix Sum and Suffix Sum arrays. Follow the steps below to solve the problem:
- Initialize two arrays prefixSum[] and suffixSum[] of size (N + 2) as 0 to store the prefix and suffix sum of elements at odd and even indices respectively.
- Store the prefix sum of elements of the array arr[] at odd and even indices in the array prefixSum[] starting from index 2.
- Store the suffix sum of elements of the array arr[] at odd and even indices in the array suffixSum[] starting from index (N + 1).
- Initialize the variable count as 0 to store the number of times the absolute difference between the sum of elements at odd and even indices is K
- Traverse the given array arr[] and increment the count as per the below conditions:
- If the current element arr[i] is removed then check if the absolute difference of ( prefixSum[i – 1] + suffix[i + 2] ) and
(prefix[i – 2] + suffix[i + 1]) is K or not. - If the difference is found to be K then increment the count by 1, else check for the next element.
- If the current element arr[i] is removed then check if the absolute difference of ( prefixSum[i – 1] + suffix[i + 2] ) and
- Check whether the condition is true after removing the 0th and 1st element separately and increment the count accordingly.
- After the above steps, the count gives the total count of elements is removed.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include "bits/stdc++.h" using namespace std; // Function to check if difference // between the sum of odd and even // indexed elements after removing // the first element is K or not int findCount0th(vector< int >& arr, int N, int K) { // Stores the sum of elements // at odd and even indices int oddsum = 0, evensum = 0; for ( int i = 1; i < N; i += 2) { oddsum += arr[i]; } for ( int i = 2; i < N; i += 2) { evensum += arr[i]; } // Return 1 if difference is K if ( abs (oddsum - evensum) == K) return 1; else return 0; } // Function to check if difference // between the sum of odd and even // indexed elements after removing // the second element is K or not int findCount1st(vector< int >& arr, int N, int K) { // Stores the sum of elements // at odd and even indices int evensum = arr[0], oddsum = 0; for ( int i = 3; i < N; i += 2) { evensum += arr[i]; } for ( int i = 2; i < N; i += 2) { oddsum += arr[i]; } // Return 1 if difference is K if ( abs (oddsum - evensum) == K) return 1; else return 0; } // Function to count number of elements // to be removed to make sum of // differences between odd and even // indexed elements equal to K int countTimes(vector< int >& arr, int K) { // Size of given array int N = ( int )arr.size(); // Base Conditions if (N == 1) return 1; if (N < 3) return 0; if (N == 3) { int cnt = 0; cnt += ( abs (arr[0] - arr[1]) == K ? 1 : 0) + ( abs (arr[2] - arr[1]) == K ? 1 : 0) + ( abs (arr[0] - arr[2]) == K ? 1 : 0); return cnt; } // Stores prefix and suffix sums vector< int > prefix(N + 2, 0); vector< int > suffix(N + 2, 0); // Base assignments prefix[0] = arr[0]; prefix[1] = arr[1]; suffix[N - 1] = arr[N - 1]; suffix[N - 2] = arr[N - 2]; // Store prefix sums of even // indexed elements for ( int i = 2; i < N; i += 2) { prefix[i] = arr[i] + prefix[i - 2]; } // Store prefix sums of odd // indexed elements for ( int i = 3; i < N; i += 2) { prefix[i] = arr[i] + prefix[i - 2]; } // Similarly, store suffix sums of // elements at even and odd indices for ( int i = N - 3; i >= 0; i -= 2) { suffix[i] = arr[i] + suffix[i + 2]; } for ( int i = N - 4; i >= 0; i -= 2) { suffix[i] = arr[i] + suffix[i + 2]; } // Stores the count of possible removals int count = 0; // Traverse and remove the ith element for ( int i = 2; i < N; i++) { // If the current element is // excluded, then previous index // (i - 1) points to (i + 2) // and (i - 2) points to (i + 1) if ( abs (prefix[i - 1] + suffix[i + 2] - prefix[i - 2] - suffix[i + 1]) == K) { count++; } } // Find count when 0th element is removed count += findCount0th(arr, N, K); // Find count when 1st element is removed count += findCount1st(arr, N, K); // Count gives the required answer return count; } // Driver Code int main() { vector< int > arr = { 1, 2, 4, 5, 6 }; int K = 2; // Function call cout << countTimes(arr, K); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG{ // Function to check if difference // between the sum of odd and even // indexed elements after removing // the first element is K or not static int findCount0th( int [] arr, int N, int K) { // Stores the sum of elements // at odd and even indices int oddsum = 0 , evensum = 0 ; for ( int i = 1 ; i < N; i += 2 ) { oddsum += arr[i]; } for ( int i = 2 ; i < N; i += 2 ) { evensum += arr[i]; } // Return 1 if difference is K if (Math.abs(oddsum - evensum) == K) return 1 ; else return 0 ; } // Function to check if difference // between the sum of odd and even // indexed elements after removing // the second element is K or not static int findCount1st( int [] arr, int N, int K) { // Stores the sum of elements // at odd and even indices int evensum = arr[ 0 ], oddsum = 0 ; for ( int i = 3 ; i < N; i += 2 ) { evensum += arr[i]; } for ( int i = 2 ; i < N; i += 2 ) { oddsum += arr[i]; } // Return 1 if difference is K if (Math.abs(oddsum - evensum) == K) return 1 ; else return 0 ; } // Function to count number of elements // to be removed to make sum of // differences between odd and even // indexed elements equal to K static int countTimes( int [] arr, int K) { // Size of given array int N = ( int )arr.length; // Base Conditions if (N == 1 ) return 1 ; if (N < 3 ) return 0 ; if (N == 3 ) { int cnt = 0 ; cnt += (Math.abs(arr[ 0 ] - arr[ 1 ]) == K ? 1 : 0 ) + (Math.abs(arr[ 2 ] - arr[ 1 ]) == K ? 1 : 0 ) + (Math.abs(arr[ 0 ] - arr[ 2 ]) == K ? 1 : 0 ); return cnt; } // Stores prefix and suffix sums int [] prefix = new int [N + 2 ]; int [] suffix = new int [N + 2 ]; Arrays.fill(prefix, 0 ); Arrays.fill(suffix, 0 ); // Base assignments prefix[ 0 ] = arr[ 0 ]; prefix[ 1 ] = arr[ 1 ]; suffix[N - 1 ] = arr[N - 1 ]; suffix[N - 2 ] = arr[N - 2 ]; // Store prefix sums of even // indexed elements for ( int i = 2 ; i < N; i += 2 ) { prefix[i] = arr[i] + prefix[i - 2 ]; } // Store prefix sums of odd // indexed elements for ( int i = 3 ; i < N; i += 2 ) { prefix[i] = arr[i] + prefix[i - 2 ]; } // Similarly, store suffix sums of // elements at even and odd indices for ( int i = N - 3 ; i >= 0 ; i -= 2 ) { suffix[i] = arr[i] + suffix[i + 2 ]; } for ( int i = N - 4 ; i >= 0 ; i -= 2 ) { suffix[i] = arr[i] + suffix[i + 2 ]; } // Stores the count of possible removals int count = 0 ; // Traverse and remove the ith element for ( int i = 2 ; i < N; i++) { // If the current element is // excluded, then previous index // (i - 1) points to (i + 2) // and (i - 2) points to (i + 1) if (Math.abs(prefix[i - 1 ] + suffix[i + 2 ] - prefix[i - 2 ] - suffix[i + 1 ]) == K) { count++; } } // Find count when 0th element is removed count += findCount0th(arr, N, K); // Find count when 1st element is removed count += findCount1st(arr, N, K); // Count gives the required answer return count; } // Driver code public static void main(String[] args) { int [] arr = { 1 , 2 , 4 , 5 , 6 }; int K = 2 ; // Function call System.out.println(countTimes(arr, K)); } } // This code is contributed by code_hunt. |
Python3
# Python3 program for the above approach # Function to check if difference # between the sum of odd and even # indexed elements after removing # the first element is K or not def findCount0th(arr, N, K): # Stores the sum of elements # at odd and even indices oddsum = 0 evensum = 0 for i in range ( 1 , N, 2 ): oddsum + = arr[i] for i in range ( 2 , N, 2 ): evensum + = arr[i] # Return 1 if difference is K if ( abs (oddsum - evensum) = = K): return 1 else : return 0 # Function to check if difference # between the sum of odd and even # indexed elements after removing # the second element is K or not def findCount1st(arr, N, K): # Stores the sum of elements # at odd and even indices evensum = arr[ 0 ] oddsum = 0 for i in range ( 3 , N, 2 ): evensum + = arr[i] for i in range ( 2 , N, 2 ): oddsum + = arr[i] # Return 1 if difference is K if ( abs (oddsum - evensum) = = K): return 1 else : return 0 # Function to count number of elements # to be removed to make sum of # differences between odd and even # indexed elements equal to K def countTimes(arr, K): # Size of given array N = len (arr) # Base Conditions if (N = = 1 ): return 1 if (N < 3 ): return 0 if (N = = 3 ): cnt = 0 if abs (arr[ 0 ] - arr[ 1 ]) = = K: cnt + = 1 if abs (arr[ 2 ] - arr[ 1 ]) = = K: cnt + = 1 if abs (arr[ 0 ] - arr[ 2 ]) = = K: cnt + = 1 return cnt # Stores prefix and suffix sums prefix = [ 0 ] * (N + 2 ) suffix = [ 0 ] * (N + 2 ) # Base assignments prefix[ 0 ] = arr[ 0 ] prefix[ 1 ] = arr[ 1 ] suffix[N - 1 ] = arr[N - 1 ] suffix[N - 2 ] = arr[N - 2 ] # Store prefix sums of even # indexed elements for i in range ( 2 , N, 2 ): prefix[i] = arr[i] + prefix[i - 2 ] # Store prefix sums of odd # indexed elements for i in range ( 3 , N, 2 ): prefix[i] = arr[i] + prefix[i - 2 ] # Similarly, store suffix sums of # elements at even and odd indices for i in range (N - 3 , - 1 , - 2 ): suffix[i] = arr[i] + suffix[i + 2 ] for i in range ( N - 4 , - 1 , - 2 ): suffix[i] = arr[i] + suffix[i + 2 ] # Stores the count of possible removals count = 0 # Traverse and remove the ith element for i in range ( 2 , N): # If the current element is # excluded, then previous index # (i - 1) points to (i + 2) # and (i - 2) points to (i + 1) if ( abs (prefix[i - 1 ] + suffix[i + 2 ] - prefix[i - 2 ] - suffix[i + 1 ]) = = K): count + = 1 # Find count when 0th element is removed count + = findCount0th(arr, N, K) # Find count when 1st element is removed count + = findCount1st(arr, N, K) # Count gives the required answer return count # Driver Code if __name__ = = "__main__" : arr = [ 1 , 2 , 4 , 5 , 6 ] K = 2 # Function call print (countTimes(arr, K)) # This code is contributed by AnkThon |
C#
// C# program for the above approach using System; class GFG{ // Function to check if difference // between the sum of odd and even // indexed elements after removing // the first element is K or not static int findCount0th( int [] arr, int N, int K) { // Stores the sum of elements // at odd and even indices int oddsum = 0, evensum = 0; for ( int i = 1; i < N; i += 2) { oddsum += arr[i]; } for ( int i = 2; i < N; i += 2) { evensum += arr[i]; } // Return 1 if difference is K if (Math.Abs(oddsum - evensum) == K) return 1; else return 0; } // Function to check if difference // between the sum of odd and even // indexed elements after removing // the second element is K or not static int findCount1st( int [] arr, int N, int K) { // Stores the sum of elements // at odd and even indices int evensum = arr[0], oddsum = 0; for ( int i = 3; i < N; i += 2) { evensum += arr[i]; } for ( int i = 2; i < N; i += 2) { oddsum += arr[i]; } // Return 1 if difference is K if (Math.Abs(oddsum - evensum) == K) return 1; else return 0; } // Function to count number of elements // to be removed to make sum of // differences between odd and even // indexed elements equal to K static int countTimes( int [] arr, int K) { // Size of given array int N = ( int )arr.Length; // Base Conditions if (N == 1) return 1; if (N < 3) return 0; if (N == 3) { int cnt = 0; cnt += (Math.Abs(arr[0] - arr[1]) == K ? 1 : 0) + (Math.Abs(arr[2] - arr[1]) == K ? 1 : 0) + (Math.Abs(arr[0] - arr[2]) == K ? 1 : 0); return cnt; } // Stores prefix and suffix sums int [] prefix = new int [N + 2]; int [] suffix = new int [N + 2]; for ( int i = 0; i < N + 2; i++) { prefix[i] = 0; } for ( int i = 0; i < N + 2; i++) { suffix[i] = 0; } // Base assignments prefix[0] = arr[0]; prefix[1] = arr[1]; suffix[N - 1] = arr[N - 1]; suffix[N - 2] = arr[N - 2]; // Store prefix sums of even // indexed elements for ( int i = 2; i < N; i += 2) { prefix[i] = arr[i] + prefix[i - 2]; } // Store prefix sums of odd // indexed elements for ( int i = 3; i < N; i += 2) { prefix[i] = arr[i] + prefix[i - 2]; } // Similarly, store suffix sums of // elements at even and odd indices for ( int i = N - 3; i >= 0; i -= 2) { suffix[i] = arr[i] + suffix[i + 2]; } for ( int i = N - 4; i >= 0; i -= 2) { suffix[i] = arr[i] + suffix[i + 2]; } // Stores the count of possible removals int count = 0; // Traverse and remove the ith element for ( int i = 2; i < N; i++) { // If the current element is // excluded, then previous index // (i - 1) points to (i + 2) // and (i - 2) points to (i + 1) if (Math.Abs(prefix[i - 1] + suffix[i + 2] - prefix[i - 2] - suffix[i + 1]) == K) { count++; } } // Find count when 0th element is removed count += findCount0th(arr, N, K); // Find count when 1st element is removed count += findCount1st(arr, N, K); // Count gives the required answer return count; } // Driver Code public static void Main() { int [] arr = { 1, 2, 4, 5, 6 }; int K = 2; // Function call Console.WriteLine(countTimes(arr, K)); } } // This code is contributed by susmitakundugoaldanga |
Javascript
<script> // JavaScript program for the above approach // Function to check if difference // between the sum of odd and even // indexed elements after removing // the first element is K or not function findCount0th(arr, N, K) { // Stores the sum of elements // at odd and even indices let oddsum = 0, evensum = 0; for (let i = 1; i < N; i += 2) { oddsum += arr[i]; } for (let i = 2; i < N; i += 2) { evensum += arr[i]; } // Return 1 if difference is K if (Math.abs(oddsum - evensum) == K) return 1; else return 0; } // Function to check if difference // between the sum of odd and even // indexed elements after removing // the second element is K or not function findCount1st(arr, N, K) { // Stores the sum of elements // at odd and even indices let evensum = arr[0], oddsum = 0; for (let i = 3; i < N; i += 2) { evensum += arr[i]; } for (let i = 2; i < N; i += 2) { oddsum += arr[i]; } // Return 1 if difference is K if (Math.abs(oddsum - evensum) == K) return 1; else return 0; } // Function to count number of elements // to be removed to make sum of // differences between odd and even // indexed elements equal to K function countTimes(arr, K) { // Size of given array let N = arr.length; // Base Conditions if (N == 1) return 1; if (N < 3) return 0; if (N == 3) { let cnt = 0; cnt += (Math.abs(arr[0] - arr[1]) == K ? 1 : 0) + (Math.abs(arr[2] - arr[1]) == K ? 1 : 0) + (Math.abs(arr[0] - arr[2]) == K ? 1 : 0); return cnt; } // Stores prefix and suffix sums let prefix = new Array(N + 2); let suffix = new Array(N + 2); for (let i = 0; i < N + 2; i++) { prefix[i] = 0; } for (let i = 0; i < N + 2; i++) { suffix[i] = 0; } // Base assignments prefix[0] = arr[0]; prefix[1] = arr[1]; suffix[N - 1] = arr[N - 1]; suffix[N - 2] = arr[N - 2]; // Store prefix sums of even // indexed elements for (let i = 2; i < N; i += 2) { prefix[i] = arr[i] + prefix[i - 2]; } // Store prefix sums of odd // indexed elements for (let i = 3; i < N; i += 2) { prefix[i] = arr[i] + prefix[i - 2]; } // Similarly, store suffix sums of // elements at even and odd indices for (let i = N - 3; i >= 0; i -= 2) { suffix[i] = arr[i] + suffix[i + 2]; } for (let i = N - 4; i >= 0; i -= 2) { suffix[i] = arr[i] + suffix[i + 2]; } // Stores the count of possible removals let count = 0; // Traverse and remove the ith element for (let i = 2; i < N; i++) { // If the current element is // excluded, then previous index // (i - 1) points to (i + 2) // and (i - 2) points to (i + 1) if (Math.abs(prefix[i - 1] + suffix[i + 2] - prefix[i - 2] - suffix[i + 1]) == K) { count++; } } // Find count when 0th element is removed count += findCount0th(arr, N, K); // Find count when 1st element is removed count += findCount1st(arr, N, K); // Count gives the required answer return count; } let arr = [ 1, 2, 4, 5, 6 ]; let K = 2; // Function call document.write(countTimes(arr, K)); </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!