Suma mínima de diferencias absolutas entre pares de un triplete de una array

Dada una array A[] que consiste en números enteros positivos, la tarea es encontrar el valor mínimo de |A[x] – A[y]| + |A[y] – A[z]| de cualquier triplete (A[x], A[y], A[z]) de una array.

Ejemplos:

Entrada: A[] = { 1, 1, 2, 3 }
Salida: 1
Explicación:
Para x = 0, y = 1, z = 2
|A[x] – A[y]| + |A[y] – A[z]| = 0 + 1 = 1, que es el máximo posible

Entrada: A[] = { 1, 1, 1 }
Salida: 0

Enfoque : El problema se puede resolver con avidez . Siga los pasos a continuación para resolver el problema:

1. Atraviesa la array .
2. Ordene la array en orden ascendente .
3. Recorra la array usando una variable i sobre índices [0, N – 3] . Para cada i ^-ésimo índice, establezca x = i, y = i + 1, z = i + 2
4. Calcula la suma del triplete (x, y, z) .
5. Actualice la suma mínima posible.
6. Imprimir la suma mínima obtenida.

A continuación se muestra la implementación del enfoque anterior:

// C++ Program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum
// sum of absolute differences
// of pairs of a triplet
int minimum_sum(int A[], int N)
{
    // Sort the array
    sort(A, A + N);
 
    // Stores the minimum sum
    int sum = INT_MAX;
 
    // Traverse the array
    for (int i = 0; i <= N - 3; i++) {
 
        // Update the minimum sum
        sum = min(sum,
                  abs(A[i] - A[i + 1]) +
                  abs(A[i + 1] - A[i + 2]));
    }
 
    // Print the minimum sum
    cout << sum;
}
 
// Driver Code
int main()
{
 
    // Input
    int A[] = { 1, 1, 2, 3 };
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function call to find minimum
    // sum of absolute differences
    // of pairs in a triplet
    minimum_sum(A, N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG
{
   
// Function to find minimum
// sum of absolute differences
// of pairs of a triplet
static int minimum_sum(int []A, int N)
{
   
    // Sort the array
    Arrays.sort(A);
 
    // Stores the minimum sum
 
    int sum = 2147483647;
 
    // Traverse the array
    for (int i = 0; i <= N - 3; i++) {
 
        // Update the minimum sum
        sum = Math.min(sum,Math.abs(A[i] - A[i + 1]) + Math.abs(A[i + 1] - A[i + 2]));
    }
 
    // Print the minimum sum
    return sum;
}
 
// Driver Code
public static void main(String[] args)
{
   
    // Input
    int []A = { 1, 1, 2, 3 };
    int N = A.length;
 
    // Function call to find minimum
    // sum of absolute differences
    // of pairs in a triplet
    System.out.print(minimum_sum(A, N));
}
}
 
// This code is contributed by splevel62.

# Python 3 Program for the above approach
import sys
 
# Function to find minimum
# sum of absolute differences
# of pairs of a triplet
def minimum_sum(A, N):
   
    # Sort the array
    A.sort(reverse = False)
 
    # Stores the minimum sum
    sum = sys.maxsize
 
    # Traverse the array
    for i in range(N - 2):
       
        # Update the minimum sum
        sum = min(sum, abs(A[i] - A[i + 1]) + abs(A[i + 1] - A[i + 2]))
 
    # Print the minimum sum
    print(sum)
 
# Driver Code
if __name__ == '__main__':
   
    # Input
    A = [1, 1, 2, 3]
    N = len(A)
 
    # Function call to find minimum
    # sum of absolute differences
    # of pairs in a triplet
    minimum_sum(A, N)
     
    # This code is contributed by ipg2016107

// C# Program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
    
// Function to find minimum
// sum of absolute differences
// of pairs of a triplet
static int minimum_sum(int []A, int N)
{
   
    // Sort the array
    Array.Sort(A);
 
    // Stores the minimum sum
 
    int sum = 2147483647;
 
    // Traverse the array
    for (int i = 0; i <= N - 3; i++) {
 
        // Update the minimum sum
        sum = Math.Min(sum,Math.Abs(A[i] - A[i + 1]) + Math.Abs(A[i + 1] - A[i + 2]));
    }
 
    // Print the minimum sum
    return sum;
}
 
// Driver Code
public static void Main()
{
 
    // Input
    int []A = { 1, 1, 2, 3 };
    int N = A.Length;
 
    // Function call to find minimum
    // sum of absolute differences
    // of pairs in a triplet
    Console.WriteLine(minimum_sum(A, N));
}
}
 
// This code is contributed by bgangwar59.

<script>
 
// Javascript Program for the above approach
 
// Function to find minimum
// sum of absolute differences
// of pairs of a triplet
function minimum_sum( A, N)
{
    // Sort the array
    A.sort();
 
    // Stores the minimum sum
    var sum = 1000000000;
 
    // Traverse the array
    for (var i = 0; i <= N - 3; i++) {
 
        // Update the minimum sum
        sum = Math.min(sum,
                  Math.abs(A[i] - A[i + 1]) +
                  Math.abs(A[i + 1] - A[i + 2]));
    }
 
    // Print the minimum sum
    document.write(sum);
}
 
// Driver Code
// Input
var A = [ 1, 1, 2, 3 ];
var N = A.length;
// Function call to find minimum
// sum of absolute differences
// of pairs in a triplet
minimum_sum(A, N);
 
 
</script>

1

Complejidad de tiempo : O(N * logN)
Espacio auxiliar : O(1)