El entero de K dígito más grande de la array dada divisible por M

Dada una array arr[] de tamaño N y 2 enteros K y M , la tarea es encontrar el mayor número entero de K dígitos de la array arr[] que es divisible por M. Imprima -1 si es imposible encontrar tal número entero.

Nota: El valor de K es tal que el entero encontrado siempre es menor o igual que INT_MAX.

Ejemplos:

Entrada: arr[] = {1, 2, 3, 4, 5, 6}, N=6, K=3, M=4
Salida: 652
Explicación: El mayor de 3 dígitos está formado por los dígitos 6, 5, 2 con sus índices 1, 4 y 5.

Entrada: arr[] = {4, 5, 4}, N=3, K=3, M=50
Salida: -1
Explicación : – No existe ningún número entero de la array que sea divisible por 50 ya que no hay 0.

Enfoque ingenuo : esto se puede hacer encontrando todas las subsecuencias de tamaño K y luego verificando la condición para encontrar la más grande.
Complejidad de Tiempo : O(2 N )
Espacio Auxiliar : O(1)

Enfoque eficiente : la idea es verificar cada número en múltiplo de M en la array para saber si es posible formar ese número o no. Si es posible, actualice la respuesta. Siga los pasos a continuación para resolver el problema:

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

C++14

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the largest integer
// of K digits divisible by M
void find(vector<int>& arr, int N, int K, int M)
{
 
    // Base Case, as there is no sub-sequence
    // of size greater than N is possible
    if (K > N) {
        cout << "-1\n";
        return;
    }
 
    // Vector to store the frequency of each
    // number from the array
    vector<int> freq(10, 0);
 
    // Calculate the frequency of each from
    // the array
    for (int i = 0; i < N; i++) {
        freq[arr[i]]++;
    }
 
    // Sort the array in ascending order
    sort(arr.begin(), arr.end());
 
    // Variable to store the maximum number
    // possible
    int X = 0;
 
    // Traverse and store the largest K digits
    for (int i = N - 1; K > 0; i--) {
        X = X * 10 + arr[i];
        K--;
    }
 
    // Base Case
    if (X < M) {
        cout << "-1\n";
        return;
    }
 
    // Variable to store the answer
    int answer = -1;
 
    // Traverse and check for each number
    for (int i = M; i <= X; i = i + M) {
        int y = i;
        vector<int> v(10, 0);
 
        // Calculate the frequency of each number
        while (y > 0) {
            v[y % 10]++;
            y = y / 10;
        }
 
        bool flag = true;
 
        // If frequency of any digit in y is less than
        // that in freq[], then it's not possible.
        for (int j = 0; j <= 9; j++) {
            if (v[j] > freq[j]) {
                flag = false;
                break;
            }
        }
 
        if (flag)
            answer = max(answer, i);
    }
 
    // Print the answer
    cout << answer << endl;
}
 
// Driver Code
int main()
{
 
    vector<int> arr = { 1, 2, 3, 4, 5, 6 };
    int N = 6, K = 3, M = 4;
 
    find(arr, N, K, M);
 
    return 0;
}

Java

// Java code for the above approach
import java.io.*;
import java.util.Arrays;;
class GFG
{
   
    // Function to find the largest integer
    // of K digits divisible by M
    static void find(int[] arr, int N, int K, int M)
    {
 
        // Base Case, as there is no sub-sequence
        // of size greater than N is possible
        if (K > N) {
            System.out.println("-1\n");
            return;
        }
 
        // Vector to store the frequency of each
        // number from the array
        int freq[] = new int[10];
 
        // Calculate the frequency of each from
        // the array
        for (int i = 0; i < N; i++) {
            freq[arr[i]]++;
        }
 
        // Sort the array in ascending order
        Arrays.sort(arr);
 
        // Variable to store the maximum number
        // possible
        int X = 0;
 
        // Traverse and store the largest K digits
        for (int i = N - 1; K > 0; i--) {
            X = X * 10 + arr[i];
            K--;
        }
 
        // Base Case
        if (X < M) {
            System.out.println("-1");
            return;
        }
 
        // Variable to store the answer
        int answer = -1;
 
        // Traverse and check for each number
        for (int i = M; i <= X; i = i + M) {
            int y = i;
            int v[] = new int[10];
 
            // Calculate the frequency of each number
            while (y > 0) {
                v[y % 10]++;
                y = y / 10;
            }
 
            boolean flag = true;
 
            // If frequency of any digit in y is less than
            // that in freq[], then it's not possible.
            for (int j = 0; j <= 9; j++) {
                if (v[j] > freq[j]) {
                    flag = false;
                    break;
                }
            }
 
            if (flag)
                answer = Math.max(answer, i);
        }
 
        // Print the answer
        System.out.println(answer);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 1, 2, 3, 4, 5, 6 };
        int N = 6, K = 3, M = 4;
 
        find(arr, N, K, M);
    }
}
 
// This code is contributed by Potta Lokesh

Python3

# Python program for the above approach
 
