Find the minimum number of single-digit prime numbers required whose sum will be equal to N.
Examples:
Input: 11 Output: 3 Explanation: 5 + 3 + 3. Another possibility is 3 + 3 + 3 + 2, but it is not the minimal Input: 12 Output: 2 Explanation: 7 + 5
Approach: Dynamic Programming can be used to solve the above problem. The observations are:
- There are only 4 single digit primes {2, 3, 5, 7}.
- If it is possible to make N from summing up single digit primes, then at least one of N-2, N-3, N-5 or N-7, is also reachable.
- The minimum number of single-digit prime numbers needed will be one more than the minimum number of prime digits needed to make one of {N-2, N-3, N-5, N-7}.
Using these observations, built a recurrence to solve this problem. The recurrence will be:
dp[i] = 1 + min(dp[i-2], dp[i-3], dp[i-5], dp[i-7])
For {2, 3, 5, 7}, the answer would be 1. For each other number, using Observation 3, try to find the minimum value possible, if possible.
Below is the implementation of the above approach.
C++
// CPP program to find the minimum number of single// digit prime numbers required which when summed// equals to a given number N.#include <bits/stdc++.h>using namespace std;// function to check if i-th// index is valid or notbool check(int i, int val){ if (i - val < 0) return false; return true;}// function to find the minimum number of single// digit prime numbers required which when summed up// equals to a given number N.int MinimumPrimes(int n){ int dp[n + 1]; for (int i = 1; i <= n; i++) dp[i] = 1e9; dp[0] = dp[2] = dp[3] = dp[5] = dp[7] = 1; for (int i = 1; i <= n; i++) { if (check(i, 2)) dp[i] = min(dp[i], 1 + dp[i - 2]); if (check(i, 3)) dp[i] = min(dp[i], 1 + dp[i - 3]); if (check(i, 5)) dp[i] = min(dp[i], 1 + dp[i - 5]); if (check(i, 7)) dp[i] = min(dp[i], 1 + dp[i - 7]); } // Not possible if (dp[n] == (1e9)) return -1; else return dp[n];}// Driver Codeint main(){ int n = 12; int minimal = MinimumPrimes(n); if (minimal != -1) cout << "Minimum number of single" << " digit primes required : " << minimal << endl; else cout << "Not possible"; return 0;} |
C
// C program to find the minimum number of single// digit prime numbers required which when summed// equals to a given number N.#include <stdio.h>#include <stdbool.h>int min(int a, int b){ int min = a; if(min > b) min = b; return min;}// function to check if i-th// index is valid or notbool check(int i, int val){ if (i - val < 0) return false; return true;}// function to find the minimum number of single// digit prime numbers required which when summed up// equals to a given number N.int MinimumPrimes(int n){ int dp[n + 1]; for (int i = 1; i <= n; i++) dp[i] = 1e9; dp[0] = dp[2] = dp[3] = dp[5] = dp[7] = 1; for (int i = 1; i <= n; i++) { if (check(i, 2)) dp[i] = min(dp[i], 1 + dp[i - 2]); if (check(i, 3)) dp[i] = min(dp[i], 1 + dp[i - 3]); if (check(i, 5)) dp[i] = min(dp[i], 1 + dp[i - 5]); if (check(i, 7)) dp[i] = min(dp[i], 1 + dp[i - 7]); } // Not possible if (dp[n] == (1e9)) return -1; else return dp[n];}// Driver Codeint main(){ int n = 12; int minimal = MinimumPrimes(n); if (minimal != -1) printf("Minimum number of single digit primes required : %d\n",minimal); else printf("Not possible"); return 0;}// This code is contributed by kothavvsaakash. |
Java
// Java program to find the minimum number// of single digit prime numbers required // which when summed equals to a given // number N.class Geeks { // function to check if i-th// index is valid or notstatic boolean check(int i, int val){ if (i - val < 0) return false; else return true;}// function to find the minimum number// of single digit prime numbers required// which when summed up equals to a given// number N.static double MinimumPrimes(int n){ double[] dp; dp = new double[n+1]; for (int i = 1; i <= n; i++) dp[i] = 1e9; dp[0] = dp[2] = dp[3] = dp[5] = dp[7] = 1; for (int i = 1; i <= n; i++) { if (check(i, 2)) dp[i] = Math.min(dp[i], 1 + dp[i - 2]); if (check(i, 3)) dp[i] = Math.min(dp[i], 1 + dp[i - 3]); if (check(i, 5)) dp[i] = Math.min(dp[i], 1 + dp[i - 5]); if (check(i, 7)) dp[i] = Math.min(dp[i], 1 + dp[i - 7]); } // Not possible if (dp[n] == (1e9)) return -1; else return dp[n];} // Driver Code public static void main(String args[]) { int n = 12; int minimal = (int)MinimumPrimes(n); if (minimal != -1) System.out.println("Minimum number of single "+ "digit primes required: "+minimal); else System.out.println("Not Possible"); }}// This code is contributed ankita_saini |
Python 3
# Python3 program to find the minimum number # of single digit prime numbers required # which when summed equals to a given # number N.# function to check if i-th # index is valid or not def check(i,val): if i-val<0: return False return True# function to find the minimum number of single # digit prime numbers required which when summed up # equals to a given number N.def MinimumPrimes(n): dp=[10**9]*(n+1) dp[0]=dp[2]=dp[3]=dp[5]=dp[7]=1 for i in range(1,n+1): if check(i,2): dp[i]=min(dp[i],1+dp[i-2]) if check(i,3): dp[i]=min(dp[i],1+dp[i-3]) if check(i,5): dp[i]=min(dp[i],1+dp[i-5]) if check(i,7): dp[i]=min(dp[i],1+dp[i-7]) # Not possible if dp[n]==10**9: return -1 else: return dp[n]# Driver Codeif __name__ == "__main__": n=12 minimal=MinimumPrimes(n) if minimal!=-1: print("Minimum number of single digit primes required : ",minimal) else: print("Not possible")#This code is contributed Saurabh Shukla |
C#
// C# program to find the // minimum number of single// digit prime numbers required // which when summed equals to // a given number N.using System;class GFG { // function to check if i-th// index is valid or notstatic Boolean check(int i, int val){ if (i - val < 0) return false; else return true;}// function to find the // minimum number of single // digit prime numbers // required which when summed // up equals to a given// number N.static double MinimumPrimes(int n){ double[] dp; dp = new double[n + 1]; for (int i = 1; i <= n; i++) dp[i] = 1e9; dp[0] = dp[2] = dp[3] = dp[5] = dp[7] = 1; for (int i = 1; i <= n; i++) { if (check(i, 2)) dp[i] = Math.Min(dp[i], 1 + dp[i - 2]); if (check(i, 3)) dp[i] = Math.Min(dp[i], 1 + dp[i - 3]); if (check(i, 5)) dp[i] = Math.Min(dp[i], 1 + dp[i - 5]); if (check(i, 7)) dp[i] = Math.Min(dp[i], 1 + dp[i - 7]); } // Not possible if (dp[n] == (1e9)) return -1; else return dp[n];}// Driver Codepublic static void Main(String []args){ int n = 12; int minimal = (int)MinimumPrimes(n); if (minimal != -1) Console.WriteLine("Minimum number of single " + "digit primes required: " + minimal); else Console.WriteLine("Not Possible");}}// This code is contributed // by Ankita_Saini |
PHP
<?php// PHP program to find the minimum // number of single digit prime // numbers required which when summed// equals to a given number N.// function to check if i-th// index is valid or notfunction check($i, $val){ if ($i - $val < 0) return false; return true;}// function to find the minimum // number of single digit prime // numbers required which when // summed up equals to a given// number N.function MinimumPrimes($n){ for ($i = 1; $i<= $n; $i++) $dp[$i] = 1e9; $dp[0] = $dp[2] = $dp[3] = $dp[5] = $dp[7] = 1; for ($i = 1; $i <= $n; $i++) { if (check($i, 2)) $dp[$i] = min($dp[$i], 1 + $dp[$i - 2]); if (check($i, 3)) $dp[$i] = min($dp[$i], 1 + $dp[$i - 3]); if (check($i, 5)) $dp[$i] = min($dp[$i], 1 + $dp[$i - 5]); if (check($i, 7)) $dp[$i] = min($dp[$i], 1 + $dp[$i - 7]); } // Not possible if ($dp[$n] == (1e9)) return -1; else return $dp[$n];}// Driver Code$n = 12;$minimal = MinimumPrimes($n);if ($minimal != -1){ echo("Minimum number of single " . "digit primes required :"); echo( $minimal );}else{ echo("Not possible");}// This code is contributed // by Shivi_Aggarwal?> |
Javascript
<script>// Javascript program to find the minimum // number of single digit prime // numbers required which when summed// equals to a given number N.// function to check if i-th// index is valid or notfunction check(i, val){ if (i - val < 0) return false; return true;}// function to find the minimum // number of single digit prime // numbers required which when // summed up equals to a given// number N.function MinimumPrimes(n){ let dp = new Array(n + 1) for (let i = 1; i<= n; i++) dp[i] = 1e9; dp[0] = dp[2] = dp[3] = dp[5] = dp[7] = 1; for (let i = 1; i <= n; i++) { if (check(i, 2)) dp[i] = Math.min(dp[i], 1 + dp[i - 2]); if (check(i, 3)) dp[i] = Math.min(dp[i], 1 + dp[i - 3]); if (check(i, 5)) dp[i] = Math.min(dp[i], 1 + dp[i - 5]); if (check(i, 7)) dp[i] = Math.min(dp[i], 1 + dp[i - 7]); } // Not possible if (dp[n] == (1e9)) return -1; else return dp[n];}// Driver Codelet n = 12;let minimal = MinimumPrimes(n);if (minimal != -1){ document.write("Minimum number of single " + "digit primes required :"); document.write( minimal );}else{ document.write("Not possible");}// This code is contributed // by gfgking</script> |
Output:
Minimum number of single digit primes required : 2
Time Complexity: O(N)
Space Complexity: O(N)
Note: In case of multiple queries, the dp[] array can be pre-computed and we can answer every query in O(1).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
