Given an array arr[] of size N, the task is to minimize the sum by removing all the occurrences of a single digit.
Examples:
Input: arr[] = {34, 23, 85, 93}
Output: 100
Explanation: Removing the occurrences of the digit 3 from each element of the array modifies arr[] to {4, 2, 85, 9}. Therefore, minimized sum of the array = 4 + 2 + 85 + 9 = 100.Input: arr[] = {434, 863, 342, 121}
Output: 293
Approach: The idea is to remove all occurrences of each possible digit ( [0, 9] ) one by one and calculate the sum of the array after removal of each of them. Finally, find the minimum of these sums. Follow the steps below to solve the problem:
- Initialize a variable, say minSum, to store the minimum sum and curSum to store the sum obtained after removing all occurrences of a digit.
- Iterate over the digits in the range [0, 9] and perform the following:
- Traverse the array arr[] and check for the minimum sum by removing every digit.
- After removing the digits from the string, convert the string back to an integer and add it to curSum.
- Update the value of minSum after each iteration.
- Print the value of minSum as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for super ugly number#include<bits/stdc++.h>using namespace std;// Function to remove each digit// from the given integerint 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 digitvoid 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 approachimport java.util.*;class GFG{// Function to remove each digit// from the given integerstatic 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 digitstatic 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 Codepublic 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 integerdef 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 digitdef 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 arrayarr = [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 integerfunction 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 digitfunction 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> |
Output:
100
Time Complexity: O(N), as we are using a loop to traverse N times.
Auxiliary Space: O(1).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
