Count number of ways to divide a number in 4 parts - GeeksforGeeks
Given a positive integer n, find number of ways to divide n in four parts or represent n as sum of four positive integers. Here n varies from 0 to 5000.
http://code.geeksforgeeks.org/Hka4ud
public static void main(String args[]){
int n= 8;
int result=count(n,4);
System.out.println(result);
}
static int max(int a, int b){
int max=a>b?a:b;
return max;
}
public static int count(int n,int k){
int arr[][]=new int[n+1][k+1];
arr[0][0]=1;
for(int j=1;j<=k;j++){
for(int i=1;i<=n;i++){
if(!((j>i)||(i>0 && j==0))){
arr[i][j]+=arr[i-j][j]+arr[i-1][j-1];
}
}
}
return arr[n][k];
}
Method 3 (A O(n2 Log n) Solution)
We can use the solution discussed in this post to find all quadruplets.
Brute Force - N^4
Read full article from Count number of ways to divide a number in 4 parts - GeeksforGeeks
Given a positive integer n, find number of ways to divide n in four parts or represent n as sum of four positive integers. Here n varies from 0 to 5000.
countWays(n, parts, nextPart) = ∑countWays(n, parts, i)
nextPart <= i <= n
n --> Input number
parts --> Count of parts of n. Initially parts = 4
nextPart --> Starting point for next part to be tried
We try for all values from nextPart to n.
We initially call the function as countWays(n, 4, 1)
Time complexity of this solution is O(n3). There are Θ(n2) entries, every entry is filled only once and filling an entry takes O(n) time.
// "parts" is number of parts left, n is the value left// "nextPart" is starting point from where we start trying// for next part.int countWaysUtil(int n, int parts, int nextPart){ // Base cases if (parts == 0 && n == 0) return 1; if (n <= 0 || parts <= 0) return 0; // If this subproblem is already solved if (dp[n][nextPart][parts] != -1) return dp[n][nextPart][parts]; int ans = 0; // Initialize result // Count number of ways for remaining number n-i // remaining parts "parts-1", and for all part // varying from 'nextPart' to 'n' for (int i = nextPart; i <= n; i++) ans += countWaysUtil(n-i, parts-1, i); // Store computed answer in table and return // result return (dp[n][nextPart][parts] = ans);}http://code.geeksforgeeks.org/Hka4ud
public static void main(String args[]){
int n= 8;
int result=count(n,4);
System.out.println(result);
}
static int max(int a, int b){
int max=a>b?a:b;
return max;
}
public static int count(int n,int k){
int arr[][]=new int[n+1][k+1];
arr[0][0]=1;
for(int j=1;j<=k;j++){
for(int i=1;i<=n;i++){
if(!((j>i)||(i>0 && j==0))){
arr[i][j]+=arr[i-j][j]+arr[i-1][j-1];
}
}
}
return arr[n][k];
}
Method 3 (A O(n2 Log n) Solution)
We can use the solution discussed in this post to find all quadruplets.
Brute Force - N^4
int countWays(int n){ int counter = 0; // Initialize result // Generate all possible quadruplet and increment // counter when sum of a quadruplet is equal to n for (int i = 1; i < n; i++) for (int j = i; j < n; j++) for (int k = j; k < n; k++) for (int l = k; l < n; l++) if (i + j + k + l == n) counter++; return counter;}