Given an array arr[], the task is to find the difference between maximum and minimum summations of consecutive odd elements in arr[].
Note: If there are no odd numbers present, return -1.
Examples:
Input: arr[] = {1, 2, 3, 4, 3, 5}
Output: 7
Explanation: The difference is 7 between minimum summation (1) and maximum summation (3, 5) of consecutive odd numbers.Input: arr[] = {2, 4, 4, 4, 5, 7}
Output : 0
Explanation: There is only one pair of consecutive odd elements (5, 7), so their maximum and minimum summations is 12, 12, thus the difference between |12-12| = 0
Approach: This can be solved using the following idea:
Iterate through all the indexes & whenever an odd element occurs get the summation of consecutive elements started from that index. Store the maximum of all summations and minimum in different variables.
Below is the implementation of the above approach :
- We have to iterate through each element.
- Whenever any odd element occurs, count the summation of the consecutive odd elements starting from that element.
- Store the maximum and minimum sum in different variables and return their difference
Below is the implementation of the code:
C++
// C++ Implementation#include <iostream>#include <climits>using namespace std;// Function to find differnece between// maximum and minimum odd sumint maxOddSum(int arr[], int n){ int i = 0; int min = INT_MAX, max = INT_MIN; while (i < n) { // if element in odd if (arr[i] % 2 == 1) { int start = i, sum = 0; // Get the summation of odd // elements starting from i while (start < n && arr[start] % 2 == 1) { sum += arr[start]; start++; } // Compare & get the maximum // & minimum summation min = std::min(min, sum); max = std::max(max, sum); i = start; } else i++; } // Check odd element present or not if (min == INT_MAX) return -1; // Return the difference return max - min;}// Driver codeint main(){ int arr[] = { 1, 2, 3, 4, 3, 5 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call int ans = maxOddSum(arr, n); cout << ans << endl; return 0;} |
Java
/* JAVA implementation of the above approach */import java.io.*;import java.util.*;class GFG { // Function to find differnece between // maximum and minimum odd sum public static int maxOddSum(int[] arr) { int n = arr.length, i = 0; int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE; while (i < n) { // if element in odd if (arr[i] % 2 == 1) { int start = i, sum = 0; // Get the summation of odd // elements starting from i while (start < n && arr[start] % 2 == 1) { sum += arr[start]; start++; } // Compare & get the maximum // & minimum summation min = Math.min(min, sum); max = Math.max(max, sum); i = start; } else i++; } // Check odd element present or not if (min == Integer.MAX_VALUE) return -1; // Return the difference return max - min; } // Driver code public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 3, 5 }; // Function call int ans = maxOddSum(arr); System.out.println(ans); }} |
Python3
# python Implementation# Function to find difference between# maximum and minimum odd sumdef max_odd_sum(arr): i = 0 minimum = float('inf') maximum = float('-inf') n = len(arr) while i < n: # If element is odd if arr[i] % 2 == 1: start = i summation = 0 # Get the summation of odd elements starting from i while start < n and arr[start] % 2 == 1: summation += arr[start] start += 1 # Compare and get the maximum and minimum summation minimum = min(minimum, summation) maximum = max(maximum, summation) i = start else: i += 1 # Check if odd element is present or not if minimum == float('inf'): return -1 # Return the difference return maximum - minimum# Driver codearr = [1, 2, 3, 4, 3, 5]# Function callans = max_odd_sum(arr)print(ans) |
C#
using System;class Program{ // Function to find differnece between // maximum and minimum odd sum static int MaxOddSum(int[] arr, int n) { int i = 0; int min = int.MaxValue, max = int.MinValue; while (i < n) { // if element in odd if (arr[i] % 2 == 1) { int start = i, sum = 0; // Get the summation of odd // elements starting from i while (start < n && arr[start] % 2 == 1) { sum += arr[start]; start++; } // Compare & get the maximum // & minimum summation min = Math.Min(min, sum); max = Math.Max(max, sum); i = start; } else { i++; } } // Check odd element present or not if (min == int.MaxValue) { return -1; } // Return the difference return max - min; } // Driver code static void Main() { int[] arr = { 1, 2, 3, 4, 3, 5 }; int n = arr.Length; int ans = MaxOddSum(arr, n); Console.WriteLine(ans); }} |
Javascript
// Function to find differnece between// maximum and minimum odd sumfunction maxOddSum(arr, n) { let i = 0; let min = Number.MAX_SAFE_INTEGER, max = Number.MIN_SAFE_INTEGER; while (i < n) { // if element in odd if (arr[i] % 2 === 1) { let start = i, sum = 0; // Get the summation of odd // elements starting from i while (start < n && arr[start] % 2 === 1) { sum += arr[start]; start++; } // Compare & get the maximum // & minimum summation min = Math.min(min, sum); max = Math.max(max, sum); i = start; } else { i++; } } // Check odd element present or not if (min === Number.MAX_SAFE_INTEGER) { return -1; } // Return the difference return max - min;}// Driver codeconst arr = [1, 2, 3, 4, 3, 5];const n = arr.length;const ans = maxOddSum(arr, n);console.log(ans); |
Output
7
Time Complexity: O(n)
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!
Share your thoughts in the comments
