# Untitled

unknown

plain_text

a year ago

6.6 kB

17

Indexable

Never

^{}

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 I replied back to the above mail as I have contacted TA already and I have mentioned in my ticket also. Please read carefully about my concern and solve the issue. ANd then I got below reply. ============ Hi Sadhu, We would like to inform you that kindly use normal array to create sieve instead of ArrayList, the constraints are very tight with respect to space. ArrayList uses more space than a normal array (Read about behind the scenes implementation of ArrayList for explanation), that's why it is throwing Java heap error. 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 : -------- 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? ------------------------------------------