# Count of possible permutations of a number represented as a sum of 2’s, 4’s and 6’s only

Given an integer **N**, the task is to find out the number of permutations in which N can be represented as a sum of **2**s, **4**s, and **6**s only.**Note:** The different permutations of the same combination will also be counted.**Examples:**

Input:N = 8Output:7Explanation:The possible combinations are:

2 2 2 2

4 4

4 2 2

2 2 4

2 4 2

2 6

6 2Input:N = 6Output:4

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the

Essential Maths for CP Courseat a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please referComplete Interview Preparation Course.

**Approach:** In order to solve this problem, we are using a Dynamic Programming approach:

- As the possible numbers that can be added to reach
**N**are 2, 4, and 6, they can be considered as base cases. By making use of the base cases further cases can be computed. - Let us consider a
**dp[]**array of size**N + 1**which computes and stores at every index**i**the possible ways to form a value**i**using only 2, 4, 6.

dp[2] = 1

dp[4] = 2 { 4 can be represented as 2+2, 4}

dp[6] = 4 { 6 can be represented as 2+2+2, 2+4, 4+2, 6}

dp[i] = dp[i-2]+dp[i-4] + dp[i – 6] for all even values of i in the range[8, N]

- Hence, dp[N] contains the required answer.

Below is the implementation of the above approach:

## C++

`// C++ code for above implementation` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Returns number of ways` `// to reach score n` `int` `count(` `int` `n)` `{` ` ` `// table[i] will store count` ` ` `// of solutions for value i.` ` ` `if` `(n == 2)` ` ` `return` `1;` ` ` `else` `if` `(n == 4)` ` ` `return` `2;` ` ` `else` `if` `(n == 6)` ` ` `return` `4;` ` ` `int` `table[n + 1], i;` ` ` `// Initialize all table` ` ` `// values as 0` ` ` `for` `(i = 0; i < n + 1; i++)` ` ` `table[i] = 0;` ` ` `// Base case (If given value` ` ` `// is 0, 1, 2, or 4)` ` ` `table[0] = 0;` ` ` `table[2] = 1;` ` ` `table[4] = 2;` ` ` `table[6] = 4;` ` ` `for` `(i = 8; i <= n; i = i + 2) {` ` ` `table[i] = table[i - 2]` ` ` `+ table[i - 4]` ` ` `+ table[i - 6];` ` ` `}` ` ` `return` `table[n];` `}` `// Driver Code` `int` `main(` `void` `)` `{` ` ` `int` `n = 8;` ` ` `cout << count(n);` ` ` `return` `0;` `}` |

## Java

`// Java code for above implementation` `import` `java.util.*;` `class` `GFG{` `// Returns number of ways` `// to reach score n` `static` `int` `count(` `int` `n)` `{` ` ` `// table[i] will store count` ` ` `// of solutions for value i.` ` ` `if` `(n == ` `2` `)` ` ` `return` `1` `;` ` ` `else` `if` `(n == ` `4` `)` ` ` `return` `2` `;` ` ` `else` `if` `(n == ` `6` `)` ` ` `return` `4` `;` ` ` `int` `table[] = ` `new` `int` `[n + ` `1` `];` ` ` `int` `i;` ` ` `// Initialize all table` ` ` `// values as 0` ` ` `for` `(i = ` `0` `; i < n + ` `1` `; i++)` ` ` `table[i] = ` `0` `;` ` ` `// Base case (If given value` ` ` `// is 0, 1, 2, or 4)` ` ` `table[` `0` `] = ` `0` `;` ` ` `table[` `2` `] = ` `1` `;` ` ` `table[` `4` `] = ` `2` `;` ` ` `table[` `6` `] = ` `4` `;` ` ` `for` `(i = ` `8` `; i <= n; i = i + ` `2` `)` ` ` `{` ` ` `table[i] = table[i - ` `2` `] +` ` ` `table[i - ` `4` `] +` ` ` `table[i - ` `6` `];` ` ` `}` ` ` `return` `table[n];` `}` `// Driver Code` `public` `static` `void` `main(String args[])` `{` ` ` `int` `n = ` `8` `;` ` ` `System.out.print(count(n));` `}` `}` `// This code is contributed by Akanksha_Rai` |

## Python3

