Minimum Element After Replacement With Digit Sum solution and explanation
Google
9 more videos on this problem
3300. Minimum Element After Replacement With Digit Sum | Leetcode Daily - PythonLeetcode Daily · 5:41 · 305 views
3300. Minimum Element After Replacement With Digit Sum (Leetcode Easy)Programming Live with Larry · 4:22 · 223 views
Minimum Element After Replacement With Digit Sum | LeetCode 3300 - Pythonimpoldev · 4:44 · 112 views
LeetCode 3300: Minimum Element After Replacement With Digit Sum | Full Solution ExplainedDecode with Ramesh · 8:55 · 65 views
DAY 25 || LeetCode 3300 Minimum Element After Digit Sum Replacement || dsa || consistencyCode_With_Pooja · 8:16 · 48 views
3300. Minimum Element After Replacement With Digit Sum | Leetcode Daily ChallengeLogic soch · 2:07 · 40 views
Minimum Element After Replacement With Digit Sum | LeetCode 3300code with vedant · 4:58 · 29 views
Leetcode 3300 - Minimum Element After Replacement With Digit SumCode Harman · 2:46 · 29 views
LeetCode 3300 - Minimum Element After Replacement With Digit Sum 🔥Jal Patel · 3:56 · 24 views
LeetCode #3300 | Minimum Element After Replacement With Digit Sum | Math Approach in C++Code with Vishv Patel · 4:23 · 22 views
The problem
You are given an integer array nums.
You replace each element in nums with the sum of its digits.
Return the minimum element in nums after all replacements.
Example 1:
Input: nums = [10,12,13,14]
Output: 1
Explanation:
nums becomes [1, 3, 4, 5] after all replacements, with minimum element 1.
Example 2:
Input: nums = [1,2,3,4]
Output: 1
Explanation:
nums becomes [1, 2, 3, 4] after all replacements, with minimum element 1.
Example 3:
Input: nums = [999,19,199]
Output: 10
Explanation:
nums becomes [27, 10, 19] after all replacements, with minimum element 10.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 104
Approach overview
Problem Overview: You receive an integer array nums. Replace each number with the sum of its digits (for example, 123 → 1+2+3 = 6). After performing this transformation for every element, return the minimum value in the updated array.
The key observation is that the transformation is independent for each number. You only need a digit-sum operation and a way to track the smallest result.
Approach 1: Iterative Approach (O(n · d) time, O(1) space)
Traverse the array and compute the digit sum for each element. The digit sum can be calculated using repeated modulus and division: digit += num % 10 and num /= 10 until the number becomes zero. Replace the current element with this computed value or simply track it in a temporary variable.
After transforming each element, maintain a running minimum. This approach explicitly follows the problem statement: convert every value first, then determine the minimum. Time complexity is O(n · d), where n is the array length and d is the number of digits per number (at most ~10 for typical constraints). Space complexity remains O(1) since only a few variables are used.
This approach works well when you want clarity and step-by-step transformation of the array. It directly demonstrates the digit-sum calculation using simple arithmetic operations.
Approach 2: Optimize using Single Pass (O(n · d) time, O(1) space)
The optimization removes the need to conceptually store the transformed array. Instead, iterate through nums once, compute the digit sum for the current number, and immediately update the minimum value.
For each element: compute the digit sum using modulus and division, compare it with the current minimum, and update the minimum if needed. Because the result is consumed immediately, there is no extra array or replacement step.
This keeps the algorithm linear with O(n · d) time and constant O(1) space. The improvement is mostly conceptual and memory-efficient, but it is typically what interviewers expect because it avoids unnecessary work.
Both solutions rely on basic operations over an array and simple math digit manipulation. No additional data structures are required.
Recommended for interviews: The single-pass approach. It demonstrates that you understand the transformation and can combine computation with aggregation efficiently. Mentioning the straightforward iterative version first shows clarity, but implementing the optimized single-pass scan highlights practical problem-solving skills.
Approach 1: Iterative Approach
In this approach, we will iterate through each number in the array, calculate the sum of its digits, replace the original number with this sum, and finally find the minimum number in the modified array.
def digit_sum(num):
sum_ = 0
while num > 0:
sum_ += num % 10
num //= 10
return sum_
def find_minimum_after_replacement(nums):
nums = [digit_sum(num) for num in nums]
return min(nums)
nums = [10, 12, 13, 14]
print("Minimum element after replacement:", find_minimum_after_replacement(nums))import java.util.Arrays;
public class Main {
public static int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
public static int findMinimumAfterReplacement(int[] nums) {
for (int i = 0; i < nums.length; i++) {
nums[i] = digitSum(nums[i]);
}
return Arrays.stream(nums).min().getAsInt();
}
public static void main(String[] args) {
int[] nums = {10, 12, 13, 14};
System.out.println("Minimum element after replacement: " + findMinimumAfterReplacement(nums));
}
}#include <iostream>
#include <vector>
int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
int findMinimumAfterReplacement(std::vector<int>& nums) {
for (int& num : nums) {
num = digitSum(num);
}
int min = *min_element(nums.begin(), nums.end());
return min;
}
int main() {
std::vector<int> nums = {10, 12, 13, 14};
std::cout << "Minimum element after replacement: " << findMinimumAfterReplacement(nums) << std::endl;
return 0;
}function digitSum(num) {
let sum = 0;
while (num > 0) {
sum += num % 10;
num = Math.floor(num / 10);
}
return sum;
}
function findMinimumAfterReplacement(nums) {
for (let i = 0; i < nums.length; i++) {
nums[i] = digitSum(nums[i]);
}
return Math.min(...nums);
}
const nums = [10, 12, 13, 14];
console.log("Minimum element after replacement:", findMinimumAfterReplacement(nums));#include <stdio.h>
int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
int findMinimumAfterReplacement(int nums[], int size) {
for (int i = 0; i < size; i++) {
nums[i] = digitSum(nums[i]);
}
int min = nums[0];
for (int i = 1; i < size; i++) {
if (nums[i] < min) min = nums[i];
}
return min;
}
int main() {
int nums[] = {10, 12, 13, 14};
int size = sizeof(nums) / sizeof(nums[0]);
printf("Minimum element after replacement: %d\n", findMinimumAfterReplacement(nums, size));
return 0;
}using System;
using System.Linq;
class Program {
static int DigitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
static int FindMinimumAfterReplacement(int[] nums) {
for (int i = 0; i < nums.Length; i++) {
nums[i] = DigitSum(nums[i]);
}
return nums.Min();
}
static void Main() {
int[] nums = { 10, 12, 13, 14 };
Console.WriteLine("Minimum element after replacement: " + FindMinimumAfterReplacement(nums));
}
}This Python function uses a list comprehension to transform the array by replacing each element with its digit sum. The built-in min function is used to find and return the minimum value.
Time Complexity: O(n * m)
Space Complexity: O(n) due to the list comprehension.
Approach 2: Optimize using Single Pass
This approach calculates the digit sum for each number and maintains the minimum value seen so far during the iteration. This eliminates the need for a separate pass to find the minimum element after transformation.
def digit_sum(num):
sum_ = 0
while num > 0:
sum_ += num % 10
num //= 10
return sum_
def find_minimum_after_replacement(nums):
min_value = digit_sum(nums[0])
for num in nums[1:]:
current_digit_sum = digit_sum(num)
if current_digit_sum < min_value:
min_value = current_digit_sum
return min_value
nums = [10, 12, 13, 14]
print("Minimum element after replacement:", find_minimum_after_replacement(nums))public class Main {
public static int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
public static int findMinimumAfterReplacement(int[] nums) {
int min = digitSum(nums[0]);
for (int i = 1; i < nums.length; i++) {
int currentDigitSum = digitSum(nums[i]);
if (currentDigitSum < min) min = currentDigitSum;
}
return min;
}
public static void main(String[] args) {
int[] nums = {10, 12, 13, 14};
System.out.println("Minimum element after replacement: " + findMinimumAfterReplacement(nums));
}
}#include <iostream>
#include <vector>
int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
int findMinimumAfterReplacement(const std::vector<int>& nums) {
int min = digitSum(nums[0]);
for (size_t i = 1; i < nums.size(); ++i) {
int currentDigitSum = digitSum(nums[i]);
if (currentDigitSum < min) min = currentDigitSum;
}
return min;
}
int main() {
std::vector<int> nums = {10, 12, 13, 14};
std::cout << "Minimum element after replacement: " << findMinimumAfterReplacement(nums) << std::endl;
return 0;
}function digitSum(num) {
let sum = 0;
while (num > 0) {
sum += num % 10;
num = Math.floor(num / 10);
}
return sum;
}
function findMinimumAfterReplacement(nums) {
let min = digitSum(nums[0]);
for (let i = 1; i < nums.length; i++) {
const currentDigitSum = digitSum(nums[i]);
if (currentDigitSum < min) min = currentDigitSum;
}
return min;
}
const nums = [10, 12, 13, 14];
console.log("Minimum element after replacement:", findMinimumAfterReplacement(nums));#include <stdio.h>
int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
int findMinimumAfterReplacement(int nums[], int size) {
int min = digitSum(nums[0]);
for (int i = 1; i < size; i++) {
int currentDigitSum = digitSum(nums[i]);
if (currentDigitSum < min) min = currentDigitSum;
}
return min;
}
int main() {
int nums[] = {10, 12, 13, 14};
int size = sizeof(nums) / sizeof(nums[0]);
printf("Minimum element after replacement: %d\n", findMinimumAfterReplacement(nums, size));
return 0;
}using System;
class Program {
static int DigitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
static int FindMinimumAfterReplacement(int[] nums) {
int min = DigitSum(nums[0]);
for (int i = 1; i < nums.Length; i++) {
int currentDigitSum = DigitSum(nums[i]);
if (currentDigitSum < min) min = currentDigitSum;
}
return min;
}
static void Main() {
int[] nums = { 10, 12, 13, 14 };
Console.WriteLine("Minimum element after replacement: " + FindMinimumAfterReplacement(nums));
}
}In this Python solution, we directly calculate the digit sum of each element while keeping track of the smallest observed digit sum, avoiding any extra passes through the list.
Time Complexity: O(n * m)
Space Complexity: O(1).
Approach 3: Simulation
We can traverse the array nums. For each number x, we calculate the sum of its digits y. The minimum value among all y is the answer.
The time complexity is O(n times log M), where n and M are the length of the array nums and the maximum value in the array, respectively. The space complexity is O(1).
function minElement(nums: number[]): number {
let ans: number = 100;
for (let x of nums) {
let y = 0;
for (; x; x = Math.floor(x / 10)) {
y += x % 10;
}
ans = Math.min(ans, y);
}
return ans;
}func minElement(nums []int) int {
ans := 100
for _, x := range nums {
y := 0
for ; x > 0; x /= 10 {
y += x % 10
}
ans = min(ans, y)
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n * m) |
| Optimize using Single Pass | Time Complexity: O(n * m) |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Transformation | O(n · d) | O(1) | When implementing the problem exactly as described by replacing every element first |
| Single Pass Minimum Tracking | O(n · d) | O(1) | Preferred approach in interviews; compute digit sum and update minimum in one traversal |
Frequently asked questions
Is Minimum Element After Replacement With Digit Sum easy or hard?
Minimum Element After Replacement With Digit Sum is classified as an Easy problem. It focuses on basic array traversal and digit manipulation, making it suitable for beginners practicing math-based transformations and simple linear scans.
Minimum Element After Replacement With Digit Sum Python/Java solution
In Python or Java, iterate through the array, compute the digit sum using repeated modulus (% 10) and division (/ 10), and track the smallest value seen. The implementation is short—usually under 10 lines—and runs in O(n · d) time with constant space.
How to solve Minimum Element After Replacement With Digit Sum in O(n)?
Iterate through the array once and compute the digit sum for each number during traversal. Immediately compare the digit sum with the current minimum and update it if smaller. Because each element is processed once and no extra data structures are used, the solution runs in O(n · d) time and O(1) space.
What is the best approach for Minimum Element After Replacement With Digit Sum?
The best approach is a single-pass traversal of the array. For each number, compute its digit sum using modulus and division, then update the current minimum. This keeps the algorithm O(n · d) time where d is the number of digits, and O(1) extra space.
Is Minimum Element After Replacement With Digit Sum asked at Google/Amazon/Meta?
This exact problem is categorized as an easy array and math problem on LeetCode. Variants involving digit sums, digit manipulation, or array transformations appear in screening rounds across companies like Amazon and Google as warm-up or foundational questions.
What data structure is used in Minimum Element After Replacement With Digit Sum?
The problem primarily uses an array for iteration and simple integer arithmetic for computing digit sums. No additional data structures such as hash maps, stacks, or trees are required. The algorithm relies on basic math operations and a running minimum variable.
What is the time complexity of Minimum Element After Replacement With Digit Sum?
The time complexity is O(n · d). The algorithm processes n numbers, and each digit-sum computation takes up to d operations where d is the number of digits in the integer. Since d is small (≤10 for typical constraints), the runtime behaves close to linear O(n).