Given an array arr[] of size N (multiple of 8) where the values in the array will be in the range [a, (a+8*N) -1] (a can be any positive integer), the task is to rearrange the array in a way such that the difference between the sum of squares at odd indices and sum of squares of the elements at even indices is the minimum among all possible rearrangements.
Note: If there are multiple rearrangements return any one of those.
Examples:
Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8}
Output: 1 2 4 3 7 8 6 5
Explanation: The difference is 0 as 1 + 42 + 72 + 62 = 102 = 22 + 32 + 82 + 52Input: arr[] = { 9, 11, 12, 15, 16, 13, 10, 14}
Output: 9 10 12 11 15 16 14 13
Explanation: The difference is 0 as 92 + 122 + 152 + 142 = 102 + 112 + 162 + 132 = 646
Approach: This problem can be solved based on the following mathematical observation:
For any positive integer S, ( S )2 + ( S+3 )2 – 4 = ( S+1 )2 + ( S+2 )2. As N is a multiple of 8 so it can be divided into N/8 groups where the difference of sum of squares of elements at odd and even indices for each group is 0.
For the first four elements keep the sum of squares at odd indices greater and four the next four just the opposite to keep the sum of squares of even indices more. So this group of 8 elements will have difference 0. As the similar is done for all N/8 groups the overall difference will be 0.The sequence of each group can be like: S, S+1, S+3, S+2, S+6, S+7, S+5, S+4
Follow the below steps to solve this problem:
- Divide the array into groups of size 8.
- Arrange elements in each group as derived from the observation.
- Return the rearranged array.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find// maximum element of the arrayint maximum(int arr[], int size){ int ma = INT_MIN; for (int i = 0; i < size; i++) { ma = max(ma, arr[i]); } return ma;}// Function to find// minimum element of the arrayint minimum(int arr[], int size){ int mi = INT_MAX; for (int i = 0; i < size; i++) { mi = min(mi, arr[i]); } return mi;}// Function to print the arrayvoid print_min(int arr[], int size){ int low = minimum(arr, size); int high = maximum(arr, size); // using the fact that // s^2 + (s+3)^2 = (s+1)^2 + (s+2)^2 + 4. for (int i = 0; i < size; i += 4) { // Making the difference +4 // for the odd indices if (i % 8 == 0) { arr[i] = low; arr[i + 2] = low + 3; arr[i + 1] = low + 1; arr[i + 3] = low + 2; } // Making the difference -4 for // odd indices +4 - 4 = 0 (balanced) else { arr[i] = low + 2; arr[i + 2] = low + 1; arr[i + 1] = low + 3; arr[i + 3] = low; } low += 4; } // Printing the array for (int i = 0; i < size; i++) { cout << arr[i] << " "; }}// Driver codeint main(){ int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; int N = sizeof(arr) / (sizeof(int)); // Function call print_min(arr, N); return 0;} |
Java
// JAVA code to implement the approachimport java.util.*;class GFG{ // Function to find // maximum element of the array public static int maximum(int arr[], int size) { int ma = Integer.MIN_VALUE; for (int i = 0; i < size; i++) { ma = Math.max(ma, arr[i]); } return ma; } // Function to find // minimum element of the array public static int minimum(int arr[], int size) { int mi = Integer.MAX_VALUE; for (int i = 0; i < size; i++) { mi = Math.min(mi, arr[i]); } return mi; } // Function to print the array public static void print_min(int arr[], int size) { int low = minimum(arr, size); int high = maximum(arr, size); // using the fact that // s^2 + (s+3)^2 = (s+1)^2 + (s+2)^2 + 4. for (int i = 0; i < size; i += 4) { // Making the difference +4 // for the odd indices if (i % 8 == 0) { arr[i] = low; arr[i + 2] = low + 3; arr[i + 1] = low + 1; arr[i + 3] = low + 2; } // Making the difference -4 for // odd indices +4 - 4 = 0 (balanced) else { arr[i] = low + 2; arr[i + 2] = low + 1; arr[i + 1] = low + 3; arr[i + 3] = low; } low += 4; } // Printing the array for (int i = 0; i < size; i++) { System.out.print(arr[i] + " "); } } // Driver code public static void main(String[] args) { int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; int N = arr.length; // Function call print_min(arr, N); }}// This code is contributed by Taranpreet |
Python3
# Python code to implement the approachINT_MIN = -2147483647 - 1INT_MAX = 2147483647# Function to find# maximum element of the arraydef maximum(arr, size): ma = INT_MIN for i in range(size): ma = max(ma, arr[i]) return ma# Function to find# minimum element of the arraydef minimum(arr, size): mi = INT_MAX for i in range(size): mi = min(mi, arr[i]) return mi# Function to print the arraydef print_min(arr, size): low = minimum(arr, size) high = maximum(arr, size) # using the fact that # s^2 + (s+3)^2 = (s+1)^2 + (s+2)^2 + 4. for i in range(0,size,4): # Making the difference +4 # for the odd indices if (i % 8 == 0): arr[i] = low arr[i + 2] = low + 3 arr[i + 1] = low + 1 arr[i + 3] = low + 2 # Making the difference -4 for # odd indices +4 - 4 = 0 (balanced) else: arr[i] = low + 2 arr[i + 2] = low + 1 arr[i + 1] = low + 3 arr[i + 3] = low low += 4 # Printing the array for i in range(size): print(arr[i],end=" ")# Driver codearr = [1, 2, 3, 4, 5, 6, 7, 8]N = len(arr)# Function callprint_min(arr, N)# This code is contributed by shinjanpatra |
C#
// C# code to implement the approachusing System;class GFG { // Function to find // maximum element of the array static int maximum(int[] arr, int size) { int ma = Int32.MinValue; for (int i = 0; i < size; i++) { ma = Math.Max(ma, arr[i]); } return ma; } // Function to find // minimum element of the array static int minimum(int[] arr, int size) { int mi = Int32.MaxValue; for (int i = 0; i < size; i++) { mi = Math.Min(mi, arr[i]); } return mi; } // Function to print the array static void print_min(int[] arr, int size) { int low = minimum(arr, size); int high = maximum(arr, size); // using the fact that // s^2 + (s+3)^2 = (s+1)^2 + (s+2)^2 + 4. for (int i = 0; i < size; i += 4) { // Making the difference +4 // for the odd indices if (i % 8 == 0) { arr[i] = low; arr[i + 2] = low + 3; arr[i + 1] = low + 1; arr[i + 3] = low + 2; } // Making the difference -4 for // odd indices +4 - 4 = 0 (balanced) else { arr[i] = low + 2; arr[i + 2] = low + 1; arr[i + 1] = low + 3; arr[i + 3] = low; } low += 4; } // Printing the array for (int i = 0; i < size; i++) { Console.Write(arr[i] + " "); } } // Driver code public static void Main() { int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8 }; int N = arr.Length; // Function call print_min(arr, N); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code to implement the approach const INT_MIN = -2147483647 - 1; const INT_MAX = 2147483647; // Function to find // maximum element of the array const maximum = (arr, size) => { let ma = INT_MIN; for (let i = 0; i < size; i++) { ma = Math.max(ma, arr[i]); } return ma; } // Function to find // minimum element of the array const minimum = (arr, size) => { let mi = INT_MAX; for (let i = 0; i < size; i++) { mi = Math.min(mi, arr[i]); } return mi; } // Function to print the array const print_min = (arr, size) => { let low = minimum(arr, size); let high = maximum(arr, size); // using the fact that // s^2 + (s+3)^2 = (s+1)^2 + (s+2)^2 + 4. for (let i = 0; i < size; i += 4) { // Making the difference +4 // for the odd indices if (i % 8 == 0) { arr[i] = low; arr[i + 2] = low + 3; arr[i + 1] = low + 1; arr[i + 3] = low + 2; } // Making the difference -4 for // odd indices +4 - 4 = 0 (balanced) else { arr[i] = low + 2; arr[i + 2] = low + 1; arr[i + 1] = low + 3; arr[i + 3] = low; } low += 4; } // Printing the array for (let i = 0; i < size; i++) { document.write(`${arr[i]} `); } } // Driver code let arr = [1, 2, 3, 4, 5, 6, 7, 8]; let N = arr.length; // Function call print_min(arr, N);// This code is contributed by rakeshsahni</script> |
Output
1 2 4 3 7 8 6 5
Time Complexity: O(N)
Auxiliary Space: O(1)
Another Approach:
- Divide the array into groups of size 8. (a)Since the given array has a length that is a multiple of 8, we can divide it into N/8 groups, where N is the length of the array.
- Arrange elements in each group as derived from the observation. (a)We can use the mathematical observation mentioned in the problem statement:
For any positive integer S, ( S )2 + ( S+3 )2 – 4 = ( S+1 )2 + ( S+2 )2
(b)We can use this formula to derive a sequence of numbers for each group of 8 elements that will keep the difference of sum of squares at odd and even indices zero.
(c)The sequence of each group can be like: S, S+1, S+3, S+2, S+6, S+7, S+5, S+4
(d)We can initialize S to be the minimum value in the array and then increment it by 4 for each group to get the above sequence.
- Return the rearranged array. (a)After arranging each group as described in step 2, we can return the rearranged array.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to find the minimum element in the arrayint findMin(int arr[], int size) { int minElement = INT_MAX; for (int i = 0; i < size; i++) { minElement = min(minElement, arr[i]); } return minElement;}// Function to rearrange the elements in each groupvoid rearrangeGroup(int arr[], int startValue) { // Using the formula: S, S+1, S+3, S+2, S+6, S+7, S+5, S+4 arr[0] = startValue; arr[1] = startValue + 1; arr[2] = startValue + 3; arr[3] = startValue + 2; arr[4] = startValue + 6; arr[5] = startValue + 7; arr[6] = startValue + 5; arr[7] = startValue + 4;}// Function to rearrange the arrayvoid rearrangeArray(int arr[], int size) { int minElement = findMin(arr, size); for (int i = 0; i < size; i += 8) { if (i % 16 == 0) { // For odd-indexed sum of squares > even-indexed sum of squares rearrangeGroup(&arr[i], minElement); } else { // For even-indexed sum of squares > odd-indexed sum of squares rearrangeGroup(&arr[i], minElement + 2); } minElement += 8; }}// Function to print the arrayvoid printArray(int arr[], int size) { for (int i = 0; i < size; i++) { cout << arr[i] << " "; } cout << endl;}// Driver codeint main() { int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; int size = sizeof(arr) / sizeof(arr[0]); // Rearrange the array rearrangeArray(arr, size); // Print the rearranged array printArray(arr, size); return 0;} |
Java
// Java Code to implement the approachimport java.util.*;public class GFG { // Function to find the minimum element in the array public static int findMin(int[] arr, int size) { int minElement = Integer.MAX_VALUE; for (int i = 0; i < size; i++) { minElement = Math.min(minElement, arr[i]); } return minElement; } // Function to rearrange the elements in each group public static void rearrangeGroup(int[] arr, int startValue) { // Using the formula: S, S+1, S+3, S+2, S+6, S+7, S+5, S+4 arr[0] = startValue; arr[1] = startValue + 1; arr[2] = startValue + 3; arr[3] = startValue + 2; arr[4] = startValue + 6; arr[5] = startValue + 7; arr[6] = startValue + 5; arr[7] = startValue + 4; } // Function to rearrange the array public static void rearrangeArray(int[] arr, int size) { int minElement = findMin(arr, size); for (int i = 0; i < size; i += 8) { if (i % 16 == 0) { // For odd-indexed sum of squares > even-indexed sum of squares rearrangeGroup(arr, minElement); } else { // For even-indexed sum of squares > odd-indexed sum of squares rearrangeGroup(arr, minElement + 2); } minElement += 8; } } // Function to print the array public static void printArray(int[] arr, int size) { for (int i = 0; i < size; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // Driver code public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8 }; int size = arr.length; // Rearrange the array rearrangeArray(arr, size); // Print the rearranged array printArray(arr, size); }} |
Python3
# Python3 Code to implement the approachimport sys# Function to find the minimum element in the arraydef findMin(arr, size): minElement = sys.maxsize for i in range(size): minElement = min(minElement, arr[i]) return minElement# Function to rearrange the elements in each groupdef rearrangeGroup(arr, startValue): # Using the formula: S, S+1, S+3, S+2, S+6, S+7, S+5, S+4 new_arr = [startValue, startValue + 1, startValue + 3, startValue + 2, startValue + 6, startValue + 7, startValue + 5, startValue + 4] return new_arr# Function to rearrange the arraydef rearrangeArray(arr, size): minElement = findMin(arr, size) for i in range(0, size, 8): if i % 16 == 0: # For odd-indexed sum of squares > even-indexed sum of squares new_arr = rearrangeGroup(arr[i:i+8], minElement) else: # For even-indexed sum of squares > odd-indexed sum of squares new_arr = rearrangeGroup(arr[i:i+8], minElement + 2) arr[i:i+8] = new_arr minElement += 8# Function to print the arraydef printArray(arr, size): for i in range(size): print(arr[i], end=" ") print()# Driver codeif __name__ == "__main__": arr = [1, 2, 3, 4, 5, 6, 7, 8] size = len(arr) # Rearrange the array rearrangeArray(arr, size) # Print the rearranged array printArray(arr, size) |
C#
using System;class GFG{ // Function to find the minimum element in the array static int FindMin(int[] arr, int size) { int minElement = int.MaxValue; for (int i = 0; i < size; i++) { minElement = Math.Min(minElement, arr[i]); } return minElement; } // Function to rearrange the elements in each group static void RearrangeGroup(int[] arr, int startValue) { // Using the formula: S, S+1, S+3, S+2, S+6, S+7, S+5, S+4 arr[0] = startValue; arr[1] = startValue + 1; arr[2] = startValue + 3; arr[3] = startValue + 2; arr[4] = startValue + 6; arr[5] = startValue + 7; arr[6] = startValue + 5; arr[7] = startValue + 4; } // Function to rearrange the array static void RearrangeArray(int[] arr, int size) { int minElement = FindMin(arr, size); for (int i = 0; i < size; i += 8) { if (i % 16 == 0) { // For odd-indexed sum of squares > even-indexed sum of squares RearrangeGroup(arr, minElement); } else { // For even-indexed sum of squares > odd-indexed sum of squares RearrangeGroup(arr, minElement + 2); } minElement += 8; } } // Function to print the array static void PrintArray(int[] arr, int size) { for (int i = 0; i < size; i++) { Console.Write(arr[i] + " "); } Console.WriteLine(); } // Driver code static void Main(string[] args) { int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8 }; int size = arr.Length; // Rearrange the array RearrangeArray(arr, size); // Print the rearranged array PrintArray(arr, size); }} |
Javascript
// JavaScript Code to implement the approach// Function to find the minimum element in the arrayfunction findMin(arr) { let minElement = Infinity; for (let i = 0; i < arr.length; i++) { minElement = Math.min(minElement, arr[i]); } return minElement;}// Function to rearrange the elements in each groupfunction rearrangeGroup(arr, startValue) { // Using the formula: S, S+1, S+3, S+2, S+6, S+7, S+5, S+4 arr[0] = startValue; arr[1] = startValue + 1; arr[2] = startValue + 3; arr[3] = startValue + 2; arr[4] = startValue + 6; arr[5] = startValue + 7; arr[6] = startValue + 5; arr[7] = startValue + 4;}// Function to rearrange the arrayfunction rearrangeArray(arr) { let minElement = findMin(arr); for (let i = 0; i < arr.length; i += 8) { if (i % 16 === 0) { // For odd-indexed sum of squares > even-indexed sum of squares rearrangeGroup(arr, minElement); } else { // For even-indexed sum of squares > odd-indexed sum of squares rearrangeGroup(arr, minElement + 2); } minElement += 8; }}// Function to print the arrayfunction printArray(arr) { console.log(arr.join(' '));}// Driver codelet arr = [1, 2, 3, 4, 5, 6, 7, 8];// Rearrange the arrayrearrangeArray(arr);// Print the rearranged arrayprintArray(arr); |
Output
1 2 4 3 7 8 6 5
Time Complexity: O(N), where N is the size of the array
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
