Given an array arr[] of size N, the task is to maximize the absolute difference between the sum of even indexed elements and the sum of odd indexed elements by left shift or right shift of array elements any number of times.
Examples:
Input: arr[] = {332, 421, 215, 584, 232}
Output: 658
Explanation:
Convert the array to {233, 421, 152, 845, 223},
Sum of odd indexed elements = 608.
Sum of even indexed elements = 1266.
Therefore, the difference equals 658.Input: arr[] = {11, 22, 33, 44, 55}
Output: 33
Approach: The idea is to minimize the value of any one of even or odd indexed array elements and maximize that of the other in order to maximize their absolute difference. Follow the steps below to solve the problem:
- Two possible cases exists. Either to minimize the even indexed array elements and maximize the odd indexed array elements or to minimize the odd indexed array elements and maximize the even indexed array elements.
- For minimizing an element, apply all the shift operations and take the minimum possible value. Similarly, to maximize an element, apply all the shift operations and take the maximum possible value.
- Take the maximum difference from both the cases.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to minimize array// elements by shift operationsint minimize(int n){ int optEle = n; string strEle = to_string(n); // For checking all the // left shift operations for (int idx = 0; idx < strEle.length();idx++) { // Left shift int temp = stoi(strEle.substr(idx) + strEle.substr(0, idx)); // Consider the minimum possible value optEle = min(optEle, temp); } return optEle;}// Function to maximize array// elements by shift operationsint maximize(int n){ int optEle = n; string strEle = to_string(n); // For checking all the // left shift operations for (int idx = 0; idx < strEle.length();idx++) { // Left shift int temp = stoi(strEle.substr(idx) + strEle.substr(0, idx)); // Consider the maximum possible value optEle = max(optEle, temp); } return optEle;}// Function to maximize the absolute// difference between even and odd// indexed array elementsvoid minimumDifference(int arr[], int N){ int caseOne = 0; int minVal = 0; int maxVal = 0; // To calculate the difference of // odd indexed elements // and even indexed elements for (int i = 0; i < N; i++) { if (i % 2 == 0) minVal += minimize(arr[i]); else maxVal += maximize(arr[i]); } caseOne = abs(maxVal - minVal); int caseTwo = 0; minVal = 0; maxVal = 0; // To calculate the difference // between odd and even indexed // array elements for (int i = 0; i < N; i++) { if (i % 2 == 0) maxVal += maximize(arr[i]); else minVal += minimize(arr[i]); caseTwo = abs(maxVal - minVal); } // Print the maximum value cout << max(caseOne, caseTwo) << endl;}// Driver codeint main(){ int arr[] = { 332, 421, 215, 584, 232 }; int N = sizeof(arr) / sizeof(arr[0]); minimumDifference(arr, N); return 0;}// This code is contributed by divyesh072019. |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to minimize array // elements by shift operations static int minimize(int n) { int optEle = n; String strEle = Integer.toString(n); // For checking all the // left shift operations for (int idx = 0; idx < strEle.length(); idx++) { // Left shift int temp = Integer.parseInt(strEle.substring(idx) + strEle.substring(0, idx)); // Consider the minimum possible value optEle = Math.min(optEle, temp); } return optEle; } // Function to maximize array // elements by shift operations static int maximize(int n) { int optEle = n; String strEle = Integer.toString(n); // For checking all the // left shift operations for (int idx = 0; idx < strEle.length(); idx++) { // Left shift int temp = Integer.parseInt(strEle.substring(idx) + strEle.substring(0, idx)); // Consider the maximum possible value optEle = Math.max(optEle, temp); } return optEle; } // Function to maximize the absolute // difference between even and odd // indexed array elements static void minimumDifference(int[] arr) { int caseOne = 0; int minVal = 0; int maxVal = 0; // To calculate the difference of // odd indexed elements // and even indexed elements for (int i = 0; i < arr.length; i++) { if (i % 2 == 0) minVal += minimize(arr[i]); else maxVal += maximize(arr[i]); } caseOne = Math.abs(maxVal - minVal); int caseTwo = 0; minVal = 0; maxVal = 0; // To calculate the difference // between odd and even indexed // array elements for (int i = 0; i < arr.length; i++) { if (i % 2 == 0) maxVal += maximize(arr[i]); else minVal += minimize(arr[i]); caseTwo = Math.abs(maxVal - minVal); } // Print the maximum value System.out.println(Math.max(caseOne, caseTwo)); } // Driver Code public static void main(String[] args) { // Given array int[] arr = { 332, 421, 215, 584, 232 }; minimumDifference(arr); }}// This code is contributed by Dharanendra L V. |
Python3
# Python3 program for the above approach# Function to minimize array# elements by shift operationsdef minimize(n): optEle = n strEle = str(n) # For checking all the # left shift operations for idx in range(len(strEle)): # Left shift temp = int(strEle[idx:] + strEle[:idx]) # Consider the minimum possible value optEle = min(optEle, temp) return optEle# Function to maximize array# elements by shift operationsdef maximize(n): optEle = n strEle = str(n) # For checking all the # left shift operations for idx in range(len(strEle)): # Left shift temp = int(strEle[idx:] + strEle[:idx]) # Consider the maximum possible value optEle = max(optEle, temp) return optEle # Function to maximize the absolute # difference between even and odd # indexed array elementsdef minimumDifference(arr): caseOne = 0 minVal = 0 maxVal = 0 # To calculate the difference of # odd indexed elements # and even indexed elements for i in range(len(arr)): if i % 2: minVal += minimize(arr[i]) else: maxVal += maximize(arr[i]) caseOne = abs(maxVal - minVal) caseTwo = 0 minVal = 0 maxVal = 0 # To calculate the difference # between odd and even indexed # array elements for i in range(len(arr)): if i % 2: maxVal += maximize(arr[i]) else: minVal += minimize(arr[i]) caseTwo = abs(maxVal - minVal) # Print the maximum value print (max(caseOne, caseTwo)) # Given arrayarr = [ 332, 421, 215, 584, 232 ]minimumDifference(arr) |
C#
// C# program for the above approachusing System;class GFG{ // Function to minimize array // elements by shift operations static int minimize(int n) { int optEle = n; string strEle = n.ToString(); // For checking all the // left shift operations for (int idx = 0; idx < strEle.Length;idx++) { // Left shift int temp = Int32.Parse(strEle.Substring(idx) + strEle.Substring(0, idx)); // Consider the minimum possible value optEle = Math.Min(optEle, temp); } return optEle; } // Function to maximize array // elements by shift operations static int maximize(int n) { int optEle = n; string strEle = n.ToString(); // For checking all the // left shift operations for (int idx = 0; idx < strEle.Length;idx++) { // Left shift int temp = Int32.Parse(strEle.Substring(idx) + strEle.Substring(0, idx)); // Consider the maximum possible value optEle = Math.Max(optEle, temp); } return optEle; } // Function to maximize the absolute // difference between even and odd // indexed array elements static void minimumDifference(int[] arr) { int caseOne = 0; int minVal = 0; int maxVal = 0; // To calculate the difference of // odd indexed elements // and even indexed elements for (int i = 0; i < arr.Length; i++) { if (i % 2 == 0) minVal += minimize(arr[i]); else maxVal += maximize(arr[i]); } caseOne = Math.Abs(maxVal - minVal); int caseTwo = 0; minVal = 0; maxVal = 0; // To calculate the difference // between odd and even indexed // array elements for (int i = 0; i < arr.Length; i++) { if (i % 2 == 0) maxVal += maximize(arr[i]); else minVal += minimize(arr[i]); caseTwo = Math.Abs(maxVal - minVal); } // Print the maximum value Console.WriteLine(Math.Max(caseOne, caseTwo)); } // Given array public static void Main() { int[] arr = { 332, 421, 215, 584, 232 }; minimumDifference(arr); }}// This code is contributed by chitranayal. |
Javascript
<script>// Javascript program for the above approach// Function to minimize array // elements by shift operationsfunction minimize(n){ let optEle = n; let strEle = (n).toString(); // For checking all the // left shift operations for (let idx = 0; idx < strEle.length; idx++) { // Left shift let temp = parseInt(strEle.substring(idx) + strEle.substring(0, idx)); // Consider the minimum possible value optEle = Math.min(optEle, temp); } return optEle;}// Function to maximize array // elements by shift operationsfunction maximize(n){ let optEle = n; let strEle = n.toString(); // For checking all the // left shift operations for (let idx = 0; idx < strEle.length; idx++) { // Left shift let temp = parseInt(strEle.substring(idx) + strEle.substring(0, idx)); // Consider the maximum possible value optEle = Math.max(optEle, temp); } return optEle;}// Function to maximize the absolute // difference between even and odd // indexed array elementsfunction minimumDifference(arr){ let caseOne = 0; let minVal = 0; let maxVal = 0; // To calculate the difference of // odd indexed elements // and even indexed elements for (let i = 0; i < arr.length; i++) { if (i % 2 == 0) minVal += minimize(arr[i]); else maxVal += maximize(arr[i]); } caseOne = Math.abs(maxVal - minVal); let caseTwo = 0; minVal = 0; maxVal = 0; // To calculate the difference // between odd and even indexed // array elements for (let i = 0; i < arr.length; i++) { if (i % 2 == 0) maxVal += maximize(arr[i]); else minVal += minimize(arr[i]); caseTwo = Math.abs(maxVal - minVal); } // Print the maximum value document.write(Math.max(caseOne, caseTwo)+"<Br>");}// Given arraylet arr=[332, 421, 215, 584, 232 ];minimumDifference(arr);// This code is contributed by avanitrachhadiya2155</script> |
Output:
658
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!
