Factor de inversión mínimo en una array

Dada una array de n enteros positivos, la tarea es encontrar el factor inversor mínimo en la array dada. 
El factor de inversión se define como la diferencia absoluta entre el reverso de dos números arr _i y arr _j donde i != j. 
Nota : los ceros finales deben ignorarse al invertir los dígitos, es decir, 1200 se convierte en 21 cuando se invierte.
Ejemplos:
 

Entrada : arr[] = { 56, 20, 47, 93, 45 } 
Salida : 9 
El factor inversor mínimo es 9, del par (56, 47).
Entrada : arr[] = { 26, 15, 45, 150 } 
Salida : 0 
El factor inversor mínimo es 0, del par (15, 150). 
 

Un enfoque ingenuo es iterar sobre dos bucles para encontrar todos los pares posibles. Invierta ambos números individualmente y encuentre su diferencia absoluta. Actualice el factor de inversión (diferencia absoluta mínima) en cada paso. La Complejidad del Tiempo sería O(N ² ).
Un enfoque eficiente sería precalcular el reverso de cada elemento de la array y almacenarlo solo en su forma invertida (considerando también el caso de los ceros finales). Ahora, para encontrar el factor de inversión mínimo, ordene la array en orden no decreciente. Dado que la array está ordenada, siempre se produce una diferencia absoluta mínima entre dos números adyacentes cualesquiera. 
A continuación se muestra la implementación del enfoque anterior. 
 

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum inverting factor
int findMinimumInvertingFactor(int arr[], int N)
{
    // ans stores the minimum inverting factor
    int ans = INT_MAX;
 
    // Iterate over the loop and convert each
    // array element into its reversed form
    for (int i = 0; i < N; i++) {
        string s;
        int num = arr[i];
 
        // Extract each digit of the number and
        // store it in reverse order
        while (num > 0) {
            s.push_back(num % 10 + '0');
            num /= 10;
        }
 
        // Find the position upto which trailing
        // zeroes occur
        int pos;
        for (pos = 0; pos < s.size(); pos++)
            if (s[pos] != 0)
                break;
 
        // Form the reversed number
        num = 0;
        for (int j = pos; j < s.size(); j++)
            num = num * 10 + (s[j] - '0');
        arr[i] = num;
    }
    sort(arr, arr + N);
 
    // Consider all adjacent pairs and update the
    // answer accordingly
    for (int i = 1; i < N; i++)
        ans = min(ans, abs(arr[i] - arr[i - 1]));
 
    return ans;
}
 
// Driver Code
int main()
{
    int arr[] = { 56, 20, 47, 93, 45 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << findMinimumInvertingFactor(arr, N) << endl;
    return 0;
}

// Java implementation of the above approach
import java.util.*;
 
class GFG
{
     
// Function to find the minimum inverting factor
static int findMinimumInvertingFactor(int arr[], int N)
{
    // ans stores the minimum inverting factor
    int ans = Integer.MAX_VALUE;
 
    // Iterate over the loop and convert each
    // array element into its reversed form
    for (int i = 0; i < N; i++)
    {
        String s = "";
        int num = arr[i];
 
        // Extract each digit of the number and
        // store it in reverse order
        while (num > 0)
        {
            s+=(char)((num % 10) + '0');
            num /= 10;
        }
 
        // Find the position upto which trailing
        // zeroes occur
        int pos;
        for (pos = 0; pos < s.length(); pos++)
            if (s.charAt(pos) != 0)
                break;
 
        // Form the reversed number
        num = 0;
        for (int j = pos; j < s.length(); j++)
            num = num * 10 + (s.charAt(j) - '0');
        arr[i] = num;
    }
    Arrays.sort(arr);
 
    // Consider all adjacent pairs and update the
    // answer accordingly
    for (int i = 1; i < N; i++)
        ans = Math.min(ans, Math.abs(arr[i] - arr[i - 1]));
 
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 56, 20, 47, 93, 45 };
    int N = arr.length;
 
    System.out.println(findMinimumInvertingFactor(arr, N));
}
}
 
// This code contributed by Rajput-Ji

# Python3 implementation of the above approach
 
import sys
 
# Function to find the minimum inverting factor
def findMinimumInvertingFactor(arr, N) :
     
    # ans stores the minimum inverting factor
    ans = sys.maxsize
 
    # Iterate over the loop and convert each
    # array element into its reversed form
    for i in range(N) :
        num = arr[i]
        s = ""
 
        # Extract each digit of the number and
        # store it in reverse order
        while (num > 0) :
            s += str(num % 10)
            num //= 10
          
 
        # Find the position upto which trailing
        # zeroes occur
        for pos in range(len(s)) :
            if (s[pos] != "0") :
                break;
 
        # Form the reversed number
        num = 0
        for j in range(pos, len(s)) :
            num = num * 10 + (ord(s[j]) - ord("0"))
        arr[i] = num
      
    arr.sort()
    # Consider all adjacent pairs and update the
    # answer accordingly
    for i in range(N) :
        ans = min(ans, abs(arr[i] - arr[i - 1]))
 
    return ans
  
 
