O(n) Time and O(n) Space


  • 1

    It's easy to get the result by generating all the numbers up to n.
    Use a index to track the times that current number occurs and a index to assign the number.

    public int magicalString(int n) {
            int[] magic=new int[n];
            int number=1, count=0;
            int index=0;
            int res=0;
            for(int i=0;i<n;i++){
                res+=number==1?1:0;
                magic[i]=number;
                count++;
                if(count==magic[index]){
                    number=(number+1)/number;
                    count=0;
                    index++;
                }
            }
            return res;
        }
    

    I was wondering if it's possible to generate the magic function like Fibonacci.


Log in to reply
 

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