LeetCode – Mike Scherbakov

Integer to English Words – task solution (LeetCode)

Leave a Comment / Interview preparation, LeetCode / Mike

The task “Integer to English Words” can be solved as follows:

introduce arrays for big numbers (100, 1000, 1 000 000 and so on) and for numbers less than 20
introduce arrays for names of big numbers and for names of numbers less than 20
use a recursive approach:
– if the current value ot the num is greater than the smallest number from the big numbers array:
— find the highest divider of the current num value from an array of big numbers
— append a result string with the recursive result of the current function with num as a reminder from division a num by the highest divider
— append a result string with the current English name of divider
— subtract the divider from the num
– otherwise find the highest divider of the current value of the num from array of small numbers
— append a result string with the current English name of divider
— subtract the divider from the num
— append a result string with the recursive result of the current function with num as a reminder from division a num by the highest divider
– recursively call the current function with a num as the reminder from division the num by the highest divider
time complexity: O(n), where n – count of digits in the num
space complexity: O(1)


public class IntegerToEnglishWords {

  private final String[] symbols = new String[]{"One", "Two", "Three", "Four", "Five", "Six", "Seven",
      "Eight",
      "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen",
      "Seventeen", "Eighteen", "Nineteen", "Twenty", "Thirty", "Forty", "Fifty", "Sixty",
      "Seventy",
      "Eighty", "Ninety"};
  private final short[] numbers = new short[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
      18, 19,
      20, 30, 40, 50, 60, 70, 80, 90};
  private final String[] bigSymbols = new String[]{"Hundred", "Thousand", "Million", "Billion"};
  private final int[] bigNumbers = new int[]{100, 1000, 1000000, 1000000000};

  public String numberToWords(int num) {
    if (num == 0) {
      return "Zero";
    }
    return numberToWordsRecursive(num);
  }

  private String numberToWordsRecursive(int num) {
    if (num == 0) {
      return "";
    }
    var resultLeft = new StringBuilder();
    if (num >= bigNumbers[0]) {
      var j = bigNumbers.length - 1;
      while (num / bigNumbers[j] == 0) {
        j--;
      }
      resultLeft.append(numberToWordsRecursive(num / bigNumbers[j]));
      resultLeft.append(" ");
      resultLeft.append(bigSymbols[j]);
      resultLeft.append(" ");

      num -= bigNumbers[j] * (num / bigNumbers[j]);
    } else {
      var j = numbers.length - 1;
      while (num / numbers[j] == 0) {
        j--;
      }
      resultLeft.append(symbols[j]);
      num -= numbers[j] * (num / numbers[j]);
      resultLeft.append(numberToWordsRecursive(num / numbers[j]));
      resultLeft.append(" ");
    }
    resultLeft.append(numberToWordsRecursive(num));
    return resultLeft.toString().trim();
  }

  public static void main(String[] args) {
    System.out.println(new IntegerToEnglishWords().numberToWords(1));
  }
}

Integer to English Words – task solution (LeetCode) Read More »

Integer to Roman – task solution (LeetCode)

Leave a Comment / Interview preparation, LeetCode / Mike

I’m going to describe how to solve the task Integer to Roman from LeetCode using greedy algorithm.

introduce 2 arrays: Roman characters (reflections) and their values
in a loop, until the remaining convertible number exceeds 0:
– find the largest predecessor of the remaining convertible number
– append the result string with the found reflection of the predecessor
– subtract the value from the remainder of the convertible number

Time complexity: O(1)

Space complexity: O(1)

public class IntegerToRoman {

  public static String intToRoman(int num) {
    var symbols = new String[]{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    var values = new short[]{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    var result = new StringBuilder();
    byte j = 0;
    while (num > 0) {
      while (values[j] > num) {
        j++;
      }
      result.append(symbols[j]);
      num -= values[j];
    }
    return result.toString();
  }

  public static void main(String[] args) {
    System.out.println(intToRoman(2888));
  }
}

Integer to Roman – task solution (LeetCode) Read More »