Dada una array arr[] de tamaño N (múltiplo de 8) donde los valores de la array estarán en el rango [a, (a+8*N) -1] ( a puede ser cualquier número entero positivo), la tarea es reorganizar la array de manera que la diferencia entre la suma de los cuadrados de los índices impares y la suma de los cuadrados de los elementos de los índices pares sea la mínima entre todas las reorganizaciones posibles.
Nota: si hay múltiples reordenamientos, devuelva cualquiera de ellos.
Ejemplos :
Entrada : arr[] = {1, 2, 3, 4, 5, 6, 7, 8}
Salida : 1 2 4 3 7 8 6 5
Explicación: La diferencia es 0 como 1 + 4 2 + 7 2 + 6 2 = 102 = 2 2 + 3 2 + 8 2 + 5 2Entrada : arr[] = { 9, 11, 12, 15, 16, 13, 10, 14}
Salida : 9 10 12 11 15 16 14 13
Explicación: La diferencia es 0 como 9 2 + 12 2 + 15 2 + 14 2 = 10 2 + 11 2 + 16 2 + 13 2 = 646
Enfoque: Este problema se puede resolver con base en la siguiente observación matemática:
Para cualquier entero positivo S, ( S ) 2 + ( S+3 ) 2 – 4 = ( S+1 ) 2 + ( S+2 ) 2 . Como N es un múltiplo de 8, se puede dividir en N/8 grupos donde la diferencia de la suma de los cuadrados de los elementos en los índices pares e impares para cada grupo es 0 .
Para los primeros cuatro elementos mantenga mayor la suma de cuadrados de índices impares y cuatro los cuatro siguientes justo al contrario para mantener mayor la suma de cuadrados de índices pares. Entonces este grupo de 8 elementos tendrá diferencia 0 . Como se hace lo mismo para todos los grupos N/8, la diferencia global será 0 .La secuencia de cada grupo puede ser como: S, S+1, S+3, S+2, S+6, S+7, S+5, S+4
Siga los pasos a continuación para resolver este problema:
- Divida la array en grupos de tamaño 8.
- Ordene los elementos en cada grupo como derivados de la observación.
- Devuelve la array reorganizada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find
// maximum element of the array
int 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 array
int 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 array
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++) {
cout << arr[i] << " ";
}
}
// Driver code
int 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 approach
import 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 approach INT_MIN = -2147483647 - 1 INT_MAX = 2147483647 # Function to find # maximum element of the array def 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 array def minimum(arr, size): mi = INT_MAX for i in range(size): mi = min(mi, arr[i]) return mi # Function to print the array def 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 code arr = [1, 2, 3, 4, 5, 6, 7, 8] N = len(arr) # Function call print_min(arr, N) # This code is contributed by shinjanpatra
C#
// C# code to implement the approach
using 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>
1 2 4 3 7 8 6 5
Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por sapu10lm39 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA