Untitled

Issue :  Advanced DSA : Maths 3: Prime Numbers  : HomeWork Question 1
--------

Q1. Prime Sum

Problem Description
Given an even number A ( greater than 2 ), return two prime numbers whose sum will be equal to the given number.

If there is more than one solution possible, return the lexicographically smaller solution.

If [a, b] is one solution with a <= b, and [c,d] is another solution with c <= d, then 
[a, b] < [c, d], If a < c OR a==c AND b < d. 
NOTE: A solution will always exist. Read Goldbach's conjecture.

Problem Constraints
4 <= A <= 2*107

Input Format
First and only argument of input is an even number A.

Output Format
Return a integer array of size 2 containing primes whose sum will be equal to given number.

Example Input
 4

Example Output
 [2, 2]


Example Explanation
 There is only 1 solution for A = 4.

------------------------------------------

// This below solution is throwing error. 
// Error pasted below the solution
// It is throwing error at Line Number 66 below
public class Solution {
    public ArrayList<Integer> primesum(int A) {
        ArrayList<Boolean> s = seive(A);

		ArrayList<Integer> output = new ArrayList<Integer>();

		for (int i = 2; i <= A; i++) {
			if (true == s.get(i) && s.get(A - i) == true) {

				output.add(i);
				output.add(A - i);

				return output;

			}
		}

		return output;
	}

	public static ArrayList<Boolean> seive(int A) {
		ArrayList<Boolean> s = new ArrayList<Boolean>();

		s.add(false);
		s.add(false);

		for (int i = 2; i <= A; i++) {
			s.add(true);
		}

		for (int i = 2; i <= A; i++) {

			if (s.get(i) == false) {
				continue;
			}

			if (i > A / i) {
				break;
			}

			for (int j = i * i; j <= A; j = j + i) {
				s.set(j, false);
			}

		}
		return s;
	}

}



Error Pasted :-
-------------------

Compiling your Code...
> Success!
Running Test Cases...
> TestCase - Easy Failed
Runtime Error
Your submission stopped because of a runtime error,ex: division by zero, array index out of bounds, uncaught exception. You can try testing your code with custom input and try putting debug statements in your code.
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at java.util.Arrays.copyOf(Arrays.java:3210)
	at java.util.Arrays.copyOf(Arrays.java:3181)
	at java.util.ArrayList.grow(ArrayList.java:267)
	at java.util.ArrayList.ensureExplicitCapacity(ArrayList.java:241)
	at java.util.ArrayList.ensureCapacityInternal(ArrayList.java:233)
	at java.util.ArrayList.add(ArrayList.java:464)
	at Solution.seive(Solution.java:28) -- It is pointing to Line number 66
	at Solution.primesum(Solution.java:3)
	at Main.main(Main.java:329)
Your submission failed for the following input
Arg 1: A single Integer, For e.g 9
16777214
Arg 2: An Integer Array, For e.g [1,2,3]
[]
Test As Custom Input
The expected return value:
31 16777183 
Final Verdict
> Wrong Answer


------------------------------------------------------
I have contacted TA for help. The TA said there is no problem with the code, It may be problem with Platform, Raise a Ticket with the issue.

So, as TA said I have raised the Ticket.  https://support.scaler.com/hc/en-us/requests/78784

In the ticket I have mentioned that ( I have connected with the instructor and he says My code perfectly alright. There is something issue with the platform.)

But Suprisingly I got reply like  below. It says, I have to contact TA for help.

============
Hi Sadhu,
 
We would like to inform you that kindly raise a TA help request and they will be able to help you with the assignment problem.
 
We hope this was helpful.
 
Please let us know if your issue is resolved or if you have any other questions by replying to this email in the next 24 hrs.
 
We wish you a great day ahead.
 
Regards,
Team Scaler.
============

So, Please look into my code, If it is not correct please suggest me where I did wrong. 
If my code is correct what should I do ? I mean how to complete this problem in my homework?


-----------------------------------------------------------------------------------------------------------------------------------------------------------

Doubt 1: 
--------

What is the Time Complexity for Math.sqrt(A)


Doubt 2: 
--------
Q3. Very Large Power
Problem Description
Given two Integers A, B. You have to calculate (A ^ (B!)) % (1e9 + 7).

"^" means power,

"%" means "mod", and

"!" means factorial.



Problem Constraints
1 <= A, B <= 5e5



Input Format
First argument is the integer A

Second argument is the integer B



Output Format
Return one integer, the answer to the problem



Example Input
Input 1:

A = 1
B = 1
Input 2:

A = 2
B = 2


Example Output
Output 1:

1
Output 2:

4


Example Explanation
Explanation 1:

 1! = 1. Hence 1^1 = 1.
Explanation 2:

 2! = 2. Hence 2^2 = 4.
 
--------------------------

public class Solution {
    public int solve(int A, int B) {
        int mod = (int) 1e9 + 7;

		int fact = factorial(B);

		int power = power(A, fact, mod);

		return (int) ((int) power % (int) mod);
	}

	private static int power(int A, int fact, int mod) {
		if (fact == 1) {
			return A % mod;
		}

		long pow = power(A, fact / 2, mod);

		if ((fact & 1) == 1) {
			return (int) (((A % mod) * ((pow * pow) % mod)) % mod);
		} else {
			return (int) ((pow * pow) % mod);
		}
	}

	public static int factorial(int B) {
		int mod = (int) 1e9 + 6;   // (mod-1) is used accoring to Fermat Little theorem.
		if (B <= 1) {
			return 1;
		}

		long f = factorial(B - 1);

		return (int) ((f * B) % mod);
	}
}
 
Can you explain  Fermat Little theorem?


 
 ------------------------------------------