Java Straightforward Solution


  • 0
    Z

    Hi there! I decided to share my solution. To know the number of ones, we definitely need to know how the sequence will continue. That can be done by relying on the 2 nd rule of magical string. Frequency sequence is the same as the sequence. It means that the sequence itself tells us the next number in it. In other words if we meet 1 then next number to put is a single number, if we meet 2 then next number must be written twice. Thus, to realize that idea we need 3 pointers:

    • ptr1 - first pointer that shows frequency of next number
    • ptr2 - second pointer that shows the position of the new number to be inserted
    • next - next number to be inserted into the sequence

    That's it. Overal time and space complexities are O(n).

    P.S Is it possible to solve for O(1) space complexity?:=)

    public class Solution {
        String str = "1221121221221121122";
        int seq[]; 
        public int magicalString(int n) {
            seq = new int[n];
            init();
            return compute();
        }
      
        private int compute(){
            int res = 0;
            for(int i =0;i<seq.length;i++) {
                if(seq[i] == 1){
                    res++;
                }
            }
            return res;
        }
        
        private void init(){
            for(int i = 0;i<Math.min(seq.length,str.length());i++){
                seq[i] = str.charAt(i)-'0';
            }
            if(seq.length<=str.length()) return;
            int next = 1;
            int ptr1 =0;
            int ptr2 = 0;
            while(ptr2<seq.length){
                if(seq[ptr1] == 1){
                    seq[ptr2] = next;
                    ptr2++;
                } else {
                    seq[ptr2] = next;
                    ptr2++;
                    if(ptr2 == seq.length) break;
                    seq[ptr2] = next;
                    ptr2++;
                }
                ptr1++;
                next = (next == 1)?2:1;
            }
           
        }
    }

Log in to reply
 

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