Simple Java solution using queue


  • 0
    S

    The basic idea is to use the digits seen so far to generate subsequent digits. Use a queue to store the digits to be processed.

    public int magicalString(int n) {
            if (n == 0) return 0;
            if (n < 4) return 1;
            Queue<Integer> nums = new LinkedList<>();
            nums.add(2); // Third digit in the sequence
            boolean nextIsOne = true;
            int numOnes = 1;
            
            for (int i = 3; i <= n; i++) {
                int popped = nums.poll();
                if (popped == 1) numOnes++;
                int toOffer = nextIsOne ? 1 : 2;
                nums.offer(toOffer);
                if (popped == 2) nums.offer(toOffer);
                nextIsOne = !nextIsOne;
            }
            return numOnes;
    }
    

Log in to reply
 

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