Detect a cycle in linked list

The problem is to detect a cycle in a linked list, and find a start node of the cycle.
We have a linked list.

First, we have to know how many nodes in the cycle. To find out, we use two pointers with different speed and stop when the node is the same. Then use only one pointer and move forward, and save current node and count the node, then stop when the pointer is in the same node.
Second, use two pointers, each apart the the number of nodes in the cycle. When we met the same node while moving two pointers, that is the start node of the cycle.
Complete source in Java is in the below.


 import java.io.*;
 class myCode
 {
   public static void main (String[] args) throws java.lang.Exception
   {
     System.out.println("Hello Java");
     myCode code = new myCode();
     code.doWork();
   }
   public void doWork() {
     Node node = new Node(1);
     Node temp1 = new Node(2);
     Node temp2 = new Node(3);
     Node temp3 = new Node(4);
     Node temp4 = new Node(5);
     node.next = temp1;
     temp1.next = temp2;
     temp2.next = temp3;
     temp3.next = temp4;
     temp4.next = temp2;
     int cycle = detect(node);
     int start = findStart(node,cycle);
     System.out.println(cycle);
   }
   public int detect(Node head) {
     Node first = head;
     Node second = head;
     int count = 0;
     boolean found = false;
     while (first != null && second.next != null) {
       first = first.next;
       second = second.next.next;
       if (first.value == second.value) {
         found = true;
         break;
       }
     }
     if (found) {
       int start = first.value;
       while (first != null) {
         first = first.next;
         count++;
         if (first != null && first.value == start) {
           return count;
         }
       }  
     }
     return -1;
   }
   public int findStart(Node head, int cycle) {
     Node first = head;
     Node second = head;
     for (int i=0;i<cycle;i++) {
       second = second.next;
     }
     while (first.value != second.value) {
       first = first.next;
       second = second.next;
     }
     return second.value;
   }
   class Node {
     int value;
     Node next = null;
     public Node(int val) {
       value = val;
     }
   }
 }

Quick Sort

Quick sort runs O(nlogn). It is similar with merge sort, but it differs by selecting a pivot and partition the array based on the pivot element.
Let's look at an example.
We have an integer array {7,5,9,10,1,6,13,2,8},  and choose pivot element. In this case we choose pivot as the last element, i.e., 8.
The rearrange the left and right based on pivot.

use index i=0, j=array.length-1
{7,5,2,6,1}            {8}              {10,13,9}
{}  {1} {7,5,2,6}   {8}              {}  {9}  {10,13}
{1} {2,5} {6} {7}  {8}              {9} {10} {13}
{1} {2} {5} {6} {7}  {8}           {9} {10} {13}
{1,2,5,6,7,8,9,10,13}

The code in Java is in the below. Please be careful when you partition the array based on the pivot.
For example, if you partition an array {5,3,7}, and set the pivot as the last element, it end up with i=1,j=1, and pivot = 7. Here, you only swap if the pivot is less than i-th element.

 import java.io.*;
 class myCode
 {
   public static void main (String[] args) throws java.lang.Exception
   {
     System.out.println("Hello Java");
     int[] input = {5,7,9,10,1,6,13,2,8};
     quickSort(input, 0, input.length-1);
     System.out.println("sorted list:");
     for (int i=0;i<input.length;i++) {
       System.out.print(input[i] + ",");
     }
   }
   public static void quickSort(int[] array, int start, int end) {
     if (end - start < 1) {
       return;
     } else if ((end - start) == 1) {
       if (array[start] > array[end]) {
         int temp = array[start];
         array[start] = array[end];
         array[end] = temp;
       }
     } else {
       partition(array, start, end);
     }
   }
   public static void partition(int[] array, int start, int end) {
     int pivot = array[end];
     int i=start;
     int j=end-1;
     while (i<j) {
       if (array[i]>pivot && array[j] < pivot) {
         int temp = array[i];
         array[i] = array[j];
         array[j] = temp;
         i++;
         j--;
       } else if (array[i] < pivot) {
         i++;
       } else if (array[j] > pivot) {
         j--;
       }
     }
     //swap i to end
     if (array[i] > array[end]) {
       int temp2 = array[i];
       array[i] = array[end];
       array[end] = temp2;
     }
     quickSort(array,start,i);
     quickSort(array,i+1,end);
   }
 }

Merge Sort

Merge sort runs in O(nlogn). It uses an divide and conquer. First, it divide the original array into two sub array until it has only 1 element in the array. Then, it merge the sub-arrays by sorting it in correct order.
The example will be more clear.
We have an integer array {7,5,9,10,1,6,13,2,8}, and by applying merge sort, we have the following sequences.

The code implemented in Java is in the below.


 import java.io.*;
 import java.util.Arrays;
 class myCode
 {
   public static void main (String[] args) throws java.lang.Exception
   {
     System.out.println("Hello Java");
     int[] input = {7,5,9,10,1,6,13,2,8};
     int[] output = mergeSort(input);
     System.out.println("sorted list:");
     for (int i=0;i<output.length;i++) {
       System.out.print(output[i] + ",");
     }
   }
   public static int[] mergeSort(int[] array) {
     int middle = array.length/2;
     if (array.length < 2) {
       return array;
     } else {
       int[] left = mergeSort(Arrays.copyOfRange(array, 0, middle));
       int[] right = mergeSort(Arrays.copyOfRange(array, middle, array.length));
       return merge(left,right);
     }
   }
   public static int[] merge(int[] a, int[] b) {
     int len = a.length + b.length;
     int[] result = new int[len];
     int i=0;
     int j=0;
     while (i<a.length || j<b.length) {
       if (j >= b.length || (i < a.length && a[i]<b[j])) {
         result[i+j] = a[i];
         i++;
       } else {
         result[i+j] = b[j];
         j++;
       }
     }
     return result;
   }
 }

Chicken McNugget Theorem

The Chicken McNugget Theorem (or Postage Stamp Problem or Frobenius Coin Problem) states that for any two relatively prime positive integers m,n, the greatest integer that cannot be written in the form am + bn for nonnegative integers a, b is mn-m-n.

For example, given two integers 4 and 7, the greatest integers that cannot be written in the form of a*4 + b*7 for nonnegative integers a,b is 4*7-4-7 = 17.

Reference: https://www.artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem

Tara's Beautiful Permutations

This problem as seen in Hackerrank.
Here is problem statement.

Tara has an array, , consisting of  integers where each integer occurs at most  times in the array.

Let's define  to be a permutation of  where  is the  element of permutation . Tara thinks a permutation is beautiful if there is no index  such that  where .

You are given  queries where each query consists of some array . For each , help Tara count the number of possible beautiful permutations of the  integers in  and print the count, modulo , on a new line.

Note: Two permutations,  and , are considered to be different if and only if there exists an index  such that  and .

Input Format

The first line contains a single integer, , denoting the number of queries. The  subsequent lines describe each query in the following form:

1. The first line contains an integer, , denoting the number of elements in array .
2. The second line contains  space-separated integers describing the respective values of  in array .

Constraints

• Each integer in  can occur at most  times.

For  of the maximum score:

• The sum of  over all queries does not exceed .

For  of the maximum score:

Output Format

For each query, print the the number of possible beautiful permutations, modulo , on a new line.

Sample Input 0

3
3
1 1 2
2
1 2
4
1 2 2 1

Sample Output 0

1
2
2

Explanation 0

We perform the following  queries:

1. Array  and there is only one good permutation: 
   
   Thus, we print the result of  on a new line.
2. Array  and there are two good permutations: 
   
   Thus, we print the result of  on a new line.
3. Array  and there are two good permutations: 
   
   For demonstration purposes, the following two permutations are invalid (i.e., not good): 
   
   Because we only want the number of good permutations, we print the result of  on a new line.

==  editorial =============================================

I spent a lot of hours to understand this problem. At first, it looks to me combinatorics problems. But, it can be solved with dynamic programming with careful observation.

In this problem, we are only care about the number of one occurrence integer, and the number of two occurrence integer, and need to figure out how they are related.

Let's take a example for this.

We have an integer array {1,2,1,2,3,4}, this array have one of one occurrence integer, and two of two occurrence integers. Let that i and j, respectively, then i = 2 and j = 2.

Our purpose is to get dp(2,2).

From {1,2,1,2,3,4}, we have two cases to reduce the size. ( there are one more case though.)

First, remove an integer that occurs once, that result in {1,2,1,2,3}. And it becomes i=1, j=2. 

How many ways exist to do this? We have 3 and 4. It is equal to the number of i, i.e., 2.

So, we have to add this case to our answer. dp(1,2)*2.

Second, remove an integer that occurs twice, that result in {2,1,2,3,4}. And it becomes i=3, j=1. Since we removed only one of two occurrence integer, here it is 1, we left single "1". This "1" becomes one occurrence integer, which is added to i.

How many ways exist to do this? We have 1 and 2. It is equal to the number of j, i.e., 2.

So, we have to add this case to our answer. dp(3,1)*2.

But, in the second case, we only remove one of two occurrence integer, we need to drill down one more step there. We have {2,1,2,3,4}, and i=3, and j=1.

Let's remove an integer that occurs once. We can remove either 3 or 4. We cannot remove "1", because it is originally an integer that occurs twice.

How many ways exist to do this? We have 3 and 4. It is equal to the number of j, i.e., 2.

The result array is {2,1,2,3} if we remove 3.

So, we have a special case to add this to the answer. dp(2,1)*2 if we are drill down one more step.

Let's summarize what we worked on so far.

dp(2,2) = 0;

dp(2,2) = dp(2,2) + dp(1,2) * 2;

dp(2,2) = dp(2,2) + dp(3,1) * 2;

dp(3,1) = 0;

dp(3,1) = dp(3,1) + dp(2,1) * 2;

These are recursive calls, and further drill down. Also, we have two states for each i and j.

Some base case:

if (i==0 && j == 0) return 0;

if (i<0 0="" div="" j="" return="">

if (dp[i][j][state] != -1) return dp[i][j][state];

Let's make a pseudo code for this.

 mod = 10^9+7;  

 int[][][] dp = new int[2000][2000][2];  

 int solve(int i, int j, int state) {  

   if (i==0 && j==0) return 0;  

   if (i<0 || j<0) return 0;  

   if (dp[i][j][state] != -1) return dp[i][j][state];  

   else {  

     int count = 0;  

     if (flag == 1) {  

      count = (count + (solve(i-1,j,0)*(i-1))%mod)%mod;  

     } else {  

      count = (count + (solve(i-1,j,0)*i)%mod)%mod;  

     }  

     count = (count + (solve(i+1,j-1)*j)%mod)%mod;  

     dp[i][j][state] = count;  

     return count;  

   }  

 }