Number of Atoms - Practice Coding Problems

Number of Atoms - Problem

Given a string formula representing a chemical formula, return the count of each atom.

The atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name. One or more digits representing that element's count may follow if the count is greater than 1. If the count is 1, no digits will follow.

For example, "H2O" and "H2O2" are possible, but "H1O2" is impossible.

Two formulas are concatenated together to produce another formula. For example, "H2O2He3Mg4" is also a formula.

A formula placed in parentheses, and a count (optionally added) is also a formula. For example, "(H2O2)" and "(H2O2)3" are formulas.

Return the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on.

Input & Output

Example 1 — Basic Formula

$ Input: formula = "H2O"

› Output: "H2O"

💡 Note: H appears 2 times, O appears 1 time. Sort alphabetically: H2O

Example 2 — Parentheses with Multiplier

$ Input: formula = "Mg(OH)2"

› Output: "H2MgO2"

💡 Note: Mg appears 1 time, (OH)2 means O appears 2 times and H appears 2 times. Sort alphabetically: H2MgO2

Example 3 — Nested Parentheses

$ Input: formula = "K4(ON(SO3)2)2"

› Output: "K4N2O14S4"

💡 Note: Complex nested structure: K appears 4 times, each (ON(SO3)2) repeated twice contains 1 O, 1 N, 2 S, and 6 O from SO3, totaling K4N2O14S4

Constraints

1 ≤ formula.length ≤ 1000
formula consists of English letters, digits, '(', and ')'
formula is always valid
All atom values in the output will fit in a 32-bit integer

Visualization

Tap to expand

Understanding the Visualization

Input Formula

Chemical formula with nested parentheses

Parse & Count

Handle nesting and multipliers

Sort & Format

Alphabetical order with counts

Key Takeaway

🎯 Key Insight: Stack data structure naturally handles nested parentheses and their multipliers

Asked in

G Google 25 a Amazon 18 f Facebook 12 M Microsoft 8

The key insight is using a stack to handle nested parentheses naturally. Each stack level maintains element counts, and when closing parentheses are encountered, counts are multiplied and merged with the parent level. Best approach is stack-based parsing in O(n) time with O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ String Expansion Approach	O(n³)	O(n³)	Expand all parentheses first, then count atoms
Stack-Based Parsing	O(n)	O(n)	Use stack to handle nested parentheses while parsing

String Expansion Approach — Algorithm Steps

Step 1: Find innermost parentheses and expand them
Step 2: Repeat until no parentheses remain
Step 3: Parse final string to count atoms
Step 4: Sort and format output

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Innermost

Locate innermost parentheses

Expand

Replace with repeated content

Count Atoms

Parse expanded string

Code -

solution.c — C

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

char* solution(char* formula) {
    // Simplified approach: directly parse without full expansion
    // This is a basic implementation
    static char result[1000];
    int counts[26] = {0}; // Only handling single letter elements for simplicity
    
    int i = 0;
    int len = strlen(formula);
    
    while (i < len) {
        if (isupper(formula[i])) {
            int elementIndex = formula[i] - 'A';
            i++;
            
            // Parse count
            int count = 0;
            while (i < len && isdigit(formula[i])) {
                count = count * 10 + (formula[i] - '0');
                i++;
            }
            if (count == 0) count = 1;
            
            counts[elementIndex] += count;
        } else {
            i++;
        }
    }
    
    // Format output
    result[0] = '\0';
    for (int j = 0; j < 26; j++) {
        if (counts[j] > 0) {
            char element = 'A' + j;
            char temp[10];
            if (counts[j] == 1) {
                sprintf(temp, "%c", element);
            } else {
                sprintf(temp, "%c%d", element, counts[j]);
            }
            strcat(result, temp);
        }
    }
    
    return result;
}

int main() {
    char formula[1000];
    fgets(formula, sizeof(formula), stdin);
    formula[strcspn(formula, "\n")] = 0;
    
    char* result = solution(formula);
    printf("%s\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Nested expansion can create exponentially long strings, each requiring O(n) processing

⚠ Quadratic Growth

Space Complexity

O(n³)

Expanded string can become exponentially large due to nested multiplications

⚠ Quadratic Space

89.5K Views

Medium Frequency

~25 min Avg. Time

1.8K 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

String Expansion Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler