Cuente los pares de elementos indexados de la misma paridad con el mismo MSD después de reemplazar cada elemento por la suma del dígito máximo * A y los dígitos mínimos * B

Dada una array arr[] de N enteros de 3 dígitos y dos enteros a y b , la tarea es modificar cada elemento de la array de acuerdo con las siguientes reglas:

• Encuentre el máximo, digamos M, y el dígito mínimo, digamos m , de cada elemento de la array arr[i] .
• Actualice el elemento de array arr[i] como (A * M + B * m) .

La tarea es contar el número de pares de modo que los elementos elegidos sean solo índices pares o impares y los dígitos más significativos (MSD) deben ser iguales y el número de pares formados a partir de ese MSD es como máximo 2 .

Ejemplos:

Entrada: arr[] = {234, 567, 321, 345, 123, 110, 767, 111}, N = 8, A = 11, B = 7
Salida: 3
Explicación:
Modifique los elementos de la array mediante las siguientes operaciones:

• Los dígitos máximo y mínimo de arr[0] (= 234) son 4 y 2 respectivamente. Por lo tanto, reemplace arr[0] por 11 * 4 + 7 * 2 = 58.
• Los dígitos máximo y mínimo de arr[1] (= 567) son 7 y 5 respectivamente. Por lo tanto, reemplaza arr[1] por 11 * 7 + 7 * 5 = 77 + 35 = 112.
• Los dígitos máximo y mínimo de arr[2] (= 321) y arr[4] (= 123) son 3 y 1 respectivamente. Por lo tanto, reemplácelos por 11 * 3 + 7 * 1 = 40.
• Los dígitos máximo y mínimo de arr[3] (= 345) son 5 y 3 respectivamente. Por lo tanto, reemplaza arr[3] por 11 * 5 + 7 * 3 = 76.
• Los dígitos máximo y mínimo de arr[5] (= 110) son 1 y 0 respectivamente. Por lo tanto, reemplace arr[5] por 11 * 1 + 7 * 0 = 11.
• Los dígitos máximo y mínimo de arr[6] (= 767) son 7 y 6 respectivamente. Por lo tanto, reemplaza arr[6] por 11 * 7 + 7 * 6 = 77 + 42 = 119.
• Los dígitos máximo y mínimo de arr[7] (= 111) son 1 y 2 respectivamente. Por lo tanto, reemplaza arr[7] por 11 * 1 + 7 * 1 = 18.

Por lo tanto, la array arr[] se modifica a {58, 12, 40, 76, 40, 11, 19, 18].
Una forma posible de formar parejas es {{40, 40}, {12, 11}, {11, 18}}.

Entrada: arr[] = {123, 452, 345, 124, 453}, N = 5, A = 11, B = 7
Salida: 1

Enfoque: El problema dado se puede resolver usando una array de frecuencias . Siga los pasos a continuación para resolver el problema dado:

• Actualice cada elemento de array de arr[] con (A * X + B * Y)%100 buscando el dígito mínimo y máximo del elemento , donde X e Y son los dígitos máximo y mínimo de arr[i].
• Inicialice una array 2D , digamos mp[10][2], para almacenar el recuento de números con MSD en posiciones pares e impares por separado.
• Recorra la array arr[] e incremente el recuento de mp[arr[i]/10][i%2] en 1 .
• Inicialice una variable, digamos res , para almacenar el conteo resultante de pares.
• Iterar sobre el rango [0, 9] y realizar los siguientes pasos:
  • Incremente el recuento de res en 2 si existen al menos 3 números con i como MSD en índices pares o índices impares, es decir, mp[i][0] >= 3 || MP[i][1] >= 3 .
  • De lo contrario, si existe un par en índices impares y un par en índices pares, es decir, mp[i][0] == 2 && mp[i][1] == 2 , entonces incremente la cuenta de res en 2 .
  • De lo contrario, si existe un par en índices impares o índices pares con MSD como i , es decir, mp[i][0] == 2 || mp[i][1] == 2 , luego incremente el conteo de res en 1 .
• Después de completar los pasos anteriores, imprima el valor de res como el conteo de pares.

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 modify N into
// A * max digit + B * min digit
// and calculate score
int bit_score(int N)
{
    // Stores maximum and minimum digit
    int maxi = 0, mini = 11;
   
    // Stores the val of N
    int score;
   
      // Find the maximum and minimum digits
    for (int i = 0; i < 3; i++) {
       
          // Update maximum digit
        maxi = max(maxi, N % 10);
           
          // Update minimum digit
        mini = min(mini, N % 10);
        N /= 10;
        if (N == 0)
            break;
    }
   
    // Calculate the modified number
    score = maxi * 11 + mini * 7;
   
      // Extract last two digits
    score = score % 100;
   
      // Return the final score
    return score;
}
 
// Function to count the number of
// pairs possible from either odd
// or even indices having same MSD
int findPairs(int arr[], int N, int a, int b)
{
    // Update the array
    for (int i = 0; i < N; i++) {
        arr[i] = bit_score(arr[i]);
    }
   
    // Stores the total number of pairs
    int pairs = 0;
 
    // Stores the count of numbers having
    // MSD at even or odd position separately
    int mp[10][2];
   
    // Initialize all elements as 0
    memset(mp, 0, sizeof(mp));
 
    // Calculate the count of a MSD
    // at even and odd positions
    for (int i = 0; i < N; i++)
        mp[arr[i] / 10][i % 2]++;
 
    // Iterate over range [0, 9]
    for (int i = 0; i < 10; i++) {
 
        if (mp[i][1] >= 3 || mp[i][0] >= 3)
            pairs += 2;
        else if (mp[i][1] == 2 && mp[i][0] == 2)
            pairs += 2;
        else if (mp[i][1] == 2 || mp[i][0] == 2)
            pairs += 1;
    }
   
    // Return the resultant count of pairs
    return pairs;
}
 
// Driver Code
int main()
{
    int arr[] = { 234, 567, 321, 345,
                  123, 110, 767, 111 };
    int N = sizeof(arr) / sizeof(arr[0]);
      int a = 11, b = 7;
   
    cout << findPairs(arr, N, a, b);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to modify N into
  // A * max digit + B * min digit
  // and calculate score
  static int bit_score(int N)
  {
    // Stores maximum and minimum digit
    int maxi = 0, mini = 11;
 
    // Stores the val of N
    int score;
 
    // Find the maximum and minimum digits
    for (int i = 0; i < 3; i++) {
 
      // Update maximum digit
      maxi = Math.max(maxi, N % 10);
 
      // Update minimum digit
      mini = Math.min(mini, N % 10);
      N /= 10;
      if (N == 0)
        break;
    }
 
    // Calculate the modified number
    score = maxi * 11 + mini * 7;
 
    // Extract last two digits
    score = score % 100;
 
    // Return the final score
    return score;
  }
 
  // Function to count the number of
  // pairs possible from either odd
  // or even indices having same MSD
  static int findPairs(int arr[], int N, int a, int b)
  {
    // Update the array
    for (int i = 0; i < N; i++) {
      arr[i] = bit_score(arr[i]);
    }
 
    // Stores the total number of pairs
    int pairs = 0;
 
    // Stores the count of numbers having
    // MSD at even or odd position separately
    int mp[][] = new int[10][2];
 
    // Calculate the count of a MSD
    // at even and odd positions
    for (int i = 0; i < N; i++)
      mp[arr[i] / 10][i % 2]++;
 
    // Iterate over range [0, 9]
    for (int i = 0; i < 10; i++) {
 
      if (mp[i][1] >= 3 || mp[i][0] >= 3)
        pairs += 2;
      else if (mp[i][1] == 2 && mp[i][0] == 2)
        pairs += 2;
      else if (mp[i][1] == 2 || mp[i][0] == 2)
        pairs += 1;
    }
 
    // Return the resultant count of pairs
    return pairs;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    int arr[] = { 234, 567, 321, 345, 123, 110, 767, 111 };
    int N = arr.length;
    int a = 11, b = 7;
 
    System.out.println(findPairs(arr, N, a, b));
  }
}
 
// This code is contributed by Kingash.

# Python3 program for the above approach
 
# Function to modify N into
# A * max digit + B * min digit
# and calculate score
def bit_score(N):
   
    # Stores maximum and minimum digit
    maxi , mini = 0, 11
 
    # Stores the val of N
    score = 0
 
      # Find the maximum and minimum digits
    for i in range(3):
 
          # Update maximum digit
        maxi = max(maxi, N % 10)
 
          # Update minimum digit
        mini = min(mini, N % 10)
        N //= 10
        if (N == 0):
            break
 
    # Calculate the modified number
    score = maxi * 11 + mini * 7
 
      # Extract last two digits
    score = score % 100
 
      # Return the final score
    return score
 
