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:
- Si K es mayor que N, imprima -1 y regrese.
- Inicialice el vector freq[] de tamaño 10 con valor 0 para almacenar la frecuencia de todos los elementos de la array arr[].
- Iterar sobre el rango [0, N) y almacenar la frecuencia de cada elemento en el arreglo freq[].
- Ordene la array arr[] en orden ascendente.
- Inicialice la variable X y establezca su valor como los K dígitos más grandes de la array arr[] como el número más grande posible.
- Si X es menor que M , imprima -1 y regrese.
- Inicialice la respuesta variable como -1 para almacenar la respuesta.
- Iterar sobre el rango [M, X] usando la variable i y realizar los siguientes pasos:
- Inicialice la variable y como i.
- Inicialice el vector v[] de tamaño 10 con valor 0 para almacenar la frecuencia de todos los dígitos del número y.
- Recorra los vectores freq[] y v[] y si para todas las posiciones freq[j] es mayor que igual a v[j], entonces actualice la respuesta como el máximo de respuesta o y.
- Después de realizar los pasos anteriores, imprima la respuesta variable como la respuesta.
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