algoadvance

Leetcode 3174. Clear Digits

Problem Statement

Given an integer n, you need to remove all digits that appear an odd number of times in the integer. For example, given the integer 122334, the digit 1 appears once (odd), the digit 2 appears twice (even), the digit 3 appears twice (even), and the digit 4 appears once (odd). After removing the digits that appear an odd number of times, the result would be 2233.

Clarifying Questions

  1. Input Constraints
    • What is the range of the integer n (is it positive, negative, any size constraints)?
  2. Output Format
    • Should the output be in the same order as the input digits?
    • What should be the output if all digits appear an odd number of times or if the input is an empty string?
  3. Edge Cases
    • How to handle leading zeros after removing the odd-occurrence digits?
    • How should the function behave if the input integer is zero?

Code

We will write a function clearOddDigits which handles the given problem. It will first count the occurrences of each digit in the input, and then construct the resulting number by excluding digits that appear an odd number of times.

import java.util.HashMap;
import java.util.Map;

public class ClearDigitsOut {

    public static String clearOddDigits(int n) {
        // Convert the integer to a string to work with individual digits
        String numStr = Integer.toString(n);
        
        // Map to count frequency of each digit
        Map<Character, Integer> frequencyMap = new HashMap<>();
        for (char digit : numStr.toCharArray()) {
            frequencyMap.put(digit, frequencyMap.getOrDefault(digit, 0) + 1);
        }
        
        // StringBuilder to construct the result
        StringBuilder result = new StringBuilder();
        for (char digit : numStr.toCharArray()) {
            if (frequencyMap.get(digit) % 2 == 0) { // Even count
                result.append(digit);
            }
        }
        
        return result.toString();
    }

    public static void main(String[] args) {
        int n = 122334;
        System.out.println(clearOddDigits(n)); // Output should be "2233"
    }
}

Strategy

  1. Counting Digit Occurrences: We first convert the integer to a string to easily iterate over each digit.
  2. Frequency Map: Use a HashMap to count the occurrences of each digit.
  3. Construct Result: Iterate again over the digits of the input string, appending only those digits whose count in the frequency map is even.
  4. Edge Cases:
    • Input integer is zero: should return an empty string if zero appears an odd number of times, otherwise return “0”.
    • Negative input handling (optional): If inputs are negative integers, we should handle the negative sign appropriately.

Time Complexity

This solution provides an efficient method to solve the problem as the operations are linear in terms of the number of digits.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI