Alternative for Look And Say prob (chapter 7.6) with better complexity and more elegant

#1

Hello, for the Look And Say problem chapter 7.6, I feel that the following reccursive solution is better because it’s time complexity is better O(n) (?) where n is the number of digit and it is also more elegant (?)

public class LookAndSay {
    public int nth(int number) {
        if (number < 0)
            return 0;
    
        int digit = number % 10;
        boolean exit = number < 10;
        number /= 10;

        if (exit) {
            return 10 + digit;
        }
        
        int val = nth(number);
        if (val % 10 == digit) {
            return 10 + val;
        }
        else {
            return val * 100 + 10 + digit;
        }
    }

    public static void main(String[] args) {
        System.out.println("Hello");
        LookAndSay lookAndSay = new LookAndSay();
        System.out.println("" + lookAndSay.nth(11223344));
    }
}

Let me know what you think…

Thanks
Shan

0 Likes
#2

Hey Shan,

First of all, thanks for your alternative answer. I took a look of this code, and it is an interesting idea in the sense you are operating on numbers instead of strings. However, I think there are several misses in your program:

  1. This problem is asking for n-th integer in the look-and-say sequence but yours only return the next one.
  2. Your program has one assumption that there is only at most nine digits are identical because you only leave one digit for the count. However, if the input contains more than nine consecutive digits, your output may not be correct.
  3. It is very interesting to see a recursive program as the problem definition is recursive in nature. However, since your program can only return the next one, I think the program in book is more elegant.

Pleas let me know what you think, and I am looking forward to your improve on this program.

0 Likes
#3

Nice solution shan!

I never think about recursion for this problem! Thanks for sharing!

As @tsunghsienlee mentioned, time complexity is same as the problem is asking for n-th from 1, but yours only returns the next.

For me, elegant is very much a subjective term that can’t be quantified (as we all have our own opinions). Sometimes, elegant code means code that is well structured, semantic, easy to read, not over-complicated. Based on this, iteration and recursion they have no big difference.

While comparing iteration and recursion in Java and other imperative languages, one thing we should consider is, recursion can lead to significant overhead because Java(JVM) doesn’t support tail recursion optimization.

0 Likes