Solution For Number Of Atoms

Problem Statement:

Given a chemical formula (given as a string), return the count of each atom.

An atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name.

1 or more digits representing the count of that element 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 concatenated together to produce another formula.

Example 1:

Input: formula = “H2O”
Output: {“H”: 2, “O”: 1}
Explanation: The count of elements are {“H”: 2, “O”: 1}.

Example 2:

Input: formula = “Mg(OH)2”
Output: {“Mg”: 1, “O”: 2, “H”: 2}
Explanation: The count of elements are {“Mg”: 1, “O”: 2, “H”: 2}.

Example 3:

Input: formula = “K4(ON(SO3)2)2”
Output: {“K”: 4, “O”: 14, “N”: 2, “S”: 4}
Explanation: The count of elements are {“K”: 4, “O”: 14, “N”: 2, “S”: 4}.

Solution:

The solution to this problem can be solved using a stack and a dictionary. We will traverse the string from left to right and push the characters into the stack. Whenever we encounter an opening bracket ‘(‘, we will push a new dictionary into the stack to collect the counts of the elements in the brackets. Whenever we encounter a closing bracket ‘)’, we will pop the last dictionary from the stack and multiply the element counts by the number outside the brackets.

For example, if we encounter the string ‘Br2(OH4)3’, we will initialize an empty dictionary and push it into the stack. When we encounter the letter ‘B’, we add it to the dictionary. When we encounter the number ‘2’, we update the count of ‘B’ to 2. When we encounter the opening bracket ‘(‘, we push a new empty dictionary into the stack. When we encounter the letter ‘O’, we add it to the second dictionary. When we encounter the letter ‘H’, we add it to the second dictionary. When we encounter the number ‘4’, we update the counts of ‘O’ and ‘H’ to 4. When we encounter the closing bracket ‘)’, we pop the second dictionary from the stack and multiply the counts by the number ‘3’ outside the brackets. We then add the updated counts to the first dictionary.

In the end, we will have the count of each element in the first dictionary.

Python code:

def countOfAtoms(formula: str) -> dict[str, int]:
stack = [collections.defaultdict(int)] i = 0
while i < len(formula):
c = formula[i] i += 1
if c == ‘(‘:
stack.append(collections.defaultdict(int))
elif c == ‘)’:
count = 0
while i < len(formula) and formula[i].isdigit():
count = count * 10 + int(formula[i])
i += 1
if count == 0:
count = 1
last = stack.pop()
for elem, cnt in last.items():
stack[-1][elem] += cnt * count
else:
elem = c
while i < len(formula) and formula[i].islower():
elem += formula[i] i += 1
count = 0
while i < len(formula) and formula[i].isdigit():
count = count * 10 + int(formula[i])
i += 1
if count == 0:
count = 1
stack[-1][elem] += count
return stack[-1]

In this code, we start by initializing a stack with an empty dictionary. We then traverse the string from left to right and use a pointer ‘i’ to keep track of our position. Whenever we encounter an opening bracket, we push a new empty dictionary into the stack. Whenever we encounter a closing bracket, we pop the last dictionary from the stack and multiply the counts by the number outside the brackets. Whenever we encounter a letter, we collect it and any following lowercase letters to form an element name. Whenever we encounter a number, we collect it and multiply the count of the current element. We then add the count to the last dictionary in the stack.

Finally, we return the count of each element in the last dictionary in the stack.

Step by Step Implementation For Number Of Atoms

import java.util.*;

public class Solution {
    public String countOfAtoms(String formula) {
        // parse the formula string into a map of elements and their counts
        Map elementCounts = parseFormula(formula);
        
        // build a string representation of the map, sorted alphabetically
        StringBuilder sb = new StringBuilder();
        List elements = new ArrayList<>(elementCounts.keySet());
        Collections.sort(elements);
        for (String element : elements) {
            sb.append(element);
            if (elementCounts.get(element) > 1) {
                sb.append(elementCounts.get(element));
            }
        }
        
        return sb.toString();
    }
    