# Driver Code
if __name__ == "__main__" :
 
    arr= [ 56, 20, 47, 93, 45 ]
    N = len(arr)
     
    print(findMinimumInvertingFactor(arr, N))
 
# This code is contributed by Ryuga

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function to find the minimum inverting factor
static int findMinimumInvertingFactor(int []arr, int N)
{
    // ans stores the minimum inverting factor
    int ans = int.MaxValue;
 
    // Iterate over the loop and convert each
    // array element into its reversed form
    for (int i = 0; i < N; i++)
    {
        String s = "";
        int num = arr[i];
 
        // Extract each digit of the number and
        // store it in reverse order
        while (num > 0)
        {
            s+=(char)((num % 10) + '0');
            num /= 10;
        }
 
        // Find the position upto which trailing
        // zeroes occur
        int pos;
        for (pos = 0; pos < s.Length;pos++)
            if (s[pos] != 0)
                break;
 
        // Form the reversed number
        num = 0;
        for (int j = pos; j < s.Length; j++)
            num = num * 10 + (s[j] - '0');
        arr[i] = num;
    }
    Array.Sort(arr);
 
    // Consider all adjacent pairs and update the
    // answer accordingly
    for (int i = 1; i < N; i++)
        ans = Math.Min(ans, Math.Abs(arr[i] - arr[i - 1]));
 
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 56, 20, 47, 93, 45 };
    int N = arr.Length;
 
    Console.WriteLine(findMinimumInvertingFactor(arr, N));
}
}
 
/* This code contributed by PrinciRaj1992 */

<?php
// PHP implementation of the above approach
 
// Function to find the minimum inverting factor
function findMinimumInvertingFactor($arr, $N)
{
    // ans stores the minimum inverting factor
    $ans = PHP_INT_MAX;
 
    // Iterate over the loop and convert each
    // array element into its reversed form
    for ($i = 0; $i < $N; $i++)
    {
        $s="";
        $num = $arr[$i];
 
        // Extract each digit of the number and
        // store it in reverse order
        while ($num > 0)
        {
            $s.=chr($num % 10 + ord('0'));
            $num =(int)($num/10);
        }
 
        // Find the position upto which trailing
        // zeroes occur
        for ($pos = 0; $pos < strlen($s); $pos++)
            if ($s[$pos] != 0)
                break;
 
        // Form the reversed number
        $num = 0;
        for ($j = $pos; $j < strlen($s); $j++)
            $num = $num * 10 + (ord($s[$j]) - ord('0'));
        $arr[$i] = $num;
    }
    sort($arr);
 
    // Consider all adjacent pairs and update the
    // answer accordingly
    for ($i = 1; $i < $N; $i++)
        $ans = min($ans, abs($arr[$i] - $arr[$i - 1]));
 
    return $ans;
}
 
// Driver Code
 
$arr = array( 56, 20, 47, 93, 45 );
$N = count($arr);
 
echo findMinimumInvertingFactor($arr, $N)."\n";
 
// This code is contributed by mits
?>

<script>
    // Javascript implementation of the approach
     
    // Function to find the minimum inverting factor
    function findMinimumInvertingFactor(arr, N)
    {
     
        // ans stores the minimum inverting factor
        let ans = Number.MAX_VALUE;
 
        // Iterate over the loop and convert each
        // array element into its reversed form
        for (let i = 0; i < N; i++)
        {
            let s = "";
            let num = arr[i];
 
            // Extract each digit of the number and
            // store it in reverse order
            while (num > 0)
            {
                s+=String.fromCharCode((num % 10) + '0'.charCodeAt());
                num = parseInt(num / 10, 10);
            }
 
            // Find the position upto which trailing
            // zeroes occur
            let pos;
            for (pos = 0; pos < s.length;pos++)
                if (s[pos] != 0)
                    break;
 
            // Form the reversed number
            num = 0;
            for (let j = pos; j < s.length; j++)
                num = num * 10 + (s[j].charCodeAt() - '0'.charCodeAt());
            arr[i] = num;
        }
        arr.sort(function(a, b){return a - b});
 
        // Consider all adjacent pairs and update the
        // answer accordingly
        for (let i = 1; i < N; i++)
            ans = Math.min(ans, Math.abs(arr[i] - arr[i - 1]));
 
        return ans;
    }
     
    let arr = [ 56, 20, 47, 93, 45 ];
    let N = arr.length;
   
    document.write(findMinimumInvertingFactor(arr, N));
     
    // This code is contributed by decode2207.
</script>

9

Complejidad de tiempo : O (N * logN)