Bulb Switcher [Leetcode]

Problem Description

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

Given n = 3. 

At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off]. 

So you should return 1, because there is only one bulb is on.

Solution

It is interesting that LeetCode just tried to introduce brainteaser problems.
For these types of problems, we just need to keep thinking simple, then we can solve the problem easily. In stead of imagining about all the n bulbs, we can consider 1 bulb only. Is the ith bulb on or off after n rounds? We see that the ith bulb is switched (on to off, or off to on) in the kth round if and only if i % k == 0. Initially the ith is on, so if i's number of divisors is odd, it will be on after n rounds, otherwise it is off.
Therefore, the importance question is: How many integer from 1 to n (inclusively) having odd numbers of divisors? 
We observe that if k | i then (i/k) | i . Hence, if k == i/k, or i is a square, then i has a odd number of divisors. And the number of squares less than or equal to n is floor ( sqrt (n)).
So we have the following simple code, which is accepted:

public class Solution {
    public int bulbSwitch(int n) {
        return (int) Math.sqrt(n);
    }
}

Is that short & good enough? Maybe. And we can move on to other problems in Leetcode or other sites. However, what I want to emphasize here is that, if we don't feel satisfied with the solution we have, we will eventually acquired more knowledge. ^_^. For example, in this problem, if we try to find another way to compute the result (actually it is Integer Square Root of n ), we will find many methods. One of them is below credited to this stackoverflow question.

public class Solution {
    public int bulbSwitch(int n) {
        return isqrt(n);
    }
    public int isqrt(int n){
        int op  = n;
        int res = 0;
        int one = 1 << 30; // The second-to-top bit is set: use 1u << 14 for uint16_t type; use 1uL<<30 for uint32_t type
    
    
        // "one" starts at the highest power of four <= than the argument.
        while (one > op)
        {
            one >>= 2;
        }
    
        while (one != 0)
        {
            if (op >= res + one)
            {
                op = op - (res + one);
                res = res +  2 * one;
            }
            res >>= 1;
            one >>= 2;
        }
        return res;
    }
}

REFERENCES
Efficient Integer Square Root for large number.
Square Root.
Comparison between different square root methods.

Count of Smaller Numbers After Self [LeetCode]

Problem Description

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

Solution
In this post, I'm going to write a little bit about Binary Indexed Tree and its application to solve the above problem. The problem itself is not really hard. We can solve it using many ways, including Binary Search Tree, Segment Tree, Sorting, or language specific way such as using lower_bound in C++, TreeSet (or SortedSet) in Java with method lower  (see some at the end) .
Once we know how to use Binary Indexed Tree or shortly BIT, we can solve many other problems, especially in programming contests since BIT is very easy to implement.

I suggest that you spend some time to read this article from Topcoder: Binary Indexed Tree.
Basically, in this problem, we use BIT to count the number of integers that are less than a specific number.
Suppose that a number N = A1B > 0 in binary representation, where B contains all 0 . The array tree is a BIT where tree[N] count the number of integers that are from A0B and A1B - 1 .
So if we call f[N] is the number of integers that are less than N, how we calculate its value?
Yes, you are correct, f[N] = tree[N] + f[A0B] (where A0B is in binary representation).
We also know that A0B = N & (N-1) using bit manipulation. (NOTE: on the Topcoder, they use A0B= N - (N & -N) .  
Having this in mind, to solve the problem we run from the back of the array, try each element. At the position i , we can simply calculate f[nums[i]] and put it into the result. However, we need to update the BIT here, because we have found another integer. So the natural question is which element we need to update in the BIT? Obviously, we need to update tree[N+1] by increasing its value by 1. But we do not stop there. Let N+1 = C1D where D has all 0 . As you can see, let  g[N+1] = C1D + 1D , we need to update g[N+1] also. And in turn, we need to update g[g[N+1]],so on...

Let's see the following Java code for implementation.

public class Solution {
    
    /*
    In this solution, we use a binary indexed tree (BIT)
    Our assumption is that all elements in nums are positive
    */
    
    static int MAX = 11000; //we set max value that can be store in the tree
    int[] tree = new int[MAX];
    
    public List<Integer> countSmaller(int[] nums) {
        Integer[] result = new Integer[nums.length];
        
        //make all elements in the array posive while maintaining their order
        makePositive(nums);
    
        for(int i=nums.length-1; i>=0; i--){
            result[i] = get(nums[i]);
            add(nums[i]+1, 1);
        }
        return Arrays.asList(result);
    }
    
    public void makePositive(int[] nums){
        int min = MAX;
        for(int i=0; i<nums.length; i++)    
            min = Math.min(min, nums[i]);
        if(min < 0){
            min = -min+1;
            for(int i=0; i<nums.length; i++)
                nums[i] += min;
        }
    }
    
    public void add(int idx, int val){
        while(idx<MAX){
            tree[idx] += val;
            idx += (idx & (-idx));
        }
    }
    
    public int get(int idx){
        int result = 0;
        while(idx>0){
            result += tree[idx];
            idx &= (idx-1);
        }
        return result;
    }
}

Appendix A: Binary search Tree solution (Java) - Credited to  yavinci

public class Solution {
    class Node {
        Node left, right;
        int val, sum, dup = 1;
        public Node(int v, int s) {
            val = v;
            sum = s;
        }
    }
    public List<Integer> countSmaller(int[] nums) {
        Integer[] ans = new Integer[nums.length];
        Node root = null;
        for (int i = nums.length - 1; i >= 0; i--) {
            root = insert(nums[i], root, ans, i, 0);
        }
        return Arrays.asList(ans);
    }
    private Node insert(int num, Node node, Integer[] ans, int i, int preSum) {
        if (node == null) {
            node = new Node(num, 0);
            ans[i] = preSum;
        } else if (node.val == num) {
            node.dup++;
            ans[i] = preSum + node.sum;
        } else if (node.val > num) {
            node.sum++;
            node.left = insert(num, node.left, ans, i, preSum);
        } else {
            node.right = insert(num, node.right, ans, i, preSum + node.dup + node.sum);
        }
        return node;
    }
}

Appendix B: Segment Tree Solution (Javascript) - Credited to opmiss.

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var countSmaller = function(nums) {
    if (nums.length<1) return []; 
    var SegmentTreeNode = function(s, e){
        this.start = s;
        this.end = e; 
        this.left = null; 
        this.right = null; 
        this.count = 0; 
    }; 
    var max = nums[0]; 
    var min = nums[0]; 
    nums.forEach(function(num){
        max = (max<num)?num:max; 
        min = (min>num)?num:min; 
    }); 
    var root = new SegmentTreeNode(min, max);
    var insert = function(node, num){
        ++node.count; 
        if (node.start===node.end){
            return 0; 
        }
        if (node.left===null){
            var mid = (node.start+node.end)>>1; 
            node.left = new SegmentTreeNode(node.start, mid); 
            node.right = new SegmentTreeNode(mid+1, node.end); 
        }
        if (num>node.left.end){
            var res=node.left.count+insert(node.right, num);
            return res; 
        }
        return insert(node.left, num); 
    }; 

    var res = []; 
    while (nums.length>0){
       res.unshift(insert(root, nums.pop()));  
    }
    return res; 
};

Appendix C: Merge sort (Java) - Credited to  lzyfriday.

int[] count;
public List<Integer> countSmaller(int[] nums) {
    List<Integer> res = new ArrayList<Integer>();     

    count = new int[nums.length];
    int[] indexes = new int[nums.length];
    for(int i = 0; i < nums.length; i++){
        indexes[i] = i;
    }
    mergesort(nums, indexes, 0, nums.length - 1);
    for(int i = 0; i < count.length; i++){
        res.add(count[i]);
    }
    return res;
}
private void mergesort(int[] nums, int[] indexes, int start, int end){
    if(end <= start){
        return;
    }
    int mid = (start + end) / 2;
    mergesort(nums, indexes, start, mid);
    mergesort(nums, indexes, mid + 1, end);

    merge(nums, indexes, start, end);
}
private void merge(int[] nums, int[] indexes, int start, int end){
    int mid = (start + end) / 2;
    int left_index = start;
    int right_index = mid+1;
    int rightcount = 0;     
    int[] new_indexes = new int[end - start + 1];

    int sort_index = 0;
    while(left_index <= mid && right_index <= end){
        if(nums[indexes[right_index]] < nums[indexes[left_index]]){
            new_indexes[sort_index] = indexes[right_index];
            rightcount++;
            right_index++;
        }else{
            new_indexes[sort_index] = indexes[left_index];
            count[indexes[left_index]] += rightcount;
            left_index++;
        }
        sort_index++;
    }
    while(left_index <= mid){
        new_indexes[sort_index] = indexes[left_index];
        count[indexes[left_index]] += rightcount;
        left_index++;
        sort_index++;
    }
    while(right_index <= end){
        new_indexes[sort_index++] = indexes[right_index++];
    }
    for(int i = start; i <= end; i++){
        indexes[i] = new_indexes[i - start];
    }
}

Appendix D: Merge sort (Python) - Credited to StefanPochmann

def countSmaller(self, nums):
    def sort(enum):
        half = len(enum) / 2
        if half:
            left, right = sort(enum[:half]), sort(enum[half:])
            for i in range(len(enum))[::-1]:
                if not right or left and left[-1][1] > right[-1][1]:
                    smaller[left[-1][0]] += len(right)
                    enum[i] = left.pop()
                else:
                    enum[i] = right.pop()
        return enum
    smaller = [0] * len(nums)
    sort(list(enumerate(nums)))
    return smaller

Remove Duplicate Letters [LeetCode]

Problem Description

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solutions
In my personal opinion, this problem is kinda interesting.

I. Simple Solution - O(kN) 
(Where k is the total number of distinct characters, N is length of the original string)

My first question after reading the problem description is that: What is the first character of the possible result? Can I determine it?

Yes, we can determine by an observation. If we call totalChars is the total number of distinct characters in the string. Then the required result must have a length of totalChars.  

Furthermore, its first character must be the smallest among all possible candidates. So what is a possible candidate? We easily see that a character is able to be the first character in a possible result string must have (totalChars - 1) distinct characters staying behind it in the original string.

For example, given s="bcabc", there are possible results "bca", "cab", "abc". We see that b=s[0] has 2 = totalChars-1 distinct characters behind it "a", "c". Similarly with c=s[1] and a=s[2]. Among these 3 possible candidates,  a=s[2] is the smallest. If there are 2 possible candidates with the same character, we just pick the one with smaller position.

Now after getting the first character of the result, what we do next? We can eliminate that character from the original string (by marking it as assigned). Then we repeat the process for the rest of characters!

Below is the java code.

public class Solution {

    public int ASSIGNED = -1;
    public int UNTOUCHED = 0;
    public int TOUCHED = 1;
    public char LARGE_CHAR = (char) 127;
    public String removeDuplicateLetters(String s){
        int n = s.length();
        if(n == 0) return s;
        
        //We use 128 is to avoid substraction
        //if we use 26, we have to substract 'a' from a char
        int[] status = new int[128];
        
        char c, smallestChar;
        int totalChars = 0;
        
        for(int i=0; i<n; i++){
            c = s.charAt(i);
            if(status[c] == UNTOUCHED) totalChars++;
            status[c] = TOUCHED;
        }
        
        StringBuilder bd = new StringBuilder();
        int tt = -1; //temp variable
        int last = -1; //last position of char that was assigned
        
        for(int i=totalChars; i>0; i--){
            smallestChar = LARGE_CHAR;
            totalChars = 0;
            
            //reset the status array
            for(int j='a'; j<='z'; j++) 
                if (status[j] == TOUCHED) status[j] = UNTOUCHED;
            
            //choose the smallest candiate by running backward
            for(int j=n-1; j>last; j--){
                c = s.charAt(j);
                if(status[c] == ASSIGNED) continue;
                if(status[c] == UNTOUCHED)totalChars++;
                
                if(totalChars == i) {
                    if(c <= smallestChar){
                        smallestChar = c;
                        tt = j;
                    }
                }
                status[c] = TOUCHED;
            }
            
            status[smallestChar] = ASSIGNED; //marked as assigned
            last = tt;
            bd.append(smallestChar);
        }
        
        return bd.toString();
    }
}

II. Better Solution - O(hN)
(Where h is a number between 1 and the total number of distinct characters)

After coming up with the above solution, I mumble "smallest candidates, smallest char, smallest possible, smallest..." . Yes, in that solution, we tried to find a smallest single character, why don't we try to find a smallest set of characters? Let's go on that direction!

We call a candidate set is a subset of distinct characters from 0 to i in the original string s so that there are still enough available characters from (i+1) to the end of string to make up totalChars distinct character.

Let's consider s="bcabc", at position 0, the candidate set is {b}. At 1, the candidate sets are {b}, {c}, {b,c}. At 2, the candidate sets are {b}, {c}, {a}, {b,c}, {c,a}, {b,c,a}. And our purpose is the same: find the smallest candidate set (by smallest, we mean lexicographically smallest). I.e, At 1, smallest candidate set is obviously {b}, at 1 it is {b}, and at 2 is {a}.

Suppose at position i, we have the smallest candidate set {a0,a1,..., ak}. Now at position i+1, what is the smallest candidate set? We know that {a0,a1,..., ak} are distinct. 

If s[i+1] already in {a0,a1,..., ak}, is it possible that there is a subset {ai0, ai1, ..., aij} so that  {ai0, ai1, ..., aij, s[i+1]} < {a0,a1,..., ak} is also a candidate set? If yes, we can easily see that {ai0, ai1, ..., aij} is a candidate set at position i, and {ai0, ai1, ..., aij} < {a0,a1,..., ak} . This means that {a0,a1,..., ak} is not the smallest candidate set at position i. Therefore, we don't need to care if s[i+1] is already in the candidate set (or we call it "assigned").

Now, if s[i+1] is not "assigned",  we have the same question - is it possible that there is a subset {ai0, ai1, ..., aij} so that  {ai0, ai1, ..., aij, s[i+1]} < {a0,a1,..., ak} is also a candidate set? If ak > s[i+1], and there are still characters that equals ak after i+1, we can remove ak and check again with ak-1; if there is no more, replace it by s[i+1]. If ak < s[i+1], we cannot replace ak by s[i+1]. So we just simply add s[i+1] to the set. Simply enough?

And to represent the smallest candidate set, we can use linked list, or array. Below are 2 different implementations.

a) Using Linked List (also by array ^_^)

public class Solution {

    public static char START = (char)('a'-1);
    public String removeDuplicateLetters(String s){
        if(s.length() == 0) return s;
        
        //We use 128 is to avoid substraction
        //if we use 26, we have to substract 'a' from a char
        int[] count = new int[128];
        char[] prev = new char[128];
        boolean[] assigned = new boolean[128];
        char c;
        char end = START;
        
        for(int i=0; i<s.length(); i++){
            c = s.charAt(i);
            count[c]++;
        }
        
        for(int i=0; i<s.length(); i++){
            c = s.charAt(i);
            count[c]--;
            if(assigned[c])
                continue;
                
            while(end >= c && count[end]>0){
                assigned[end] = false;
                end = prev[end];
            }
            
            prev[c] = end;
            end = c;
            assigned[c] = true;
        }
        
        StringBuilder bd = new StringBuilder();
        while(end>START){
            bd.append(end);
            end = prev[end];
        }
        return bd.reverse().toString();
    }
}

b) Using array (which similar to stack)

public class Solution {

    public String removeDuplicateLetters(String s){
        if(s.length() == 0) return s;
        
        //We use 128 is to avoid substraction
        //if we use 26, we have to substract 'a' from a char
        int[] count = new int[128];
        char[] result = new char[26];
        boolean[] assigned = new boolean[128];
        char c;
        int end = -1;
        
        for(int i=0; i<s.length(); i++){
            count[s.charAt(i)]++;
        }
        
        for(int i=0; i<s.length(); i++){
            c = s.charAt(i);
            count[c]--;
            if(assigned[c])
                continue;
                
            while(end >= 0 && result[end] > c && count[result[end]]>0){
                assigned[result[end]] = false;
                end--;
            }
            
            end++;
            result[end] = c;
            assigned[c] = true;
        }
        
        StringBuilder bd = new StringBuilder();
        for(int i=0; i<=end; i++){
            bd.append(result[i]);
        }
        return bd.toString();
    }
}

Maximum Product of Word Lengths [LeetCode]

Problem Description

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]

Return 16
The two words can be "abcw", "xtfn".

Example 2:

Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".

Example 3:

Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solution

If you first read the problem, you can think of brute force solution: for each pair of words, check whether they have a common letter, if not, get the product of their lengths and compare to max value achieved so far.
The brute force solution leads to another requirement: checking a pair of words if they contain common letters? Actually, we can do that with some pre-calculation, and with the understanding that the words contain only lowercase letters.
Since there are only 26 lowercase letters, we can represent a set of letters using an integer. So let's say if the word contains 'a', then the integer's 0th bit will be 1. If it has 'b', then the 1st is set to 1, so on and so forth.

Below is the Java code with simple implementation.
I. Simple Solution

public class Solution {
    //In this code, I used dietpepsi as array's name to give credit to dietpepsi ^_^
    public int maxProduct(String[] words) {
        int n = words.length;
        int[] dietpepsi = new int[n];
        for(int i=0; i<n; i++){
            dietpepsi[i] = getMask(words[i]);
        }
        int max = 0; int t;
        for(int i=0; i<n; i++){
            t = 0;
            for(int j=i+1; j<n; j++){
                if((dietpepsi[i] & dietpepsi[j]) == 0){
                    t = Math.max(t, words[j].length());
                }
            }
            max = Math.max(max, t*words[i].length());
        }
        return max;
    }
    private int getMask(String s){
        int mask = 0;
        for(char c: s.toCharArray()){
            mask |= 1 << (c - 'a');
        }
        return mask;
    }
}