`# Python3 code for above implementation` `# Returns number of ways` `# to reach score n` `def` `count(n) :` ` ` `# table[i] will store count` ` ` `# of solutions for value i.` ` ` `if` `(n ` `=` `=` `2` `) :` ` ` `return` `1` `;` ` ` `elif` `(n ` `=` `=` `4` `) :` ` ` `return` `2` `;` ` ` `elif` `(n ` `=` `=` `6` `) :` ` ` `return` `4` `;` ` ` `table ` `=` `[` `0` `] ` `*` `(n ` `+` `1` `);` ` ` `# Initialize all table` ` ` `# values as 0` ` ` `for` `i ` `in` `range` `(n ` `+` `1` `) :` ` ` `table[i] ` `=` `0` `;` ` ` `# Base case (If given value` ` ` `# is 0, 1, 2, or 4)` ` ` `table[` `0` `] ` `=` `0` `;` ` ` `table[` `2` `] ` `=` `1` `;` ` ` `table[` `4` `] ` `=` `2` `;` ` ` `table[` `6` `] ` `=` `4` `;` ` ` `for` `i ` `in` `range` `(` `8` `, n ` `+` `1` `, ` `2` `) :` ` ` `table[i] ` `=` `table[i ` `-` `2` `] ` `+` `\` ` ` `table[i ` `-` `4` `] ` `+` `\` ` ` `table[i ` `-` `6` `];` ` ` `return` `table[n];` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `n ` `=` `8` `;` ` ` `print` `(count(n));` `# This code is contributed by AnkitRai01` |

## C#

`// C# code for above implementation` `using` `System;` `class` `GFG{` `// Returns number of ways` `// to reach score n` `static` `int` `count(` `int` `n)` `{` ` ` `// table[i] will store count` ` ` `// of solutions for value i.` ` ` `if` `(n == 2)` ` ` `return` `1;` ` ` `else` `if` `(n == 4)` ` ` `return` `2;` ` ` `else` `if` `(n == 6)` ` ` `return` `4;` ` ` `int` `[]table = ` `new` `int` `[n + 1];` ` ` `int` `i;` ` ` `// Initialize all table` ` ` `// values as 0` ` ` `for` `(i = 0; i < n + 1; i++)` ` ` `table[i] = 0;` ` ` `// Base case (If given value` ` ` `// is 0, 1, 2, or 4)` ` ` `table[0] = 0;` ` ` `table[2] = 1;` ` ` `table[4] = 2;` ` ` `table[6] = 4;` ` ` `for` `(i = 8; i <= n; i = i + 2)` ` ` `{` ` ` `table[i] = table[i - 2] +` ` ` `table[i - 4] +` ` ` `table[i - 6];` ` ` `}` ` ` `return` `table[n];` `}` `// Driver Code` `public` `static` `void` `Main()` `{` ` ` `int` `n = 8;` ` ` `Console.Write(count(n));` `}` `}` `// This code is contributed by Code_Mech` |

## Javascript

`<script>` `// Javascript program to implement` `// the above approach` `// Returns number of ways` `// to reach score n` `function` `count(n)` `{` ` ` `// table[i] will store count` ` ` `// of solutions for value i.` ` ` `if` `(n == 2)` ` ` `return` `1;` ` ` `else` `if` `(n == 4)` ` ` `return` `2;` ` ` `else` `if` `(n == 6)` ` ` `return` `4;` ` ` ` ` `let table = Array.from({length: n+1}, (_, i) => 0);` ` ` `let i;` ` ` ` ` `// Initialize all table` ` ` `// values as 0` ` ` `for` `(i = 0; i < n + 1; i++)` ` ` `table[i] = 0;` ` ` ` ` `// Base case (If given value` ` ` `// is 0, 1, 2, or 4)` ` ` `table[0] = 0;` ` ` `table[2] = 1;` ` ` `table[4] = 2;` ` ` `table[6] = 4;` ` ` ` ` `for` `(i = 8; i <= n; i = i + 2)` ` ` `{` ` ` `table[i] = table[i - 2] +` ` ` `table[i - 4] +` ` ` `table[i - 6];` ` ` `}` ` ` ` ` `return` `table[n];` `}` ` ` ` ` `// Driver Code` ` ` ` ` `let n = 8;` ` ` `document.write(count(n));` ` ` ` ` `// This code is contributed by susmitakundugoaldanga.` `</script>` |

**Output:**

7

**Time Complexity:*** O(N)* **Auxiliary Space Complexity:** *O(N)*