Given an array arr[] of even length N and an integer K denoting the range of numbers in the array i.e. the numbers in the array are in the range [1, K]. The task is to find all opposite indices pair sums possible with minimum replacements where in any replacement any number of the array can be changed to any other number in the range [1, K].
Note: Two indices i and j are said to be opposite if the distance of i from start and distance of j from the end are equal and i is in the first half of the array and j in the last half of the array.
Examples:
Input: arr[] = {1, 2, 4, 3}, K = 4
Output: 4 6
Explanation: Initially the pair sum is 1+3 = 4 and 2+4 = 6 which is not equal.
Replace 4 with 2 in one step (minimum moves) and it will give two pairs having sum 4.
Or change the 1 to 3 in one step, that will give two pairs having sum 6.
So there are two possible values of equal sum of all pairs, 4 and 6, in minimum moves.Input: arr[] = {1, 2, 4, 6, 5, 3}, K = 6
Output: 7
Explanation: The three different pair sums are 4, 7, and 10.
Change 3 to 6 and 6 to 3. and this will give all the pair sum as 7 with minimum changes.
Notice here pair sum cannot be made 4 as {4, 6} itself will require 2 .
So total changes will not be minimum.
And also pair sum cannot be made 10 as then 3 should be changed to 9 or 1 to 7.
Both the values lies outside the range [1, 6].
Approach: This problem is based on the sweeping algorithm. For every pair find the max and min value that it can take and create segments so that minimum operations can be achieved. Find the most overlapping segments and also mark the total sum in the segments. In this way, the minimum sum values that make equal pairs can be found.
Below is the implementation of the above approach.
C++
#include <bits/stdc++.h>using namespace std;// Function to find the possible valuesvoid findValues(vector<int> arr, int K){ int N = arr.size(); int range[(K * 2) + 2] = { 0 }; for (int i = 0; i < N / 2; i++) { int mini = min(arr[i], arr[N - 1 - i]) + 1; int maxi = max(arr[i], arr[N - 1 - i]) + K; int total = arr[i] + arr[N - 1 - i]; // Using the sweeping the algorithm // Increment the array range[mini]--; range[maxi + 1]++; range[total]--; range[total + 1]++; } int count = N; int mini = INT_MAX; int value = 0; for (int i = 2; i < (K * 2) + 1; i++) { count += range[i]; mini = min(mini, count); } count = N; for (int i = 2; i < (K * 2) + 1; i++) { count += range[i]; if (count == mini) { cout << i << " "; } }}// Driver codeint main(){ vector<int> arr = { 1, 2, 4, 3 }; int K = 4; findValues(arr, K); return 0;}// This code is contributed by Potta Lokesh |
Java
// Java code to implement above approachimport java.io.*;import java.util.*;class GFG { // Function to find the possible values public static void findValues(int arr[], int K) { int N = arr.length; int range[] = new int[K * 2 + 2]; for (int i = 0; i < N / 2; ++i) { int min = Math.min(arr[i], arr[N - 1 - i]) + 1; int max = Math.max(arr[i], arr[N - 1 - i]) + K; int total = arr[i] + arr[N - 1 - i]; // Using the sweeping the algorithm // Increment the array range[min]--; range[max + 1]++; range[total]--; range[total + 1]++; } int count = N; int min = Integer.MAX_VALUE; int value = 0; for (int i = 2; i < K * 2 + 1; ++i) { count += range[i]; min = Integer.min(min, count); } count = N; for (int i = 2; i < K * 2 + 1; ++i) { count += range[i]; if (count == min) { System.out.print(i + " "); } } } // Driver code public static void main(String[] args) { int arr[] = { 1, 2, 4, 3 }; int K = 4; findValues(arr, K); }} |
Python3
# Python program for the above approachimport sys# Function to find the possible valuesdef findValues(arr, K): N = len(arr) ranges = [0] * ((K * 2) + 2) for i in range(0, N // 2): mini = min(arr[i], arr[N - 1 - i]) + 1 maxi = max(arr[i], arr[N - 1 - i]) + K total = arr[i] + arr[N - 1 - i] # Using the sweeping the algorithm # Increment the array ranges[mini] = ranges[mini] - 1 ranges[maxi + 1] = ranges[maxi + 1] + 1 ranges[total] = ranges[total] - 1 ranges[total + 1] = ranges[total + 1] + 1 count = N mini = sys.maxsize value = 0 for i in range(2, K*2+1): count = count + ranges[i] mini = min(mini, count) count = N for i in range(2, K*2+1): count = count + ranges[i] if (count == mini): print(i, end=" ")# Driver codearr = [1, 2, 4, 3]K = 4findValues(arr, K)# This code is contributed by Taranpreet |
C#
using System;public class GFG{ // Function to find the possible values public static void findValues(int[] arr, int K) { int N = arr.Length; int[] range = new int[K * 2 + 2]; for (int i = 0; i < N / 2; ++i) { int min = Math.Min(arr[i], arr[N - 1 - i]) + 1; int max = Math.Max(arr[i], arr[N - 1 - i]) + K; int total = arr[i] + arr[N - 1 - i]; // Using the sweeping the algorithm // Increment the array range[min]--; range[max + 1]++; range[total]--; range[total + 1]++; } int count = N; int mn = Int32.MaxValue; for (int i = 2; i < K * 2 + 1; ++i) { count += range[i]; mn = Math.Min(mn, count); } count = N; for (int i = 2; i < K * 2 + 1; ++i) { count += range[i]; if (count == mn) { Console.Write(i + " "); } } } // Driver code static public void Main (){ int[] arr = { 1, 2, 4, 3 }; int K = 4; findValues(arr, K); }}// This code is contributed by hrithikgarg03188. |
Javascript
<script>// Function to find the possible valuesfunction findValues(arr, K){ let N = arr.length; let range = []; for(let i = 0; i < (K * 2) + 1; i++) { range[i] = 0; } for (let i = 0; i < N / 2; i++) { let mini = Math.min(arr[i], arr[N - 1 - i]) + 1; let maxi = Math.max(arr[i], arr[N - 1 - i]) + K; let total = arr[i] + arr[N - 1 - i]; // Using the sweeping the algorithm // Increment the array range[mini]--; range[maxi + 1]++; range[total]--; range[total + 1]++; } let count = N; let mini = Number.MAX_SAFE_INTEGER; let value = 0; for (let i = 2; i < (K * 2) + 1; i++) { count += range[i]; mini = Math.min(mini, count); } count = N; for (let i = 2; i < (K * 2) + 1; i++) { count += range[i]; if (count == mini) { document.write(i + " "); } }}// Driver codelet arr = [ 1, 2, 4, 3 ];let K = 4;findValues(arr, K);// This code is contributed by Samim Hossain Mondal.</scripty |
4 6
Time Complexity: O(K)
Auxiliary Space: O(K)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
