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 YYYInput: 4
Output: 8
XYXY, XYYX, YXYX, YYYX, YYXY, YXYY, XYYY and YYYY
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)
Auxiliary Space: O(1)
Contact Us