# Function to count the number of
# pairs possible from either odd
# or even indices having same MSD
def findPairs(arr, N, a, b):
    #Update the array
    for i in range(N):
        arr[i] = bit_score(arr[i])
 
    # Stores the total number of pairs
    pairs = 0
 
    # Stores the count of numbers having
    # MSD at even or odd position separately
    mp = [[0 for i in range(2)] for i in range(10)]
 
    # Initialize all elements as 0
    # memset(mp, 0, sizeof(mp))
 
    # Calculate the count of a MSD
    # at even and odd positions
    for i in range(N):
        mp[arr[i] // 10][i % 2] += 1
 
    # Iterate over range [0, 9]
    for i in range(10):
        if (mp[i][1] >= 3 or mp[i][0] >= 3):
            pairs += 2
        elif (mp[i][1] == 2 and mp[i][0] == 2):
            pairs += 2
        elif (mp[i][1] == 2 or mp[i][0] == 2):
            pairs += 1
 
    # Return the resultant count of pairs
    return pairs
 
# Driver Code
if __name__ == '__main__':
    arr = [234, 567, 321, 345, 123, 110, 767, 111]
    N = len(arr)
    a, b = 11, 7
 
    print (findPairs(arr, N, a, b))
 
# This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
 
class GFG{
 
// Function to modify N into
// A * max digit + B * min digit
// and calculate score
static int bit_score(int N)
{
     
    // Stores maximum and minimum digit
    int maxi = 0, mini = 11;
     
    // Stores the val of N
    int score;
     
    // Find the maximum and minimum digits
    for(int i = 0; i < 3; i++)
    {
     
        // Update maximum digit
        maxi = Math.Max(maxi, N % 10);
         
        // Update minimum digit
        mini = Math.Min(mini, N % 10);
        N /= 10;
         
        if (N == 0)
            break;
    }
     
    // Calculate the modified number
    score = maxi * 11 + mini * 7;
     
    // Extract last two digits
    score = score % 100;
     
    // Return the final score
    return score;
}
     
// Function to count the number of
// pairs possible from either odd
// or even indices having same MSD
static int findPairs(int[] arr, int N,
                     int a, int b)
{
     
    // Update the array
    for(int i = 0; i < N; i++)
    {
        arr[i] = bit_score(arr[i]);
    }
     
    // Stores the total number of pairs
    int pairs = 0;
     
    // Stores the count of numbers having
    // MSD at even or odd position separately
    int[,] mp = new int[10, 2];
     
    // Calculate the count of a MSD
    // at even and odd positions
    for(int i = 0; i < N; i++)
        mp[arr[i] / 10, i % 2]++;
     
    // Iterate over range [0, 9]
    for(int i = 0; i < 10; i++)
    {
        if (mp[i, 1] >= 3 || mp[i, 0] >= 3)
            pairs += 2;
        else if (mp[i, 1] == 2 && mp[i, 0] == 2)
            pairs += 2;
        else if (mp[i, 1] == 2 || mp[i, 0] == 2)
            pairs += 1;
    }
     
    // Return the resultant count of pairs
    return pairs;
}
 
// Driver Code
public static void Main()
{
    int[] arr = { 234, 567, 321, 345,
                  123, 110, 767, 111 };
    int N = arr.Length;
    int a = 11, b = 7;
 
    Console.Write(findPairs(arr, N, a, b));
}
}
 
// This code is contributed by sanjoy_62

<script>
 
// Javascript program for the above approach
 
// Function to modify N into
// A * max digit + B * min digit
// and calculate score
function bit_score(N)
{
     
    // Stores maximum and minimum digit
    let maxi = 0, mini = 11;
     
    // Stores the val of N
    let score;
     
    // Find the maximum and minimum digits
    for(let i = 0; i < 3; i++)
    {
         
        // Update maximum digit
        maxi = Math.max(maxi, N % 10);
         
        // Update minimum digit
        mini = Math.min(mini, N % 10);
        N /= 10;
         
        if (N == 0)
            break;
    }
     
    // Calculate the modified number
    score = maxi * 11 + mini * 7;
     
    // Extract last two digits
    score = score % 100;
     
    // Return the final score
    return score;
}
     
// Function to count the number of
// pairs possible from either odd
// or even indices having same MSD
function findPairs(arr, N, a, b)
{
     
    // Update the array
    for(let i = 0; i < N; i++)
    {
        arr[i] = bit_score(arr[i]);
    }
     
    // Stores the total number of pairs
    let pairs = 0;
     
    // Stores the count of numbers having
    // MSD at even or odd position separately
    let mp = new Array(10);
     
    // Loop to create 2D array using 1D array
    for (let i = 0; i < mp.length; i++)
    {
        mp[i] = new Array(2);
    }
     
    for(let i = 0; i < mp.length; i++)
    {
        for(let j = 0; j < mp.length; j++)
        {
            mp[i][j] = 0;
        }
    }
     
    // Calculate the count of a MSD
    // at even and odd positions
    for(let i = 0; i < N; i++)
        mp[Math.floor(arr[i] / 10)][i % 2]++;
     
    // Iterate over range [0, 9]
    for(let i = 0; i < 10; i++)
    {
        if (mp[i][1] >= 3 ||
            mp[i][0] >= 3)
            pairs += 2;
        else if (mp[i][1] == 2 &&
                 mp[i][0] == 2)
            pairs += 2;
        else if (mp[i][1] == 2 ||
                 mp[i][0] == 2)
            pairs += 1;
    }
     
    // Return the resultant count of pairs
    return pairs;
}
 
// Driver code
 
// Given Input
let arr = [ 234, 567, 321, 345,
            123, 110, 767, 111 ];
let N = arr.length;
let a = 11, b = 7;
 
document.write(findPairs(arr, N, a, b));
 
// This code is contributed by target_2 
 
</script>

3

Complejidad temporal: O(N)
Espacio auxiliar: O(1)