Java Code

public class Main
{
	public static void main(String[] args)
	{
		int A[] = {5, 1, 2, 3, 7, 6, 1, 9, 2, 3};
		mergeSort(0, A.length-1, A);
 
		for(int i : A)
		{
			System.out.print(i + " ");
		}
		System.out.println();
	}
 
	static void merge(int p, int q, int r, int A[])		// merge sorted arrays A[p..q]
																										// and A[q+1..r] into A[p..r]
	{
		int mergedArray[] = new int[r-p+1];
 
		int index_pq = p, index_qr = q+1, mergedArrayIndex = 0;
		while(index_pq <= q && index_qr <= r)
		{

Scratch would be a great place to start

I tried it too. I am not sure why that happens but it's likely due to dynamic memory allocation and all the overheads from function calls, error checking etc. When I wrote my own priority queue, it worked quite well. Here's the code if you are interested.

I got the correct answer for all test cases except for 7th. Anyone facing the same issue?

The swap function that you wrote doesn't work. You need to swap pointers.

Try using Cygwin.

I also hate white background. Check this.

Ok (Spoiler alert). For example, say to need to find the answer when N = 12.

If a divides b, it is written as a|b. Let c keep the string count.

Since 1|12, we add 2^1 = 2 periodic strings. c = 2.

Since 2|12, we add 2^2 = 4 periodic strings. However, we are couting strings of length 1 twice. So we subtract them. So instead we add 2^2 - 2 = 2. c = 4.

Since 3|12, we add 2^3. Again we are overcounting strings of length 1 twice so we add 2^3 - 2 = 6. c = 10.

Since 4|12, we add 2^4. However, now we are overcounting strings of length 1 and 2 twice. So we add 2^4 - 2 - 2 = 12. c = 22.

6|12 so we add 2^6. But we are overcounting strings of length 1, 2 and 3. So add 2^6 - 2 - 2 - 6 = 54. c = 76.