Dada una array arr[] de tamaño N , la tarea es minimizar la suma eliminando todas las ocurrencias de un solo dígito.
Ejemplos:
Entrada: arr[] = {34, 23, 85, 93}
Salida: 100
Explicación: Eliminar las ocurrencias del dígito 3 de cada elemento de la array modifica arr[] a {4, 2, 85, 9}. Por lo tanto, suma minimizada de la array = 4 + 2 + 85 + 9 = 100.Entrada: arr[] = {434, 863, 342, 121}
Salida: 293
Enfoque: la idea es eliminar todas las ocurrencias de cada dígito posible ( [0, 9] ) una por una y calcular la suma de la array después de eliminar cada uno de ellos. Finalmente, encuentre el mínimo de estas sumas. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos minSum , para almacenar la suma mínima y curSum para almacenar la suma obtenida después de eliminar todas las ocurrencias de un dígito.
- Itere sobre los dígitos en el rango [0, 9] y realice lo siguiente:
- Recorra la array arr[] y verifique la suma mínima eliminando cada dígito.
- Después de eliminar los dígitos de la string, vuelva a convertir la string en un número entero y agréguelo a curSum .
- Actualice el valor de minSum después de cada iteración.
- Imprime el valor de minSum como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for super ugly number
#include<bits/stdc++.h>
using namespace std;
// Function to remove each digit
// from the given integer
int remove(int N, int digit)
{
// Convert into string
string strN = to_string(N);
// Stores final string
string ans = "";
// Traverse the string
for (char i:strN)
{
if ((i - '0') == digit)
{
continue;
}
// Append it to the
// final string
ans += i;
}
// Return integer value
return stoi(ans);
}
// Function to find the minimum sum by
// removing occurences of each digit
void getMin(vector<int> arr)
{
int minSum = INT_MAX;
// Iterate in range [0, 9]
for (int i = 0; i < 10; i++)
{
int curSum = 0;
// Traverse the array
for (int num :arr)
curSum += remove(num, i);
// Update the minimum sum
minSum = min(minSum, curSum);
}
// Print the minimized sum
cout << minSum;
}
/* Driver program to test above functions */
int main()
{
vector<int> arr = {34, 23, 85, 93};
getMin(arr);
return 0;
}
// This code is contributed by mohit kumar 29.
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to remove each digit
// from the given integer
static int remove(int N, int digit)
{
// Convert into string
String strN = String.valueOf(N);
// Stores final string
String ans = "";
// Traverse the string
for (char i:strN.toCharArray())
{
if ((i - '0') == digit)
{
continue;
}
// Append it to the
// final string
ans += i;
}
// Return integer value
return Integer.parseInt(ans);
}
// Function to find the minimum sum by
// removing occurences of each digit
static void getMin(int[] arr)
{
int minSum = Integer.MAX_VALUE;
// Iterate in range [0, 9]
for (int i = 0; i < 10; i++)
{
int curSum = 0;
// Traverse the array
for (int num :arr)
curSum += remove(num, i);
// Update the minimum sum
minSum = Math.min(minSum, curSum);
}
// Print the minimized sum
System.out.print(minSum);
}
// Driver Code
public static void main(String[] args)
{
int[] arr = {34, 23, 85, 93};
getMin(arr);
}
}
// This code is contributed by code_hunt.
Python3
# Python3 program for the above approach
# Function to remove each digit
# from the given integer
def remove(N, digit):
# Convert into string
strN = str(N)
# Stores final string
ans = ''
# Traverse the string
for i in strN:
if int(i) == digit:
continue
# Append it to the
# final string
ans += i
# Return integer value
return int(ans)
# Function to find the minimum sum by
# removing occurences of each digit
def getMin(arr):
minSum = float('inf')
# Iterate in range [0, 9]
for i in range(10):
curSum = 0
# Traverse the array
for num in arr:
curSum += remove(num, i)
# Update the minimum sum
minSum = min(minSum, curSum)
# Print the minimized sum
print(minSum)
# Given array
arr = [34, 23, 85, 93]
getMin(arr)
C#
using System;
public class GFG
{
// Function to remove each digit
// from the given integer
static int remove(int N, int digit)
{
// Convert into string
String strN = N.ToString();
// Stores final string
String ans = "";
// Traverse the string
foreach(char i in strN.ToCharArray())
{
if ((i - '0') == digit)
{
continue;
}
// Append it to the
// final string
ans += i;
}
// Return integer value
return Int32.Parse(ans);
}
// Function to find the minimum sum by
// removing occurences of each digit
static void getMin(int[] arr)
{
int minSum = Int32.MaxValue;
// Iterate in range [0, 9]
for (int i = 0; i < 10; i++)
{
int curSum = 0;
// Traverse the array
foreach(int num in arr)
curSum += remove(num, i);
// Update the minimum sum
minSum = Math.Min(minSum, curSum);
}
// Print the minimized sum
Console.WriteLine(minSum);
}
// Driver Code
static public void Main (){
int[] arr = {34, 23, 85, 93};
getMin(arr);
}
}
// This code is contributed by Dharanendra L V.
Javascript
<script>
// Javascript program for super ugly number
// Function to remove each digit
// from the given integer
function remove(N, digit)
{
// Convert into string
var strN = N.toString();
// Stores final string
var ans = "";
var i;
// Traverse the string
for(i=0;i<strN.length;i++){
if ((strN.charCodeAt(i) - 48) == digit)
{
continue;
}
// Append it to the
// final string
ans += strN[i];
}
// Return integer value
return parseInt(ans);
}
// Function to find the minimum sum by
// removing occurences of each digit
function getMin(arr)
{
var minSum = 1000000000;
var i,j;
// Iterate in range [0, 9]
for (i = 0; i < 10; i++)
{
var curSum = 0;
// Traverse the array
for(j=0;j<arr.length;j++){
curSum += remove(arr[j], i);
}
// Update the minimum sum
minSum = Math.min(minSum, curSum);
}
// Print the minimized sum
document.write(minSum);
}
/* Driver program to test above functions */
var arr = [34, 23, 85, 93];
getMin(arr);
</script>
Producción:
100
Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces.
Espacio Auxiliar: O(N).
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA