Given an array arr[] and a number K, the task is to find the absolute difference of the sum of K maximum even and odd array elements.
Note: At least K even and odd elements are present in the array respectively.
Examples:
Input arr[] = {1, 2, 3, 4, 5, 6}, K = 2
Output: 2
Explanation:
The 2 maximum even numbers are 6, 4. The sum is 6 + 4 = 10.
The 2 maximum odd numbers are 5, 3. The sum is 5 + 3 = 8.
Difference = 10 – 8 = 2.Input arr[] = {1, 8, 4, 5, 6, 3}, K = 3
Output: 4
Explanation:
The 3 maximum even numbers are 8, 6, 4. The sum is 8 + 6 + 4 = 18.
The 3 maximum odd numbers are 5, 3, 1. The sum is 5 + 3 + 1 = 9.
Difference = 18 – 9 = 9.
Naive Approach: The simplest approach is to find the K maximum even numbers and K maximum odd numbers by traversing the array and print the absolute difference between the sum of the K maximum even and odd elements obtained.
Time Complexity: O(N*K)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use the concept of segregate the array into odd and even numbers and then sort the array into two parts in descending order containing even and odd numbers respectively. Follow the steps below to solve the problem:
- Segregate even number and odd number in the given array respectively and store the index from where odd numbers start.
- Let the index from where the odd numbers start to be K. Sort the number in the range [0, K – 1] and [K, N – 1] in decreasing order.
- The sum of the first K numbers from the start of the array and from the point where odd numbers start is the sum first K maximum even and odd numbers in the array respectively.
- Print the absolute difference between the sums calculated in the above step as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the absolute// difference between sum of first K// maximum even and odd numbersvoid evenOddDiff(int a[], int n, int k){ // Stores index from where odd // number starts int j = -1; // Segregate even and odd number for (int i = 0; i < n; i++) { // If current element is even if (a[i] % 2 == 0) { j++; swap(a[i], a[j]); } } j++; // Sort in decreasing order even part sort(a, a + j, greater<int>()); // Sort in decreasing order odd part sort(a + j, a + n, greater<int>()); int evenSum = 0, oddSum = 0; // Calculate sum of k // maximum even number for (int i = 0; i < k; i++) { evenSum += a[i]; } // Calculate sum of k // maximum odd number for (int i = j; i < (j + k); i++) { oddSum += a[i]; } // Print the absolute difference cout << abs(evenSum - oddSum);}// Driver Codeint main(){ // Given array arr[] int arr[] = { 1, 8, 3, 4, 5 }; // Size of array int N = sizeof(arr) / sizeof(arr[0]); int K = 2; // Function Call evenOddDiff(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the absolute// difference between sum of first K// maximum even and odd numbersstatic void evenOddDiff(int a[], int n, int k){ // Stores index from where odd // number starts int j = -1; Vector<Integer> even = new Vector<>(); Vector<Integer> odd = new Vector<>(); // Segregate even and odd number for(int i = 0; i < n; i++) { // If current element is even if (a[i] % 2 == 0) { even.add(a[i]); } else odd.add(a[i]); } j++; // Sort in decreasing order even part Collections.sort(even); Collections.reverse(even); // Sort in decreasing order odd part Collections.sort(odd); Collections.reverse(odd); int evenSum = 0, oddSum = 0; // Calculate sum of k // maximum even number for(int i = 0; i < k; i++) { evenSum += even.get(i); } // Calculate sum of k // maximum odd number for(int i = 0; i < k; i++) { oddSum += odd.get(i); } // Print the absolute difference System.out.print(Math.abs(evenSum - oddSum));}// Driver Codepublic static void main(String[] args){ // Given array arr[] int arr[] = { 1, 8, 3, 4, 5 }; // Size of array int N = arr.length; int K = 2; // Function Call evenOddDiff(arr, N, K);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approach# Function to find the absolute# difference between sum of first K# maximum even and odd numbersdef evenOddDiff(a, n, k) : # Stores index from where odd # number starts j = -1 even = [] odd = [] # Segregate even and odd number for i in range(n) : # If current element is even if (a[i] % 2 == 0) : even.append(a[i]) else : odd.append(a[i]) j += 1 # Sort in decreasing order even part even.sort() even.reverse() # Sort in decreasing order odd part odd.sort() odd.reverse() evenSum, oddSum = 0, 0 # Calculate sum of k # maximum even number for i in range(k) : evenSum += even[i] # Calculate sum of k # maximum odd number for i in range(k) : oddSum += odd[i] # Print the absolute difference print(abs(evenSum - oddSum)) # Given array []arrarr = [ 1, 8, 3, 4, 5 ] # Size of arrayN = len(arr)K = 2# Function CallevenOddDiff(arr, N, K)# This code is contributed by divyeshrabadiya07 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find the absolute// difference between sum of first K// maximum even and odd numbersstatic void evenOddDiff(int []a, int n, int k){ // Stores index from where odd // number starts int j = -1; List<int> even = new List<int>(); List<int> odd = new List<int>(); // Segregate even and odd number for(int i = 0; i < n; i++) { // If current element is even if (a[i] % 2 == 0) { even.Add(a[i]); } else odd.Add(a[i]); } j++; // Sort in decreasing order even part even.Sort(); even.Reverse(); // Sort in decreasing order odd part odd.Sort(); odd.Reverse(); int evenSum = 0, oddSum = 0; // Calculate sum of k // maximum even number for(int i = 0; i < k; i++) { evenSum += even[i]; } // Calculate sum of k // maximum odd number for(int i = 0; i < k; i++) { oddSum += odd[i]; } // Print the absolute difference Console.Write(Math.Abs(evenSum - oddSum));}// Driver Codepublic static void Main(String[] args){ // Given array []arr int []arr = { 1, 8, 3, 4, 5 }; // Size of array int N = arr.Length; int K = 2; // Function Call evenOddDiff(arr, N, K);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// javascript program for the above approach // Function to find the absolute // difference between sum of first K // maximum even and odd numbers function evenOddDiff(a , n , k) { // Stores index from where odd // number starts var j = -1; var even = []; var odd = []; // Segregate even and odd number for (i = 0; i < n; i++) { // If current element is even if (a[i] % 2 == 0) { even.push(a[i]); } else odd.push(a[i]); } j++; // Sort in decreasing order even part even.sort((a,b)=>a-b); even.reverse(even); // Sort in decreasing order odd part odd.sort((a,b)=>a-b);; odd.reverse(); var evenSum = 0, oddSum = 0; // Calculate sum of k // maximum even number for (i = 0; i < k; i++) { evenSum += even[i]; } // Calculate sum of k // maximum odd number for (i = 0; i < k; i++) { oddSum += odd[i]; } // Print the absolute difference document.write(Math.abs(evenSum - oddSum)); } // Driver Code // Given array arr var arr = [ 1, 8, 3, 4, 5 ]; // Size of array var N = arr.length; var K = 2; // Function Call evenOddDiff(arr, N, K);// This code is contributed by umadevi9616</script> |
Output:
4
Time Complexity: O(N*log N + K)
Auxiliary Space: O(1)
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!
