We should do better than O(n)


  • -1

    I have a naive O(n) algorithm below.
    Let's think hard if there is O(1) algorithm. We've seen patterns in the result.

    public class Solution {
        public int magicalString(int n) {
            if (n == 0) return 0; 
            // initialize the string with "122", after "122", the char being considered is surely not part of the newly added segment of the string. 
            StringBuilder sb = new StringBuilder("122"); 
            int cnt = 0, pos = 2, pre = 2; 
            while (sb.length() <= n) {  
                if (sb.charAt(pos) == '1') 
                    // if previously "1" or "11" was appended, this time add "2" or "22".  
                    sb.append(pre == 1 ? "2" : "1"); 
                else sb.append(pre == 1 ? "22" : "11"); 
                pre = pre == 1 ? 2 : 1; 
                pos++; 
            } 
            // Calculate how many 1's in the string builder. 
            for (int i = 0; i < n; i++) 
                 if (sb.charAt(i) == '1') cnt++; 
                
            return cnt; 
        }
    }

  • 0
    C

    @zzhai the while loop already makes it O(n)


  • 0

    @cgxy1995

    Pls read the statement on the top.


  • -1
    C

    @zzhai no. there is no pattern in this problem


  • 0

    @zzhai What are the patterns you say we have seen?

    It's the Kolakoski sequence and apparently it's unknown whether the density of 1's is 1/2. That makes me doubt that there is an easy formula to solve our problem. If there were one, then I suspect the density question would've been solved already.

    But the article mentions a way to solve it in O(n) time and O(log n) space. That might be worth doing (but I won't).


  • 0

    @StefanPochmann

    Saying there is a well-defined pattern in the sequence was premature.
    I only checked the first 100 characters, and noticed 221121 seems to occur at a regular pace.
    221121 is a special segment IMHO. It consists of 2 1's, 2 2's, 1 1 and 1 2.

    12211212212211211221211212211211212212211212212112112212211212212211211212212112212211212212211211221


  • 0

    @zzhai What do you mean with regular pace? Doesn't look regular to me. And if you mean "often", there are other length-6 segments that appear about as often, here's the complete distribution in that prefix:

    >>> s = '12211212212211211221211212211211212212211212212112112212211212212211211212212112212211212212211211221'
    >>> sixes = {s[i:i+6] for i in range(len(s) - 5)}
    >>> for six in sorted(sixes, key=lambda six: -s.count(six)):
            print six, s.count(six)
    
    122112 8
    221121 8
    112122 7
    121221 7
    211212 7
    212211 7
    221221 6
    122122 6
    212212 6
    112112 5
    211211 5
    121122 4
    121121 4
    211221 4
    122121 3
    221211 3
    212112 3
    112212 3
    

    Btw I now did an O(log n) space algorithm after all, because I thought it might be a nice application for generators.


  • 0

    @StefanPochmann Thanks for the reference that I wasn't aware that this is a well known sequence which have been well studied before.

    To be honest, I was also attempting to figure out a pattern or formulate a mathematical equation initially since the setup of the sequence is so simple, and, of course, no results. So, this sequence can be viewed as an "irrational" number, very interesting.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.