## Thursday, November 26, 2015

### Count number of ways to divide a number in 4 parts - GeeksforGeeks

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;`
`}`
Read full article from Count number of ways to divide a number in 4 parts - GeeksforGeeks