Skip to main content

Find Loveable strings containing permutations of ANU


Anubhav has a crush on Anu. Therefore he likes the letters A,N and U the most.

He likes those strings which consists of only A N U

According to him, the strings containing A,N and U only are "LOVABLE" If they contain either of these patterns:


1) ANU


2) AUN


3) NAU


4) NUA


5) UAN


6) UNA


He asks you to find out how many LOVABLE strings are there of length N.


Note: Assume all strings are made of A,N,U. Consider all other alphabets as non-existent.


Input format: First line contains T the number of test cases. Next T lines contain a single integer N, denoting the length of string


Output format: Output the count of LOVABLE strings of length N in a single line for each test case


Constraints:


1<= T <= 30


1<= N <= 30

Solution : 

// Online C++ compiler to run C++ program online
#include<bits/stdc++.h>
using namespace std;
class Solution{
   
    int a = 1;
    int n1 = 7;
    int u = 3;
    public :
    int solve(int n , int pre , int pre_pre , int sum , bool x  )
    {  
        if(n ==0)
        {
            if(x)
            return 1;
            return 0;
        }
        long long result =0;
        if(sum == a + pre + pre_pre )
        {
            result += solve(n-1 , a , pre , sum , true );
        }
        else
        result += solve(n-1 , a , pre , sum , x);
       
        if(sum == n1 + pre + pre_pre )
        {
            result += solve(n-1 , n1 , pre , sum , true );
        }
        else
        result += solve(n-1 , n1 , pre , sum , x);
       
        if(sum == u + pre + pre_pre )
        {
            result += solve(n-1 , u , pre , sum , true );
        }
        else
        result += solve(n-1 , u , pre , sum , x);
       
        return result;
       
       
       
       
    }
    int Loveable(int  n )
    {
        if(n == 0 || n==1 || n==2)
        {
            return 0;
        }
        return solve(n , -1 , -1 , 11 , false);
       
       
    }
};


int main() {
    
    Solution s ;
     int n = 4;
     int x = s.Loveable(n);
     cout << x << " "<<"\n";
}


The dynamic programming solution will be uploaded soon, Stay tuned.
Labels:

Comments

Post a Comment

Popular posts from this blog

[PDF DOWNLOAD] AKTU Quantum series data structure b.tech 2nd year download

  All AKTU Quantums are available here. Get your hands on AKTU Quantums and boost your grades in AKTU semester exams. You can either search them category wise or can use the search bar or can manually search on this page. Download aktu second year quantum pdf data structures  download  data structures quantum aktu download aktu data structures quantum click here to download  write in comment section if you want quantum of any other subject.
Post a Comment
Read more

2485. Find the Pivot Integer | Binary search

  Given a positive integer   n , find the   pivot integer   x   such that: The sum of all elements between  1  and  x  inclusively equals the sum of all elements between  x  and  n  inclusively. Return  the pivot integer  x . If no such integer exists, return  -1 . It is guaranteed that there will be at most one pivot index for the given input.   Example 1: Input: n = 8 Output: 6 Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21. Example 2: Input: n = 1 Output: 1 Explanation: 1 is the pivot integer since: 1 = 1. Example 3: Input: n = 4 Output: -1 Explanation: It can be proved that no such integer exist.   Constraints: 1 <= n <= 1000 Solution : class Solution { publ ic:     int pivotInteger( int n ) {         int sum = (( n )*( n + 1 ))/ 2 ;         int i = 1 ;         int j =...
Post a Comment
Read more

leetcode 48 solution

  48 .  Rotate Image You are given an  n x n  2D  matrix  representing an image, rotate the image by  90  degrees (clockwise). You have to rotate the image  in-place , which means you have to modify the input 2D matrix directly.  DO NOT  allocate another 2D matrix and do the rotation.   Example 1: Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]] Example 2: Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]   Constraints: n == matrix.length == matrix[i].length 1 <= n <= 20 -1000 <= matrix[i][j] <= 1000 solution: class Solution { public:     void swap(int& a , int &b)     {         int c ;         c = a;         a = b;         b = c;     }     void transpose (vector<vector<int>...
Post a Comment
Read more