Fibonacci String Codechef Solution

For a string SS let the unique set of characters that occur in it one or more times be CC. Consider a permutation of the elements of CC as (c1,c2,c3…)(c1,c2,c3…). Let f(c)f(c) be the number of times cc occurs in SS.

If any such permutation of the elements of CC satisfies f(ci)=f(ci−1)+f(ci−2)f(ci)=f(ci−1)+f(ci−2) for all i≥3i≥3, the string is said to be a dynamic string.

Mr Bancroft is given the task to check if the string is dynamic, but he is busy playing with sandpaper. Would you help him in such a state?

Note that if the number of distinct characters in the string is less than 3, i.e. if |C|<3|C|<3, then the string is always dynamic.

Input:

  • First line will contain TT, number of testcases. Then the testcases follow.
  • Each testcase contains of a single line of input, a string SS.

Output:

For each testcase, output in a single line “Dynamic” if the given string is dynamic, otherwise print “Not“. (Note that the judge is case sensitive)

Constraints

  • 1≤T≤101≤T≤10
  • 1≤|S|≤1051≤|S|≤105
  • SS contains only lower case alphabets: aa, bb, …, zz

Sample Input:

3
aaaabccc
aabbcc
ppppmmnnoooopp

Sample Output:

Dynamic
Not
Dynamic

Explanation:

  • Testase 1: For the given string, C={a,b,c}C={a,b,c} and f(a)=4,f(b)=1,f(c)=3f(a)=4,f(b)=1,f(c)=3. f(a)=f(c)+f(b)f(a)=f(c)+f(b) so the permutation (b,c,a)(b,c,a) satisfies the requirement.
  • Testcase 2: Here too C={a,b,c}C={a,b,c} but no permutation satisfies the requirement of a dynamic string.
  • Testcase 3: Here C={m,n,o,p}C={m,n,o,p} and (m,n,o,p)(m,n,o,p) is a permutation that makes it a dynamic string.

Fibonacci String – CodeChef Solution in JAVA

import java.util.*;
import java.util.stream.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    
	    int numberOfInputs = Integer.valueOf(br.readLine());
	    
	    for (int i = 0; i < numberOfInputs; i++) {
	        determineDynamic(br.readLine());
	    }
	    
	    br.close();
	}
	
	private static void determineDynamic(String input) {
	    char[] charArray = input.toCharArray();
	    
	    List<Integer> numOfChars = new ArrayList<Integer>();
	    int currentAmount = 1;
	    
	    for (int k = 1; k < charArray.length; k++) {
	        if (charArray[k-1] == charArray[k]) {
	            currentAmount = currentAmount + 1;
	        }
	        else {
	            numOfChars.add(currentAmount);
	            currentAmount = 1;
	        }
	    }
	    
	    numOfChars.add(currentAmount);
	    
	    for (int j = 2; j < numOfChars.size(); j++) {
	        if (numOfChars.get(j-2) + numOfChars.get(j-1) == numOfChars.get(j) ||
	            numOfChars.get(j-2) + numOfChars.get(j) == numOfChars.get(j-1) ||
	            numOfChars.get(j) + numOfChars.get(j-1) == numOfChars.get(j-2)) {
	                continue;
	        }
	        else {
	            System.out.println("Not");
	            return;
	        }
	    }
	    
	    System.out.println("Dynamic");
	}
}

Fibonacci String – CodeChef Solution in CPP

#include <bits/stdc++.h>
using namespace std;


int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--)
	{
	    string s;
	    cin>>s;
	    int n=s.length();
	    map<char,int>m;
	    for(int i=0; i<n; i++)
	    {
	        m[s[i]]++;
	    }
	    int*arr,j=0;
	    arr=new int[m.size()];
	    for(auto it=m.begin(); it!=m.end(); it++)
	    {
	        arr[j++]=it->second;
	        
	    }
	    sort(arr,arr+j);
	    
	    if(j<3)
	    {
	        cout<<"Dynamic"<<endl;
	    }
	    else
	    {
	        int f=1;
	        if(j>3)
	        {
	            if(arr[1]+arr[2]!=arr[3])
	            {
	                swap(arr[0],arr[1]);
	            }
	            
	        }
	        for(int i=2; i<j; i++)
	        {
	            if(arr[i]!=arr[i-1]+arr[i-2])
	            {
	                f=0;
	                break;
	            }
	        }
	        if(f==1)
	        {
	            cout<<"Dynamic"<<endl;
	        }
	        else
	        {
	            cout<<"Not"<<endl;
	        }
	        
	    }
	}
	return 0;
}

Fibonacci String   -CodeChef Solution in Python

for _ in range(int(input())):
    a=input()
    b=[a.count(i) for i in set(a)]
    b.sort()
    if(len(b)<3):
        print('Dynamic')
        continue
    if(b[-3]+b[-2]!=b[-1]):
        print('Not')
        continue
    else:
        print('Dynamic')

Disclaimer: The above Problem (Fibonacci String ) is generated by CodeChef but the solution is provided by Codeworld19.This tutorial is only for Educational and Learning purpose.

Leave a Reply

Your email address will not be published. Required fields are marked *