    private Map parseFormula(String formula) {
        Map elementCounts = new HashMap<>();
        int i = 0;
        while (i < formula.length()) {
            int start = i;
            char c = formula.charAt(i);
            if (c == '(') {
                // find the matching closing parenthesis
                int openCount = 1;
                i++;
                while (openCount > 0) {
                    c = formula.charAt(i);
                    if (c == '(') {
                        openCount++;
                    } else if (c == ')') {
                        openCount--;
                    }
                    i++;
                }
                // process the contents of the parentheses
                Map subElementCounts = parseFormula(formula.substring(start + 1, i - 1));
                // get the multiplier for the contents of the parentheses
                int multiplier = 1;
                if (i < formula.length() && Character.isDigit(formula.charAt(i))) {
                    int end = i;
                    while (i < formula.length() && Character.isDigit(formula.charAt(i))) {
                        i++;
                    }
                    multiplier = Integer.parseInt(formula.substring(end, i));
                }
                // update the counts in the map
                for (String element : subElementCounts.keySet()) {
                    elementCounts.put(element, elementCounts.getOrDefault(element, 0) + subElementCounts.get(element) * multiplier);
                }
            } else {
                // process an element
                i++;
                while (i < formula.length() && Character.isLowerCase(formula.charAt(i))) {
                    i++;
                }
                String element = formula.substring(start, i);
                // get the count for the element
                int count = 1;
                if (i < formula.length() && Character.isDigit(formula.charAt(i))) {
                    int end = i;
                    while (i < formula.length() && Character.isDigit(formula.charAt(i))) {
                        i++;
                    }
                    count = Integer.parseInt(formula.substring(end, i));
                }
                // update the count in the map
                elementCounts.put(element, elementCounts.getOrDefault(element, 0) + count);
            }
        }
        return elementCounts;
    }
}

def countOfAtoms(formula):

# initialize an empty dictionary to store the count of each atom

atom_count = {}

# keep track of the current index in the formula string

i = 0

# loop through the entire string

while i < len(formula):

# get the current character

c = formula[i]

# if the current character is an uppercase letter,

# it indicates the start of an atom

if c.isupper():

# initialize an empty string to store the atom

atom = ''

# loop until we reach the end of the atom

while i < len(formula) and formula[i].islower():

# add the current character to the atom string

atom += formula[i]

# move to the next character

i += 1

# if the next character is a digit, it indicates the count of the atom

if i < len(formula) and formula[i].isdigit():

# initialize an empty string to store the count

count = ''

# loop until we reach the end of the count

while i < len(formula) and formula[i].isdigit():

# add the current character to the count string

count += formula[i]

# move to the next character

i += 1

# convert the count string to an integer

count = int(count)

# if the atom is already in the dictionary, update the count

if atom in atom_count:

atom_count[atom] += count

# otherwise, add the atom to the dictionary with the count

else:

atom_count[atom] = count

# move to the next character

i += 1

# return the dictionary of atom counts

return atom_count

var countOfAtoms = function(formula) {
    
};

std::map parse(std::string formula) {
    int n = formula.size();
    std::map count;
    for (int i = 0, i_end = 0; i < n; i = i_end) {
        int val = 1;
        i_end = i+1;
        if (formula[i] == '(') {
            int cnt = 0;
            for (; i_end < n; ++i_end) {
                if (formula[i_end] == '(') ++cnt;
                if (formula[i_end] == ')') --cnt;
                if (cnt == 0) break;
            }
            std::map tmp = parse(formula.substr(i+1, i_end-i-2));
            i = i_end+1;
            if (i < n && isdigit(formula[i])) {
                int j = i;
                while (i < n && isdigit(formula[i])) ++i;
                val = stoi(formula.substr(j, i-j));
            }
            for (auto& [k, v] : tmp) {
                count[k] += v*val;
            }
        } else {
            while (i_end < n && islower(formula[i_end])) ++i_end;
            std::string key = formula.substr(i, i_end-i);
            i = i_end;
            if (i < n && isdigit(formula[i])) {
                int j = i;
                while (i < n && isdigit(formula[i])) ++i;
                val = stoi(formula.substr(j, i-j));
            }
            count[key] += val;
        }
    }
    return count;
}

std::string countOfAtoms(std::string formula) {
    std::map count = parse(formula);
    std::string res;
    for (auto& [k, v] : count) {
        res += k;
        if (v > 1) res += std::to_string(v);
    }
    return res;
}

public class Solution {
    public string CountOfAtoms(string formula) {
        // Your code here
    }
}