Little verbose but intuitive solution from wikipedia, Did anyone post this before?


  • 0
    S

    This idea is directly derived from https://en.wikipedia.org/wiki/Kolakoski_sequence.
    Here is the code.

            int[] kseq = new int[n+1];  // start from 1, the kolakoski sequence
            int[] xseq = new int[n+1];  // record how many copies should print
            int k = 1;  // real index that is to be filled
            int cnt = 0;    // #1 in kseq
            boolean isOdd = true;
            for (int i = 1; i <= n; i++) {
                if (kseq[i] == 0) {
                    xseq[i] = i;
                }
                else
                    xseq[i] = kseq[i];
                int seed = -1;
                if (isOdd) {
                    seed= 1;
                    isOdd = false;
                }
                else {
                    seed =2;
                    isOdd =true;
                }
                int tmp = k;
                for (; k < n+1 && k <= tmp+xseq[i]-1; k++)
                    kseq[k] = seed;
                if (seed == 1)
                    cnt += Math.min(xseq[i], n-tmp+1);
    
                if (k >= n+1)
                    break;
            }
            return cnt;
    }

Log in to reply
 

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