Java solution with an array


  • 1
    Y

    The main point is to create the magical string:
    We could use the value of current element to calculate the index of the elements to create. For example,

    Value-of-Current-Element           Index-of-Element-to-Create (start from 1)
    1                                                         1
    2                                                         2, 3
    2                                                         4, 5
    1                                                         6
    1                                                         7
    2                                                         8, 9
    

    The value of the elements is changing b/w '1' and '2' alternatively.

        public int magicalString(int n) {
            if (n < 1) return 0;
            if (n == 1) return 1;
            
            int[] s = new int[n + 1];
    
            int val = 1;
            int index = 2;
            int count = 1;
            for (int i = 2; i < n + 1; i++) {
                val = val == 2 ? 1 : 2;
                s[index++] = val;
                if (val == 1) count++;
                if (index > n) break;
                if (s[i] == 2) {
                    s[index++] = val;
                    if (val == 1) count++;
                    if (index > n) break;
                }
            }
    
            return count;
        }
    

Log in to reply
 

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