LeetCode 972. Equal Rational Numbers [Analysis]

Hello to whoever is reading this post! I realised that a good friend of mine (that is you Ji Hyung) is working on LeetCode problems, and I decided to attempt some LeetCode problems too when I have time. Afterall, I like solving puzzles, thinking about algorithms and just taxing my brain to solve hard problems. This doesn’t mean though, that I’ll be only solving LeetCode problems. I’ll just post whatever fun Math, Computer Science or Brainteaser that I come across in my life (or anything interesting that I learn in my life). I might occasionally post some random stuff about my life too.

The problem I am going to discuss today is Equal Rational Numbers. Although this problem is categorized as “hard”, it seems very doable and the only difficult part of this problem is casework i.e. one needs to cover a shit ton of edge cases to get his/her solution accepted.

To summarise the problem, we are given two rational numbers (represtend by the string data type) and we have to determine whether these two rational numbers are equivalent or not. The rational number is given in the following format: <IntegerPart><.><NonRepeatingPart><RepeatingPart>. For instance, if we have 1.155(6) as an input, this means that the integer part is 1, the non-repeating part is 155 and the repeating part is 6. As such, if we are given two rational numbers S = 0.(52) and T = 0.5(25), we know that those two are equal, because the non-repeating part for T can be merged with the repeating part for T and we end up with the repeating part (52) as well for T.

The observation regarding S = 0.(52) and T = 0.5(25) actually leads us to the solution. First if the integer part for the two numbers S and T are different, then the two numbers are not equal. Now, we can merge the non-repeating part and the repeating part. For S, we would have the merged string “52”, and for T, we would have the merged string “525”. We chop the longer string from the back until it has a length equal to that of the shorter string. So we would get rid of the 5 for 525. We then compare each of the characters for the two merged strings. We see that “52” is equal to “52” so we can say that S and T are equal.

Now we are only left with the implementation, and we can pretty much break down the implementation step as follows: (1) parse the string and extract the integer part, non-repeating part and repeating part for both S and T

(2) Check if their integer parts are equal, if not S and T are not equal

(3) If repeating part for S is only consisted of 0, ignore the repeating part. If the repeating part for S is only consisted of 9, treat the repeating part as an empty string, and increment the non-repeating part by 1. If the non-repeating part does not exist for S, increment the integer part instead. Repeat this for T.

(4) Take care of some edge cases (as shown in my code below). Finally, merge the non-repeating and repeating parts of S, do the same for T then compare.

Overall an unpleasant problem. Not so sure if my code is robust enough but it passes all the leetcode test cases (maybe their test case is weak??) Anyways was my first post and I’ll hopefully come back with a better post next time.

Time Complexity: O(|S| + |T|), S and T are two input strings

This is my C++ Solution Code

class Solution {
public:
    void extract(string s,string &intpart,string &nonrepeating,string &repeating){
          int idx1 = s.find('.');
          int idx2 = s.find('(');
          int idx3 = s.find(')');
          if (idx1 != string::npos){
            intpart = s.substr(0,idx1);
            nonrepeating = s.substr(idx1+1,idx2-idx1-1);
            if (idx3 != string::npos){
              repeating = s.substr(idx2+1,idx3-idx2-1);
            }
          }else{
            intpart = s;
          }
    }
    bool only0s(string s){
        if (s.empty()) return false;
         for (int i = 0; i < s.size(); i++){
            if (s[i] != '0') return false;
         }
        return true;
    }

    bool only9s(string s){
      if (s.empty()) return false;
      for (int i = 0; i < s.size(); i++){
        if (s[i] != '9') return false;
      }
      return true;
    }
    string increment(string s){
      string res = s;
      int idx = res.size()-1;
      while (idx >= 0 && res[idx] == '9'){
        res[idx] = '0';
        idx--;
      }
      if (idx == -1){
        return "1"+res;
      }
      int added = (res[idx]-'0')+1;
      res[idx] = char(added + '0');
      return res;
    }
    bool isRationalEqual(string S,string T){
      string s_integer,s_non_repeating,s_repeating;
      string t_integer,t_non_repeating,t_repeating;
      extract(S,s_integer,s_non_repeating,s_repeating);
      extract(T,t_integer,t_non_repeating,t_repeating);
      if (only9s(s_repeating)){
        if (!s_non_repeating.empty()){
          if (only9s(s_non_repeating)){
            s_non_repeating = "";
            s_integer = increment(s_integer);
          }else{
            s_non_repeating = increment(s_non_repeating);
          }
        }else if (!s_integer.empty()){
          s_integer = increment(s_integer);
        }
        s_repeating = "";
      }
      if (only9s(t_repeating)){
        if (!t_non_repeating.empty()){
          if (only9s(t_non_repeating)){
            t_non_repeating = "";
            t_integer = increment(t_integer);
          }else{
            t_non_repeating = increment(t_non_repeating);
          }
        }else if (!t_integer.empty()){
          t_integer = increment(t_integer);
        }
        t_repeating = "";
      }
      if (only0s(s_repeating)) s_repeating = "";
      if (only0s(t_repeating)) t_repeating = "";
      if (s_integer != t_integer) return false;
      if (s_repeating.empty() && t_repeating.empty()){
        if (only0s(s_non_repeating)) s_non_repeating = "";
        if (only0s(t_non_repeating)) t_non_repeating = "";
        return s_non_repeating == t_non_repeating;
      }
      if (s_non_repeating.empty() && !s_repeating.empty() && !t_non_repeating.empty() && t_repeating.empty()){
        return false;
      }
      if (!s_non_repeating.empty() && s_repeating.empty() && t_non_repeating.empty() && !t_repeating.empty()){
        return false;
      }
      string s_merge = s_non_repeating+s_repeating;
      string t_merge = t_non_repeating+t_repeating;
      if (!s_merge.empty() && t_merge.empty()) return false;
      if (s_merge.empty() && !t_merge.empty()) return false;
      for (int i = 0; i < min(s_merge.size(),t_merge.size()); i++){
        if (s_merge[i] != t_merge[i]) return false;
      }
      return true;
    }
};