Minimum Element After Replacement With Digit Sum

Minimum Element After Replacement With Digit Sum - Problem

Array Math Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [10,12,13,14]

› Output: 1

💡 Note: Replace elements: 10→1, 12→3, 13→4, 14→5. Array becomes [1,3,4,5]. Minimum is 1.

Example 2 — Larger Numbers

$ Input: nums = [1,2,3,4]

› Output: 1

💡 Note: Single digit numbers remain unchanged: [1,2,3,4]. Minimum is 1.

Example 3 — Multi-digit Numbers

$ Input: nums = [999,191,22]

› Output: 4

💡 Note: Replace elements: 999→27 (9+9+9), 191→11 (1+9+1), 22→4 (2+2). Array becomes [27,11,4]. Minimum is 4.

Constraints

1 ≤ nums.length ≤ 100
1 ≤ nums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Array

Original integer array

Replace with Digit Sums

Each number becomes sum of its digits

Find Minimum

Return smallest digit sum

Key Takeaway

🎯 Key Insight: Transform each number to its digit sum and find the minimum in one efficient pass

Asked in

M Meta 12 G Google 8

The key insight is to calculate digit sums while tracking the minimum in a single pass. We iterate through each number, compute its digit sum by repeatedly taking modulo 10, and maintain the running minimum. Best approach is the optimized single-pass solution. Time: O(n × d), Space: O(1) where d is average digits per number.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Single Pass	O(n × d)	O(1)	Calculate digit sums and track minimum in one pass
Brute Force - Two Pass	O(n × d)	O(1)	Replace all elements with digit sums, then find minimum

Optimized - Single Pass — Algorithm Steps

Step 1: Initialize minimum with digit sum of first element
Step 2: For each remaining element, calculate digit sum
Step 3: Update minimum if current digit sum is smaller

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with first element's digit sum as minimum

Process Each Element

Calculate digit sum and compare with current minimum

Update Minimum

Keep track of smallest digit sum seen so far

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int digitSum(int num) {
    num = abs(num);
    int total = 0;
    while (num > 0) {
        total += num % 10;
        num /= 10;
    }
    return total;
}

int solution(int* nums, int numsSize) {
    // Find minimum digit sum in single pass
    int minDigitSum = digitSum(nums[0]);
    for (int i = 1; i < numsSize; i++) {
        int currentDigitSum = digitSum(nums[i]);
        if (currentDigitSum < minDigitSum) {
            minDigitSum = currentDigitSum;
        }
    }
    return minDigitSum;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int count = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[count++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, count);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × d)

Single pass through n elements, each requiring d digit calculations

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track minimum and calculate digit sums

✓ Linear Space

12.0K Views

Medium Frequency

~10 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Single Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler