Prime And Validity

Hard
0/120
Average time to solve is 30m
profile
Contributed by
8 upvotes
Asked in company
Goldman Sachs

Problem statement

A prime number is a number that has only two factors, 1 and the number itself. Ninja came across a problem in which he has a number ‘N’, and Ninja has to find whether ‘N’ can be formed with the sum of ‘K’ prime numbers.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains 2 space-separated integers, representing the integers ‘N’ and ‘K’.
Output Format : 
For each test case, print the 1, if the number can be formed with the sum of ‘K’ prime numbers, else print 0.

Print the output of each test case in a separate line.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N, K <= 3*10^3

Time Limit: 1 sec
Sample Input 1 :
2
10 2
2 2
Sample Output 1 :
1
0
Explanation For Sample Input 1 :
For the first test case :

10 can be formed by sum 5 two times.

For the second test :

We have no prime number smaller than 2 and thus 2 can not be formed by the sum of 2 prime numbers.
Sample Input 2 :
2
10 3
7 3
Sample Output 2 :
1
1
Hint

Try to find all the possibilities of forming a sum.

Approaches (2)
Brute Force

The basic idea is to check for all the possible combinations of forming ‘N’ by the sum of ‘K’ prime numbers.

 

Here is the algorithm :

 

  1. Base case
    • If ‘N’ is smaller than equal to 0, return 0.
  2. If ‘K’ is equal to 1, check if ‘N’ is a prime number or not.
  3. Run a loop from 2 to ‘N’ (say, iterator ‘i’), that can be used for forming ‘N’.
    • Check if ‘i’ is a prime number.
      • Call the function recursively by updating ‘N’ by ‘N’ - ‘i’ and ‘K’ by ‘K’ - 1 and check if the value returned by the recursive function is 1, return 1.
  4. Finally, return 0.

 

isPrime(N)
 

  1. Run a loop from 2 to square root of ‘N’ (say, iterator ‘i’)
  2. Check if the ‘N’ is divisible by i
    • Return FALSE.
  3. Return TRUE.
Time Complexity

O(N^(N*sqrt(N))), where ‘N’ is the given number.

 

We run a loop from 2 to ‘N’ and for each ‘N’ we check whether that number is prime or not which takes sqrt of time. We call a recursive function to count the prime numbers in range 1 to ‘N’ which can not be more than ‘N’. Therefore, the overall time complexity will be O(N^(N*sqrt(N))).

Space Complexity

O(N), where ‘N’ is the given number.

 

The recursion stack can contain the count of prime numbers in range 1 to ‘N’ which cannot be more than ‘N’. Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Prime And Validity
Full screen
Console