Dada una array arr[] de N enteros y un entero positivo K , la tarea es elegir K enteros de la array arr[] de modo que la concatenación de ellos forme el entero más grande posible. Todos los elementos de la array deben elegirse al menos una vez para crear el número.
Nota: Siempre se garantiza que N es mayor o igual que K .
Ejemplos:
Entrada: arr[] = {3, 2, 7}, K = 3
Salida: 732
Explicación:
dado que cada elemento de la array debe usarse al menos una vez, el número más grande posible es 732.Entrada: arr[] = {1, 10, 100}, K = 4
Salida: 110100100
Enfoque: el problema anterior se puede resolver clasificando y convirtiendo números en strings . El enfoque óptimo es tomar todos los números una vez. Después de eso, toma el número con más dígitos. En caso de empate, se toma el número lexicográficamente mayor. Convierte todos los números de la string usando la función to_string() . Siga los pasos a continuación para resolver el problema:
- Inicialice una string vacía res para almacenar la respuesta.
- Ordene los números de la array [] en orden ascendente.
- Inicialice un vector de strings v[] .
- Iterar sobre el rango [0, K) usando la variable i y empujar el número de string numbers[i] en el vector v[] .
- Disminuya el valor de N en K y empuje el valor números[K-1] N veces en el vector v[] .
- Ordene el vector v[] usando la función de comparación.
- Itere sobre el rango [v.size()-1, 0] usando la variable i y agregue el valor v[i] a la variable res .
- Después de realizar los pasos anteriores, imprima el valor de res como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Custom comparator function
bool str_cmp(string s1, string s2)
{
return (s1 + s2 < s2 + s1);
}
// Function to get the largest possible
// string
string largestNumber(vector<int> arr,
int K)
{
int N = arr.size();
// Initialize a new variable which
// will store the answers.
string res = "";
// Sort the numbers array in
// non-decreasing order
sort(arr.begin(), arr.end());
// Stores the array element which will
// be used to construct the answer
vector<string> v;
// Take all numbers atleast once
for (int i = 0; i < N; i++) {
v.push_back(to_string(arr[i]));
}
K -= N;
// Take the largest digits number
// for remaining required numbers
while (K) {
v.push_back(to_string(arr[N - 1]));
K--;
}
// Sort the final answer according to
// the comparator function.
sort(v.begin(), v.end(), str_cmp);
for (int i = v.size() - 1; i >= 0; i--)
res += v[i];
return res;
}
// Driver Code
int main()
{
vector<int> arr = { 1, 10, 100 };
int K = 4;
cout << largestNumber(arr, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG
{
// Custom comparator function
static int str_cmp(String s1, String s2)
{
return (s1 + s2).compareTo(s2 + s1);
}
// Function to get the largest possible
// String
static String largestNumber(int arr[], int K)
{
int N = arr.length;
// Initialize a new variable which
// will store the answers.
String res = "";
// Sort the numbers array in
// non-decreasing order
Arrays.sort(arr);
// Stores the array element which will
// be used to construct the answer
ArrayList<String> v = new ArrayList<String>();
// Take all numbers atleast once
for (int i = 0; i < N; i++) {
v.add(String.join("",Integer.toString(arr[i])));
}
K -= N;
// Take the largest digits number
// for remaining required numbers
while (K > 0) {
v.add(String.join("",Integer.toString(arr[N - 1])));
K--;
}
// Sort the readonly answer according to
// the comparator function.
v.sort((s1,s2) -> str_cmp(s1,s2));
for (int i = v.size() - 1; i >= 0; i--)
res += v.get(i);
return res;
}
// Driver Code
public static void main(String[] args) {
int arr[] = { 1, 10, 100 };
int K = 4;
System.out.print(largestNumber(arr, K));
}
}
// This code is contributed by Pushpesh Raj.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Custom comparator function
// Function to get the largest possible
// String
static String largestNumber(int[] arr, int K)
{
int N = arr.Length;
// Initialize a new variable which
// will store the answers.
String res = "";
// Sort the numbers array in
// non-decreasing order
Array.Sort(arr);
// Stores the array element which will
// be used to construct the answer
List<String> v = new List<String>();
// Take all numbers atleast once
for (int i = 0; i < N; i++) {
v.Add(String.Join("",arr[i]));
}
K -= N;
// Take the largest digits number
// for remaining required numbers
while (K > 0) {
v.Add(String.Join("",arr[N - 1]));
K--;
}
// Sort the readonly answer according to
// the comparator function.
v.Sort((s1,s2) => (s1 + s2).CompareTo(s2 + s1));
for (int i = v.Count - 1; i >= 0; i--)
res += v[i];
return res;
}
// Driver Code
public static void Main(String[] args) {
int[] arr = { 1, 10, 100 };
int K = 4;
Console.Write(largestNumber(arr, K));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to get the largest possible
// string
function largestNumber(arr,
K) {
let N = arr.length;
// Initialize a new variable which
// will store the answers.
let res = "";
// Sort the numbers array in
// non-decreasing order
arr.sort(function (a, b) { return a - b })
// Stores the array element which will
// be used to construct the answer
let v = [];
// Take all numbers atleast once
for (let i = 0; i < N; i++) {
v.push(arr[i].toString());
}
K -= N;
// Take the largest digits number
// for remaining required numbers
while (K) {
v.push(arr[N - 1].toString());
K--;
}
// Sort the final answer according to
// the comparator function.
v.sort(function (s1, s2) { return parseInt(s1 + s2) - parseInt(s2 + s1) });
for (let i = v.length - 1; i >= 0; i--)
res += v[i];
return res;
}
// Driver Code
let arr = [1, 10, 100];
let K = 4;
document.write(largestNumber(arr, K));
// This code is contributed by Potta Lokesh
</script>
Producción:
110100100
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA