Dada una array arr[] y un entero S , la tarea es elegir el recuento máximo de números de la array de modo que la suma de los números sea menor que S y formar el número más pequeño posible usando sus índices
Nota: se puede elegir cualquier elemento cualquier número de veces.
Ejemplos:
Entrada: arr[] = {3, 4, 2, 4, 6, 5, 4, 2, 3}, S = 13
Salida: 133333
Explicación:
Elementos elegidos: 3 + 2 + 2 + 2 + 2 + 2 = 13
Por lo tanto, Concatenación de índices – 133333Entrada: arr[] = {18, 21, 22, 51, 13, 14, 17, 15, 17}, S = 50
Salida: 115
Enfoque: La idea es encontrar el recuento máximo de los elementos que se pueden elegir que se pueden calcular para el número usando
Finalmente, los índices mínimos que pueden elegir varias veces se calculan tomando el dígito mínimo en el número para cada lugar de dígito.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find
// minimum number which
// have a maximum length
#include <bits/stdc++.h>
using namespace std;
// Function to find the
// minimum number which
// have maximum length
string max_number(int arr[], int sum)
{
int frac[9];
int maxi = INT_MIN;
string ans;
int pos;
// Find Maximum length
// of number
for (int i = 0; i < 9; i++) {
frac[i] = sum / arr[i];
if (frac[i] > maxi) {
pos = i;
maxi = frac[i];
}
}
ans.insert(0,
string(maxi,
(pos + 1) + '0'));
sum -= maxi * arr[pos];
// Find minimum number WHich
// have maximum length
for (int i = 0; i < maxi; i++) {
for (int j = 1; j <= 9; j++) {
if (sum
+ arr[pos]
- arr[j - 1]
>= 0) {
ans[i] = (j + '0');
sum += arr[pos]
- arr[j - 1];
break;
}
}
}
if (maxi == 0) {
return 0;
}
else {
return ans;
}
}
// Driver Code
int main()
{
int arr[9] = { 3, 4, 2, 4, 6,
5, 4, 2, 3 };
int s = 13;
cout << max_number(arr, s);
return 0;
}
Java
// Java implementation to find
// minimum number which
// have a maximum length
class GFG{
// Function to find the
// minimum number which
// have maximum length
static String max_number(int arr[], int sum)
{
int frac[] = new int[9];
int maxi = Integer.MIN_VALUE;
StringBuilder ans = new StringBuilder();
int pos = 0;
// Find Maximum length
// of number
for(int i = 0; i < 9; i++)
{
frac[i] = sum / arr[i];
if (frac[i] > maxi)
{
pos = i;
maxi = frac[i];
}
}
for(int i = 0; i < maxi; i++)
{
ans.append((char)((pos + 1) + '0'));
}
sum -= maxi * arr[pos];
// Find minimum number WHich
// have maximum length
for(int i = 0; i < maxi; i++)
{
for(int j = 1; j <= 9; j++)
{
if (sum + arr[pos] - arr[j - 1] >= 0)
{
ans.setCharAt(i, (char)(j + '0'));
sum += arr[pos] - arr[j - 1];
break;
}
}
}
if (maxi == 0)
{
return "0";
}
else
{
return ans.toString();
}
}
// Driver Code
public static void main(String str[])
{
int arr[] = { 3, 4, 2, 4, 6,
5, 4, 2, 3 };
int s = 13;
System.out.println(max_number(arr, s));
}
}
// This code is contributed by rutvik_56
Python3
# Python3 implementation to find # minimum number which # have a maximum length # Function to find the # minimum number which # have maximum length def max_number(arr, sum): frac = [0]*9 maxi = -10**9 pos = 0 # Find Maximum length # of number for i in range(9): frac[i] = sum // arr[i] if (frac[i] > maxi): pos = i maxi = frac[i] an = str((pos + 1)) * maxi #print(an) sum -= maxi * arr[pos] ans = [i for i in an] # Find minimum number WHich # have maximum length for i in range(maxi): for j in range(1, 10): if (sum + arr[pos] - arr[j - 1] >= 0): ans[i] = str(j) sum += arr[pos] - arr[j - 1] break if (maxi == 0): return 0 else: return "".join(ans) # Driver Code if __name__ == '__main__': arr = [ 3, 4, 2, 4, 6, 5, 4, 2, 3 ] s = 13 print(max_number(arr, s)) # This code is contributed by mohit kumar 29
C#
// C# implementation to find
// minimum number which
// have a maximum length
using System;
using System.Text;
class GFG{
// Function to find the
// minimum number which
// have maximum length
static String max_number(int []arr,
int sum)
{
int []frac = new int[9];
int maxi = int.MinValue;
StringBuilder ans =
new StringBuilder();
int pos = 0;
// Find Maximum length
// of number
for(int i = 0; i < 9; i++)
{
frac[i] = sum / arr[i];
if (frac[i] > maxi)
{
pos = i;
maxi = frac[i];
}
}
for(int i = 0; i < maxi; i++)
{
ans.Append((char)((pos + 1) + '0'));
}
sum -= maxi * arr[pos];
// Find minimum number WHich
// have maximum length
for(int i = 0; i < maxi; i++)
{
for(int j = 1; j <= 9; j++)
{
if (sum + arr[pos] -
arr[j - 1] >= 0)
{
ans[i] = (char)(j + '0');
sum += arr[pos] - arr[j - 1];
break;
}
}
}
if (maxi == 0)
{
return "0";
}
else
{
return ans.ToString();
}
}
// Driver Code
public static void Main(String []str)
{
int []arr = {3, 4, 2, 4, 6,
5, 4, 2, 3};
int s = 13;
Console.WriteLine(max_number(arr, s));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation to find
// minimum number which
// have a maximum length
// Function to find the
// minimum number which
// have maximum length
function max_number(arr,sum)
{
let frac = new Array(9);
let maxi = Number.MIN_VALUE;
let ans = [];
let pos = 0;
// Find Maximum length
// of number
for(let i = 0; i < 9; i++)
{
frac[i] = Math.floor(sum / arr[i]);
if (frac[i] > maxi)
{
pos = i;
maxi = frac[i];
}
}
for(let i = 0; i < maxi; i++)
{
ans.push(String.fromCharCode((pos + 1) + '0'.charCodeAt(0)));
}
sum -= maxi * arr[pos];
// Find minimum number WHich
// have maximum length
for(let i = 0; i < maxi; i++)
{
for(let j = 1; j <= 9; j++)
{
if (sum + arr[pos] - arr[j - 1] >= 0)
{
ans[i] = String.fromCharCode((j + '0'.charCodeAt(0)));
sum += arr[pos] - arr[j - 1];
break;
}
}
}
if (maxi == 0)
{
return "0";
}
else
{
return ans.join("");
}
}
// Driver Code
let arr = [3, 4, 2, 4, 6,
5, 4, 2, 3];
let s = 13;
document.write(max_number(arr, s));
// This code is contributed by unknown2108
</script>
Producción:
133333