Identidad de Proizvolov

Dadas dos arrays A y B de tamaño N . La array A está en orden creciente y la B en orden decreciente. Ambos arreglos son las subsecuencias de los números del 1 al 2N . La tarea es encontrar la suma de la diferencia absoluta de dos arrays.
 

Suma = |A ₁ – B ₁ | + |A ₂ – B ₂ | + |A ₃ – B ₃ | + …. + |A _N – B _N | 
 

Ejemplos: 
 

Entrada: A[] = {1, 2, 3, 4, 5}, B[] = {10, 9, 8, 7, 6} 
Salida: 25
Entrada: A[] = {1, 5, 6, 8 , 10, 12}, B[] = {11, 9, 7, 4, 3, 2} 
Salida: 36 
 

Enfoque ingenuo: un enfoque ingenuo es ejecutar un ciclo y encontrar la suma de las diferencias absolutas.
Enfoque eficiente: la identidad de Proizvolov es una identidad relativa a las sumas de las diferencias de números enteros positivos. Establece que si tomamos los primeros 2N enteros y los dividimos en dos subconjuntos de N números cada uno. 
Organice un subconjunto en orden creciente: A ₁ < A ₂ < A ₃ < …. < A _N
Ordene otro subconjunto en orden decreciente: B ₁ > B ₂ > B ₃ > …. > B _N
Entonces la suma |A ₁ – B₁ | + |A ₂ – B ₂ | + |A ₃ – B ₃ | + …. + |A _N – B _N | siempre es igual a N ²
A continuación se muestra la implementación del enfoque anterior: 
 

// CPP program to implement proizvolov's identity
#include<bits/stdc++.h>
using namespace std;
 
// Function to implement proizvolov's identity
int proizvolov(int a[], int b[], int n)
{
    // According to proizvolov's identity
    return n*n;
}
 
// Driver code
int main()
{
    int a[] = {1, 5, 6, 8, 10}, b[] = {9, 7, 4, 3, 2};
     
    int n = sizeof(a) / sizeof(a[0]);
     
    // Function call
    cout << proizvolov(a, b, n);
     
    return 0;
}

// Java program to implement proizvolov's identity
class GFG
{
    // Function to implement proizvolov's identity
    static int proizvolov(int a [], int b [], int n)
    {
        // According to proizvolov's identity
        return n * n;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int a [] = {1, 5, 6, 8, 10};
        int b [] = {9, 7, 4, 3, 2};
         
        int n = a.length;
         
        // Function call
        System.out.println(proizvolov(a, b, n));
    }
}
 
// This code is contributed by ihritik

# Python3 program to implement
# proizvolov's identity
 
# Function to implement
# proizvolov's identity
def proizvolov(a, b, n):
    return n * n
 
# Driver code
a = [ 1, 5, 6, 8, 10 ]
b = [ 9, 7, 4, 3, 2 ]
n = len(a)
 
# Function call
print(proizvolov(a, b, n, ))
 
# This code is contributed by nidhiva

// C# program to implement proizvolov's identity
using System;
 
class GFG
{
    // Function to implement proizvolov's identity
    static int proizvolov(int [] a,
                          int [] b, int n)
    {
        // According to proizvolov's identity
        return n * n;
    }
     
    // Driver code
    public static void Main ()
    {
        int [] a = {1, 5, 6, 8, 10};
        int [] b = {9, 7, 4, 3, 2};
         
        int n = a.Length;
         
        // Function call
        Console.WriteLine(proizvolov(a, b, n));
    }
}
 
// This code is contributed by ihritik

<script>
 
// Javascript program to implement
// proizvolov's identity
 
// Function to implement proizvolov's identity
function proizvolov(a, b, n)
{
    // According to proizvolov's identity
    return n*n;
}
 
// Driver code
    let a = [1, 5, 6, 8, 10], b = [9, 7, 4, 3, 2];
     
    let n = a.length;
     
    // Function call
    document.write(proizvolov(a, b, n));
 
</script>

25