Java Simple O(n) Time O(n) Space


  • 0

    We start off with the base magic sequence "122" and generate subsequent digits up to digit n, counting the number of '1' elements added to the sequence in the process.

    public int magicalString(int n) {
        if (n<=0) return 0;
        StringBuilder magic = new StringBuilder("122");
        int count = 1, nextDigitCount;
        for (int i=3, indx=2; i<n; i+=nextDigitCount, indx++) {
            int nextDigit = indx%2 + 1;
            nextDigitCount = Math.min(magic.charAt(indx) - '0', n-i);
            if (nextDigit == 1) count += nextDigitCount;
            magic.append(nextDigit);
            if (nextDigitCount == 2) magic.append(nextDigit);
        }
        return count;
    }
    

Log in to reply
 

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