# Total number of ways to place X and Y at n places such that no two X are together

Given N positions, the task is to count the total number of ways to place X and Y such that no two X are together. **Examples:**

Input: 3 Output: 5 XYX, YYX, YXY, XYY and YYY Input: 4 Output: 8 XYXY, XYYX, YXYX, YYYX, YYXY, YXYY, XYYY and YYYY

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

**Approach:**

For N = 1, X and Y are 2 possible ways.

For N = 2, XY, YX and YY are the 3 possible ways.

For N = 3, XYX, YYX, YXY, XYY and YYY are 5 possible ways.

For N = 4, XYXY, XYYX, YXYX, YYYX, YYXY, YXYY, XYYY and YYYY are 8 possible ways.

On solving for values of N, a Fibonacci pattern series is observed.

Below is the iterative implementation of the above approach:

## C++

`// C++ program to find the` `// number of ways Calculate` `// total ways to place 'x'` `// and 'y' at n places such` `// that no two 'x' are together` `#include <iostream>` `using` `namespace` `std;` ` ` `// Function to return` ` ` `// number of ways` ` ` `int` `ways(` `int` `n)` ` ` `{` ` ` `// for n=1` ` ` `int` `first = 2;` ` ` `// for n=2` ` ` `int` `second = 3;` ` ` `int` `res = 0;` ` ` `// iterate to find` ` ` `// Fibonacci term` ` ` `for` `(` `int` `i = 3; i <= n; i++)` ` ` `{` ` ` `res = first + second;` ` ` `first = second;` ` ` `second = res;` ` ` `}` ` ` `return` `res;` ` ` `}` `// Driver Code` `int` `main()` `{` ` ` `// total number of places` ` ` `int` `n = 7;` ` ` `cout << ` `"Total ways are : "` `;` ` ` `cout << ways(n);` ` ` `return` `0;` `}` `// This code is contributed` `// by jit_t` |

## Java

`// Java program to find the number of ways` `// Calculate total ways to place 'x' and 'y'` `// at n places such that no two 'x' are together` `public` `class` `GFG {` ` ` ` ` `// Function to return number of ways` ` ` `static` `int` `ways(` `int` `n)` ` ` `{` ` ` `// for n=1` ` ` `int` `first = ` `2` `;` ` ` `// for n=2` ` ` `int` `second = ` `3` `;` ` ` `int` `res = ` `0` `;` ` ` `// iterate to find Fibonacci term` ` ` `for` `(` `int` `i = ` `3` `; i <= n; i++) {` ` ` `res = first + second;` ` ` `first = second;` ` ` `second = res;` ` ` `}` ` ` `return` `res;` ` ` `}` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `// total number of places` ` ` `int` `n = ` `7` `;` ` ` `System.out.print(` `"Total ways are: "` `+ ways(n));` ` ` `}` `}` |

## Python3

`# Python3 program to find the` `# number of ways Calculate` `# total ways to place 'x'` `# and 'y' at n places such` `# that no two 'x' are together` `# Function to return` `# number of ways` `def` `ways(n):` ` ` ` ` `# for n=1` ` ` `first ` `=` `2` `;` ` ` `# for n=2` ` ` `second ` `=` `3` `;` ` ` `res ` `=` `0` `;` ` ` `# iterate to find` ` ` `# Fibonacci term` ` ` `for` `i ` `in` `range` `(` `3` `, n ` `+` `1` `):` ` ` `res ` `=` `first ` `+` `second;` ` ` `first ` `=` `second;` ` ` `second ` `=` `res;` ` ` `return` `res;` ` ` `# Driver Code` `# total number of places` `n ` `=` `7` `;` `print` `(` `"Total ways are: "` `,` ` ` `ways(n));` `# This code is contributed by mits` |

## C#

`// C# program to find the` `// number of ways. Calculate` `// total ways to place 'x'` `// and 'y' at n places such` `// that no two 'x' are together` `using` `System;` `class` `GFG` `{` ` ` ` ` `// Function to return` ` ` `// number of ways` ` ` `static` `int` `ways(` `int` `n)` ` ` `{` ` ` `// for n=1` ` ` `int` `first = 2;` ` ` `// for n=2` ` ` `int` `second = 3;` ` ` `int` `res = 0;` ` ` `// iterate to find` ` ` `// Fibonacci term` ` ` `for` `(` `int` `i = 3; i <= n; i++)` ` ` `{` ` ` `res = first + second;` ` ` `first = second;` ` ` `second = res;` ` ` `}` ` ` `return` `res;` ` ` `}` ` ` ` ` `// Driver Code` ` ` `static` `public` `void` `Main ()` ` ` `{` ` ` ` ` `// total number` ` ` `// of places` ` ` `int` `n = 7;` ` ` `Console.WriteLine(` `"Total ways are: "` `+` ` ` `ways(n));` ` ` `}` `}` `//This code is contributed by ajit` |

## PHP

`<?php` `// PHP program to find the` `// number of ways Calculate` `// total ways to place 'x'` `// and 'y' at n places such` `// that no two 'x' are together` `// Function to return` `// number of ways` `function` `ways(` `$n` `)` `{` ` ` `// for n=1` ` ` `$first` `= 2;` ` ` `// for n=2` ` ` `$second` `= 3;` ` ` `$res` `= 0;` ` ` `// iterate to find` ` ` `// Fibonacci term` ` ` `for` `(` `$i` `= 3; ` `$i` `<= ` `$n` `; ` `$i` `++)` ` ` `{` ` ` `$res` `= ` `$first` `+ ` `$second` `;` ` ` `$first` `= ` `$second` `;` ` ` `$second` `= ` `$res` `;` ` ` `}` ` ` `return` `$res` `;` `}` `// Driver Code` `// total number of places` `$n` `= 7;` `echo` `"Total ways are: "` `, ways(` `$n` `);` `// This code is contributed by ajit` `?>` |

## Javascript

`<script>` `// javascript program to find the number of ways` `// Calculate total ways to place 'x' and 'y'` `// at n places such that no two 'x' are together` ` ` `// Function to return number of ways` ` ` `function` `ways(n)` ` ` `{` ` ` ` ` `// for n = 1` ` ` `var` `first = 2;` ` ` `// for n = 2` ` ` `var` `second = 3;` ` ` `var` `res = 0;` ` ` `// iterate to find Fibonacci term` ` ` `for` `(i = 3; i <= n; i++)` ` ` `{` ` ` `res = first + second;` ` ` `first = second;` ` ` `second = res;` ` ` `}` ` ` `return` `res;` ` ` `}` ` ` `// total number of places` ` ` `var` `n = 7;` ` ` `document.write(` `"Total ways are: "` `+ ways(n));` `// This code is contributed by aashish1995` `</script>` |

**Output:**

Total ways are: 34

**Time Complexity:** O(N)