Simple Java solution using one array and two pointers


  • 42

    Algorithm:

    1. Create an int array a and initialize the first 3 elements with 1, 2, 2.
    2. Create two pointers head and tail. head points to the number which will be used to generate new numbers. tail points to the next empty position to put the new number. Then keep generating new numbers until tail >= n.
    3. Need to create the array 1 element more than n to avoid overflow because the last round head might points to a number 2.
    4. A trick to flip number back and forth between 1 and 2: num = num ^ 3
    public class Solution {
        public int magicalString(int n) {
            if (n <= 0) return 0;
            if (n <= 3) return 1;
            
            int[] a = new int[n + 1];
            a[0] = 1; a[1] = 2; a[2] = 2;
            int head = 2, tail = 3, num = 1, result = 1;
            
            while (tail < n) {
                for (int i = 0; i < a[head]; i++) {
                    a[tail] = num;
                    if (num == 1 && tail < n) result++;
                    tail++;
                }
                num = num ^ 3;
                head++;
            }
            
            return result;
        }
    }
    

  • 4

    To flip x between any two given values x1 and x2, I think using x = x1 + x2 - x is more straightforward (as long as no overflow).


  • 0

    @zzg_zzm Yes, that is a more general approach. Thanks!


  • 0

    @shawngao In what way more general?


  • 0

    @StefanPochmann They way @zzg_zzm described, x = x1 + x2 - x, if we know x1 + x2 won't overflow.


  • 2

    @shawngao said in Simple Java solution using one array and two pointers:

    @StefanPochmann They way @zzg_zzm described, x = x1 + x2 - x, if we know x1 + x2 won't overflow.

    I think @StefanPochmann means x ^= (x1^x2) can achieve the same purpose still using ^ operator. So rewriting 3 = 1^2 is more general :-)


  • 0

    @zzg_zzm yep, agreed. thanks.


  • 1
    B

    You can just put a tail < n in the for's condition

    public class Solution {
        public int magicalString(int n) {
            if (n <= 0) {
                return 0;
            }
            if (n <= 3) {
                return 1;
            }
            
            int[] a = new int[n];
            a[0] = 1; a[1] = 2; a[2] = 2;
            int head = 2, tail = 3, num = 1, result = 1;
            while (tail < n) {
                for (int i = 0; i < a[head] && tail < n; i++) {
                    a[tail] = num;
                    if (num == 1) {
                        result++;
                    }
                    tail++;
                }
                num = num ^ 3;
                head++;
            }
            
            return result;
        }
    }

  • 1
    J

    why must start 1,2,2?

    I wonder whether there is magical string start from 2,2,1,1,2,1,2,2...


  • 2

    @jh2016 said in Simple Java solution using one array and two pointers:

    why must start 1,2,2?

    I wonder whether there is magical string start from 2,2,1,1,2,1,2,2...

    I got your point. Actually, the magic string S is uniquely determined by only the first char S[0] (either '1' or '2'). Either case gives a well defined problem, but they are "logically" duplicated problem, so OJ just simply picked the case S[0] = 1 to define as magic string. The method to solve "the other" magic string will be duplicated anyway.

    Hopefully, it will help.


  • 0
    P

    Good post, I like the idea to represent the characters with int array, and flip between 1 and 2 with XOR. x = x1 + x2 - x is also very good idea.

    As I want to avoid the nested loop, I used the algorithm below:

    int magicalNaive (int n) {
            string magical;
            magical.append("122");
            char next = '1';
            /* the position in magical that act as a recurrence count */
            int cntIdx = 2;
            int cnt = 2;
            /* '1' count in magical string */
            int ret = 1;
            for (int i = 3; i < n; i++) {
                if (cnt == 0) {
                    cnt = magical[++cntIdx] - '0';
                    next = next == '1' ? '2' : '1';
                }
                
                /* push in next to magical top */
                ret += next == '1';
                
                magical.push_back (next);
                cnt--;
            }
            
            return n < 1 ? 0 : ret;
        }
    

  • 4

    My solution is naive: https://en.wikipedia.org/wiki/Kolakoski_sequence
    Using a pointer to point the repeat times number. If it is 1, no repeat, if it is 2, add two repeat number to the result list.

    1 and 2 are appear one by one, so using num = num ^ 3.

        public int magicalString(int n) {
          List<Integer> nums = new ArrayList();
          nums.add(1);
          nums.add(2);
          nums.add(2);
          int repIndex = 2, i = 3, num = 1, res = 0;
          while(i < n){
             int repeat = nums.get(repIndex);
             repIndex++;
             if(repeat == 1) {
                 addOne(nums, num);
                 i++;
             } else {
                 addTwo(nums, num);
                 i += 2;
             }
             num ^= 3;
          }
          
          for(i = 0; i < n; i++){
            if(nums.get(i) == 1) res++;  
          }
          return res;
        }
        
        void addOne(List<Integer> nums, int num){
          nums.add(num);      
        }
        
        void addTwo(List<Integer> nums, int num){
          nums.add(num);  
          nums.add(num); 
        }

  • 0
    G

    Similar idea, one loop

    public int magicalString(int n) {
            if(n == 0) return 0;
            
            StringBuilder sb = new StringBuilder("122");
            int sPtr = 2, groupPtr=2, count = 1;
            int nextChar = 1;
            
            while(sPtr < n) {
                 sb.append(nextChar);
                 sPtr++;
                if(sb.charAt(groupPtr) == '2') {
                    sb.append(nextChar);
                    sPtr++;
                } 
                if(nextChar == 1) {
                    if(sPtr < n) count+=1;
                    if(sb.charAt(groupPtr) == '2' && sPtr-1 < n)  count+=1;
                } 
                nextChar = nextChar ^ 3;
                groupPtr++;
            }
            return count;
        }
    

  • -3
    Z

    No need to use O(n) space, just keep a window of numbers you will concern.
    But still, brilliant solution of yours!

        public int magicalString(int n) {
            if(n==0)return 0;
            int res=1,count=3;
            Deque<Integer>list = new LinkedList<>();
            list.offer(2);
            while(count<n){
                int next = (list.peekLast()==1?2:1);
                int occur = list.removeFirst();
                for(int i=1;i<=occur&&count<n;i++){
                    if(next==1)res++;
                    count++;
                    list.add(next);
                }
            }
            return res;
        }
    

  • 0

    @zhangsikai123 said in Simple Java solution using one array and two pointers:

    No need to use O(n) space

    Yours does, too.


  • 0
    Z

    @ManuelP That's true, but less.


  • 0

    @shawngao said in Simple Java solution using one array and two pointers:

    Create two pointers head and tail. head points to the number which will be used to generate new numbers. tail points to the next empty position to put the new number. Then keep generating new numbers until tail >= n.

    I hate Advanced Math.... I know it's Kolakoski sequence but I still don't know what's the trick to generating the next number.

    I draw a graph:

                1    2    2    X    M
    head:                 ^   
    tail:                      ^
    

    Why will the X be 1 if we don't know what the M is?


  • 0

    @zzg_zzm

    Thanks for your clarification butI still don't get why string S is determined by the first char S[0].....And how it will be a "logically" duplicated.... Sorry about my bad math...


  • 0
    B

    Improve Space Complexity with Deque.

      public int magicalString(int n) {
          if(n <= 0){
              return 0;
          }
          if(n <= 3){
              return 1;
          }
        
        Deque<Integer> que = new ArrayDeque<>(Arrays.asList(2));
        int res = 1;
        int len = 2;
        
        int nextNum = 1;
        
        while(len < n){
            int curNum = que.removeFirst();
            if(curNum == 1){
                res++;
            }
            len++;
            
            for(int i = 0; i < curNum; i++){
                que.addLast(nextNum);
            }
            nextNum = nextNum ^ 3;
        }
        
        return res;
    }

  • 0

    @bailiang said in Simple Java solution using one array and two pointers:

    Improve Space Complexity with Deque.

    How much does it improve?


Log in to reply
 

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