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)

Perfect Squares [LeetCode] Part 2: Solve it Mathematically

This is continuation of the previous post - Perfect Squares. I've decided to separate the problem into two parts because the solution using maths knowledge recalled me the happy time when I studied maths in high school.

Before we start, I want to confirm that all the returned values will always be in range [1,4] inclusively. Why is that? It is because we have Lagrange's Four Square Theorem, also known as Bachet's conjecture:
Every natural numbers can be expressed as a sum of four square numbers. (*)

The theorem is proved by Lagrange in 1770. To understand the proof, I suggest you read the provided link from Wiki. And later, the talented mathematician Ramanujan did a generalization on the theorem.  I have to say it is extremely sad that Ramanujan's life was too short, even though his legacy is more than 3900 results (mostly identities and equations).

As a note, many proofs of the theorem use the Euler's four square identity:

Picture 1: Euler's Four Square Identity

Now I suggest you read this page. After reading it, you can solve this LeetCode problem mathematically! And you can also understand the algorithm to represent a natural number as a sum of four perfect squares!

Let me help you to summarize the related part of it.

From the article, you can find that if a number is in the form n = 4^r (8k+7) (Where ^ is power), then n cannot be represented as a sum of less than 4 perfect squares. If n is not in the above form, then n can be represented as a sum of 1, 2, or 3 perfect squares.

So now you know the basic theory behind, we can start coding!

I. Python Code

class Solution(object):
    
    def is_square(self, n):
        temp = int(math.sqrt(n))
        return temp*temp == n
        
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        while n & 3 == 0: #n % 4
            n = n >> 2
        if n % 8 == 7: return 4
        
        sqrt_n = int(math.sqrt(n))
        if self.is_square(n): return 1
        else:
            for i in range(1, sqrt_n+1):
                if self.is_square(n-i*i):
                    return 2
        return 3

II. Java Code

public class Solution {
    public boolean is_square(int n){
        int temp = (int) Math.sqrt(n);
        return temp * temp == n;
    }
    public int numSquares(int n) {
        while ((n & 3) == 0) //n % 4 == 0
            n >>= 2;
        if ((n & 7) == 7) return 4; //n% 8 == 7
        
        if(is_square(n)) return 1;
        int sqrt_n = (int) Math.sqrt(n);
        for (int i = 1; i<= sqrt_n; i++){
            if (is_square(n-i*i)) return 2;
        }
        return 3;
    }
}

III. C++ Code

class Solution {
public:
    int is_square(int n){
        int temp = (int) sqrt(n);
        return temp * temp == n;
    }
    int numSquares(int n) {
        while ((n & 3) == 0) //n%4 == 0
            n >>= 2;
        if ((n & 7) == 7) return 4; //n % 8 == 7
        if(is_square(n)) return 1;
        int sqrt_n = (int) sqrt(n);
        for(int i = 1; i<= sqrt_n; i++){
            if (is_square(n-i*i)) return 2;
        }
        return 3;
    }
};

IV. Javascript Code

/**
 * @param {number} n
 * @return {number}
 */
var is_square = function(n){
    var t = Math.floor(Math.sqrt(n));
    return t * t == n;
}
var numSquares = function(n) {
    while ((n & 3) ===0) //n%4 == 0
        n >>=2;
    if((n&7) == 7) return 4; //n % 8 = 7
    if(is_square(n)) return 1;
    var sqrt_n = Math.floor(Math.sqrt(n));
    for(var i=1; i<= sqrt_n; i++){
        if(is_square(n-i*i)) return 2;
    }
    return 3;
};

Perfect Squares [LeetCode]

Problem Description

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Solutions

I. Dynamic Programming
This problem can be solved by dynamic programming. If we call dp is the array of least numbers of perfect square numbers for each integer from 1 to n, we have the following relation:
dp[n] = 1 + min (dp[n-i*i] for i from 1 to square root of n)
However, (as of 2015-09-09) I saw people complain that the dynamic programming solution got Time Limit Exception (TLE) with Python. Therefore, StefanPochmann, a member of LeetCode, solved the solution by using "Static" dynamic programming. That means the array dp is a static variable of the class Solution.
Dynamic Programming C++ Code

int numSquares(int n) {
    static vector<int> dp {0};
    while (dp.size() <= n) {
        int m = dp.size(), squares = INT_MAX;
        for (int i=1; i*i<=m; ++i)
            squares = min(squares, dp[m-i*i] + 1);
        dp.push_back(squares);
    }
    return dp[n];
}

Dynamic Programming C++ : Reverse for-loops inside out

int numSquares(int n) {
    static vector<int> dp {0};
    int m = dp.size();
    dp.resize(max(m, n+1), INT_MAX);
    for (int i=1, i2; (i2 = i*i)<=n; ++i)
        for (int j=max(m, i2); j<=n; ++j)
            if (dp[j] > dp[j-i2] + 1)
                dp[j] = dp[j-i2] + 1;
    return dp[n];
}

Dynamic Programming Python Code

class Solution(object):
    _dp = [0]
    def numSquares(self, n):
        dp = self._dp
        while len(dp) <= n:
            dp += min(dp[-i*i] for i in range(1, int(len(dp)**0.5+1))) + 1,
        return dp[n]

Dynamic Programming Ruby Code

$dp = [0]
def num_squares(n)
  $dp << (1..$dp.size**0.5).map { |i| $dp[-i*i] }.min + 1 until $dp[n]
  $dp[n]
end

However, in Python, if you test that code with test case 1,000,000, you will get the TLE error.
NOTE: I'm very happy that LeetCode now provides testing against custom input (From 2015-09-09). This feature I've seen in Hackerrank and wanted LeetCode to implemente it for quite a long time ago.

II. Breadth First Search

Picture 1: Graph of numbers 

In this problem, we define a graph where each number from 0 to n is a node. Two numbers p < q is connected if (q-p) is a perfect square.

So we can simply do a Breadth First Search from the node 0.

Below is the Python code that even can pass the custom test case of 1,000,000.

Breadth First Search Python Code

class Solution(object):
    _dp = [0]
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
       
        q1 = [0]
        q2 = []
        level = 0
        visited = [False] * (n+1)
        while True:
            level += 1
            for v in q1:
                i = 0
                while True:
                    i += 1
                    t = v + i * i
                    if t == n: return level
                    if t > n: break
                    if visited[t]: continue
                    q2.append(t)
                    visited[t] = True
            q1 = q2
            q2 = []
                
        return 0

PS: For now, I do not have very much time to write the code in Java, C++, C#, Javacript or Ruby, so you are extremely welcome to post your solutions as a comment!