II. Improvement on (I)
We can make some improvement by first sorting the words according to their lengths. Then for the ith word in the sorted array, we check from i-1 to 0 to see if there is a word that shares no common letter with it. Then we calculate the product, compare to the max value so far, stop the loop for the ith word, and move on with the (i+1)th word.

public class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        
        Arrays.sort(words, new LengthComparator());
        int[][] dietpepsi = new int[n][2];
        int max = 0;
        for(int i=0; i<n; i++){
            dietpepsi[i][0] |= getMask(words[i]); 
            dietpepsi[i][1] = words[i].length();
        }
        
        int last = 0;
        for(int i=n-1; i>=1; i--){
            for(int j=i-1; j>=last; j--){
                if((dietpepsi[i][0] & dietpepsi[j][0]) == 0){
                    max = Math.max(dietpepsi[i][1] * dietpepsi[j][1], max);
                    last = j;
                    while(last<n && dietpepsi[last][1]==dietpepsi[j][1]) last++;
                    break;
                }
            }
        }
        return max;
    }
    private int getMask(String s){
        int mask = 0;
        for(char c: s.toCharArray()){
            mask |= 1 << (c - 'a');
        }
        return mask;
    }
    class LengthComparator implements Comparator<String>{
        public int compare(String a, String b){
            return a.length() - b.length();
        }
    }
}

PS: Do you think there is a O( NLgN) or O(N) solution for this problem?

[Hackerrank] Manasa and Prime Game

Problem Description (Credited to Hackerrank)
Manasa loves the NIM Game, but having played the same game so many times, she gets bored one day. So she wants to change the rules of the game. As she loves prime numbers, she makes a new rule: any player can remove only prime number of balls from a bucket. But there are infinite prime numbers. So to keep the game simple, a player can remove only x number of balls from a bucket, where x belongs to the set S.




 S={2,3,5,7,11,13}

Now whole game can be described as follows:
Given N number of buckets and kth bucket having Ak number of balls, a player can choose a bucket and remove x number of balls from that bucket where x belongs to S. Manasa plays the first move against Sandy. Who will win if both of them play optimally?

Input Format 
The first line contains an integer T i.e. the number of test cases.
First line of each test case will contain an integer N i.e. number of buckets.
Next lines will contain N integers.

Output Format 
Print the name of the winner - "Manasa" or "Sandy".

Constraints
1≤T≤10 
1≤N≤104 
1≤Ak≤1018

Sample Input

2
2
10 10
3
2 2 3

Sample Output

Sandy
Manasa

Solution

This is another example of problems in game theory. If Permutation Game is solved using Minimax algorithm, this problem requires some knowledge about Nim games, and Grundy number (or Nimber).
You can read more about Nim Games and Grundy number using reference links at the end of the post, but I will describe it shortly so that you get how to do (even without understanding Nim Games and Grundy numbers!!!).

In this type of problem, one game is a combination of multiple sub-games. At each time, a player chooses a sub-game to play. Who is the last person to make a move is the winner. And to decide who is the winner, we need to calculate Grundy numbers for all the sub-games, and take the XOR value of them. If this value > 0, then the first player is the winner. Otherwise, the second player is the winner !!! Sound like magic? Again, I suggest you read through everything I put in reference links to understand the theory behind.

So what is the sub-games here? Assuming that the 2 players play only with a bucket. So this is a sub-game.

Now, how to calculate Grundy number for a sub-game? Call C is the current state of the sub-game (In this problem, C is the number of balls in the bucket). Call T1, T2, ..., Tn are all possible states can be reached from C within a single move. And call G is a function on these states. G is defined as followed:

G map a state to non-negative integer.
G(losing state) = 0
G(C) = smallest number that not in the set {G(T1), G(T2), ..., G(Tn)} where T1, T2, ..., Tn are all possible states reached from current state C by a single move.

How to apply for this problem?
First, we need to define losing state. Losing state is the state a player cannot remove balls. In this problem, losing states are 0 and 1. Therefore, we have G(0) = G(1) = 0.

So we have: G(2) = 1. (Why?), G(3) = 1 (Why?), G(4) = 2 (Why?), and so on.

And the problem ask us to calculate Grundy number for 1<=Ak <= 10^18!
The Grundy number G(Ak) can be calculated using Dynamic Programming if Ak is small. But 10^18 is way too big. We have to find another way.

We see that, from the current state C, we can only move to maximum 6 other states. This means that the Grundy numbers may be at most 6 (Why?). That means there is a high chance that they are periodic! Yes, they are periodic.

Hence, I wrote a quick Python script to see if it is periodic.

def run():
  n = 100
  dp = [0]*(n+1)
  a = [2,3,5,7,11,13]
  b = [0] * (23)
  for i in range(2, n+1):
    for k in a:
      if i >= k:
        b[dp[i-k]]= 1
    for k in range(len(b)):
      if b[k] == 0: 
        dp[i] = k
        break
    for k in range(len(b)): b[k] = 0
  print dp
if __name__ == "__main__":
  run()

And the result is

[0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1
, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2,
2, 3, 3, 4, 0, 0]

So the period will be values = [0, 0, 1, 1, 2, 2, 3, 3, 4]. Simple, isn't it?
And G(Ak) = values[ Ak % 9].
Now, we just need to XOR up all Grundy numbers G(A1) ^ G(A2) ^ ... ^ G(An).

Below is the code in java for your reference.
Before seeing the solution, try yourself with the following test case:

5
10
84 87 78 16 94 36 87 93 50 22
10
63 28 91 60 64 27 41 27 73 37
10
12 69 68 30 83 31 63 24 68 36
10
30 3 23 59 70 68 94 57 12 43
10
30 74 22 20 85 38 99 25 16 71

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        int t = ni();
        for(int i=0; i<t; i++){
            System.out.println(solve());
        }
    }
    
    public static int[] values = new int[]{0, 0, 1, 1, 2, 2, 3, 3, 4};
    public static String solve(){
        int n = ni();
        long ak;
        long nimber = 0; //or grundy number
        for(int i=0; i<n; i++){
            ak = nl();
            nimber ^= values[(int) (ak % values.length)];
        }
        if(nimber > 0) return "Manasa";
        return "Sandy";
    }
    
    public static Scanner sc = new Scanner(System.in);
    public static int ni(){
        return sc.nextInt();
    }
    public static long nl(){
        return sc.nextLong();
    }
}

Reference links:
Combinatorial Games - PDF (Standford course)
Sprague-Grundy Theorem (Wiki)
Grundy Numbers (Nice blog post)

[Hackerrank] Permutation Game

Problem Description (Credited to Hackerrank)

Alice and Bob play the following game:

1. They choose a permutation of the first N numbers to begin with.
2. They play alternately and Alice plays first.
3. In a turn, they can remove any one remaining number from the permutation.
4. The game ends when the remaining numbers form an increasing sequence. The person who played the last turn (after which the sequence becomes increasing) wins the game.

Assuming both play optimally, who wins the game?
Input Format: 
The first line contains the number of test cases T. T test cases follow. Each case contains an integer N on the first line, followed by a permutation of the integers 1..N on the second line.

Output Format: 

Output T lines, one for each test case, containing "Alice" if Alice wins the game and "Bob" otherwise.

Constraints:

1<=T<=100
2<=N<=15
The permutation will not be an increasing sequence initially.

Solution

Hackerrank is a very good place for training our programming ability. However, one thing I realize is that its discussion is not really helpful, and many problems lack editorials. So I decided to start writing analysis on the website's problems with the hope that it can help someone on their joyful journey of studying algorithms.

This problem is categorized as a game theory problem. Most of the times, game theory problems can be solved either using Minimax algorithm or with Nim game knowledge ( with Grundy numbers which I'll cover in a future post), so as long as we equip ourselves with these kinds of knowledge, game theory is not hard at all.

For this problem, we can solve it by Minimax algorithm (or shortly Minimax).

To be simple, Minimax can be described as: My current state is S, and I need to calculate the score f(S). Consider all the possible states T1, T2, ..., Tn that I can make a move from S, then I have:
f(S) = - min ( f(T1), f(T2), ..., f(Tn))
Note on the minus sign. Why it is minus? The explanation is that we are playing 2-play games. So next turn is my opponent turn, isn't it? Therefore, if he wins in the next state, that means I lose in the current state.

And often, Minimax can be solved simply by recursion with memoization!!! So keep in mind, M&M (Minimax & Memoization) is the normal way to solve this kind of problems.

Go back to our problem. How can we define a state in this game? Simply, the state is all the available numbers! However, in order to easily using memoization, we need a better way to represent states here. You got the idea right? (^_^) Let's use a polynomial to map an array of numbers to a number, then we can use hash table for memoization - this technique we can reuse a lot and alot!

Since the constraint here is N <= 15, so we can use 16 as base (since 16 ^ 15 = 2^60 is in range of a long integer) . Why 16, not N+1? Because using 16 enables fast multiplication by bit manipulation.
So for example, given array: [1, 3, 2], its equivalent numbers is 1 * 16^2 + 3*16 + 2 = 306, and we can do bit manipulation by ((((1 << 4) + 3) << 4) + 2).

With the above analysis, I hope you get an idea to solve the problem. Below is the code for your reference.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        int t = ni();
        for(int i=0; i<t; i++){
            int n = ni();
            Map<Long, Boolean> map = new HashMap<Long, Boolean>();
            int[] numbers = new int[n];
            for(int j=0; j<n; j++){
                numbers[j] = ni();
            }
            if(aliceWin(numbers, map)) System.out.println("Alice");
            else System.out.println("Bob");
        }
    }
    
    public static boolean aliceWin(int[] a, Map<Long, Boolean> map){
        long h = hashCode(a); int temp; 
        if(map.containsKey(h)) return true;
        
        for(int i=0; i<a.length; i++){
            if(a[i]>0){
                temp = a[i] ;
                a[i] = 0;
                if(isIncreasing(a)){
                    map.put(h, true);
                    a[i] = temp;
                    return true;
                }
                if(!aliceWin(a, map)) {
                    map.put(h, true);
                    a[i] = temp;
                    return true;
                }
                a[i] = temp;
            }
        }
        return false;
    }
    
    public static long hashCode(int[] a){
        long result = 0;
        for(int i=0; i<a.length; i++){
            result = (result << 4) + a[i];
        }
        return result;
    }
    public static boolean isIncreasing(int[] a){
        int last = 0;
        for(int i=0; i<a.length; i++){
            if (a[i] > 0){
                if(last > a[i]) return false;
                last = a[i];
            }
        }
        return true;
    }
    public static int ni(){
        return sc.nextInt();
    }
    
    public static void print(Object... args){        
        System.out.println(Arrays.deepToString(args));
    }
}