# Function to find the largest integer
# of K digits divisible by M
def find(arr, N, K, M):
 
    # Base Case, as there is no sub-sequence
    # of size greater than N is possible
    if (K > N):
        print("-1")
        return
 
    # Vector to store the frequency of each
    # number from the array
    freq = [0] * 10
 
    # Calculate the frequency of each from
    # the array
    for i in range(N):
        freq[arr[i]] += 1
 
    # Sort the array in ascending order
    arr.sort()
 
    # Variable to store the maximum number
    # possible
    X = 0
 
    # Traverse and store the largest K digits
    for i in range(N - 1, 2, -1):
        X = X * 10 + arr[i]
        K -= 1
 
    # Base Case
    if (X < M):
        print("-1")
        return
 
    # Variable to store the answer
    answer = -1
 
    # Traverse and check for each number
    for i in range(M, X + 1, M):
        y = i
        v = [0] * 10
 
        # Calculate the frequency of each number
        while (y > 0):
            v[y % 10] += 1
            y = y // 10
 
        flag = True
 
        # If frequency of any digit in y is less than
        # that in freq[], then it's not possible.
        for j in range(10):
            if (v[j] > freq[j]):
                flag = False
                break
 
        if (flag):
            answer = max(answer, i)
 
    # Print the answer
    print(answer)
 
 
# Driver Code
arr = [1, 2, 3, 4, 5, 6]
N = 6
K = 3
M = 4
 
find(arr, N, K, M)
 
# This code is contributed by gfgking.

C#

// C# code for the above approach
using System;
 
public class GFG
{
 
    // Function to find the largest integer
    // of K digits divisible by M
    static void find(int[] arr, int N, int K, int M)
    {
 
        // Base Case, as there is no sub-sequence
        // of size greater than N is possible
        if (K > N) {
            Console.WriteLine("-1\n");
            return;
        }
 
        // Vector to store the frequency of each
        // number from the array
        int []freq = new int[10];
 
        // Calculate the frequency of each from
        // the array
        for (int i = 0; i < N; i++) {
            freq[arr[i]]++;
        }
 
        // Sort the array in ascending order
        Array.Sort(arr);
 
        // Variable to store the maximum number
        // possible
        int X = 0;
 
        // Traverse and store the largest K digits
        for (int i = N - 1; K > 0; i--) {
            X = X * 10 + arr[i];
            K--;
        }
 
        // Base Case
        if (X < M) {
            Console.WriteLine("-1");
            return;
        }
 
        // Variable to store the answer
        int answer = -1;
 
        // Traverse and check for each number
        for (int i = M; i <= X; i = i + M) {
            int y = i;
            int []v = new int[10];
 
            // Calculate the frequency of each number
            while (y > 0) {
                v[y % 10]++;
                y = y / 10;
            }
 
            bool flag = true;
 
            // If frequency of any digit in y is less than
            // that in freq[], then it's not possible.
            for (int j = 0; j <= 9; j++) {
                if (v[j] > freq[j]) {
                    flag = false;
                    break;
                }
            }
 
            if (flag)
                answer = Math.Max(answer, i);
        }
 
        // Print the answer
        Console.WriteLine(answer);
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int[] arr = { 1, 2, 3, 4, 5, 6 };
        int N = 6, K = 3, M = 4;
 
        find(arr, N, K, M);
    }
}
 
// This code is contributed by AnkThon

Javascript

<script>
// Javascript program for the above approach
 
// Function to find the largest integer
// of K digits divisible by M
function find(arr, N, K, M) {
 
  // Base Case, as there is no sub-sequence
  // of size greater than N is possible
  if (K > N) {
    document.write("-1<br>");
    return;
  }
 
  // Vector to store the frequency of each
  // number from the array
  let freq = new Array(10).fill(0);
 
  // Calculate the frequency of each from
  // the array
  for (let i = 0; i < N; i++) {
    freq[arr[i]]++;
  }
 
  // Sort the array in ascending order
  arr.sort((a, b) => a - b);
 
  // Variable to store the maximum number
  // possible
  let X = 0;
 
  // Traverse and store the largest K digits
  for (let i = N - 1; K > 0; i--) {
    X = X * 10 + arr[i];
    K--;
  }
 
  // Base Case
  if (X < M) {
    cout << "-1\n";
    return;
  }
 
  // Variable to store the answer
  let answer = -1;
 
  // Traverse and check for each number
  for (let i = M; i <= X; i = i + M) {
    let y = i;
    let v = new Array(10).fill(0);
 
    // Calculate the frequency of each number
    while (y > 0) {
      v[y % 10]++;
      y = Math.floor(y / 10);
    }
 
    let flag = true;
 
    // If frequency of any digit in y is less than
    // that in freq[], then it's not possible.
    for (let j = 0; j <= 9; j++) {
      if (v[j] > freq[j]) {
        flag = false;
        break;
      }
    }
 
    if (flag)
      answer = Math.max(answer, i);
  }
 
  // Print the answer
  document.write(answer);
}
 
// Driver Code
let arr = [1, 2, 3, 4, 5, 6];
let N = 6, K = 3, M = 4;
 
find(arr, N, K, M);
 
// This code is contributed by gfgking.
</script>
Producción

652

Complejidad de tiempo : O(max(M, N))
Espacio auxiliar : O(1) 

Publicación traducida automáticamente

Artículo escrito por suryahome0000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *