Given a string S find the frequency of each character in the string and check whether they can be rearranged into a sequence F where F_i = F_{i-2} + F_{i-1} holds for all i \ge 3.
EXPLANATION:
Finding the frequency of each character can be done in linear time. One possible way is below
m = empty map
for each character c in S:
if c in m:
m[c] = m[c] + 1
else:
m[c] = 0
F = empty list
for each key, value in m:
append value to F
Next we can say that because F_i = F_{i-1} + F_{i-2} and F_{i-2} cannot be 0, F_i > F_{i-1} for all i \ge 3. So it makes sense to sort the array F.
Then we can check if F satisfies the given condition for all i \ge 3. If it does, then the string is dynamic otherwise it is not, right? …But hold on, there is a catch. Indeed F_i > F_{i-1} for all i \ge 3, but what about F_2? The relation between F_2 and F_1 is not specified. So it maybe that F_4 \ne F_2 + F_3 in the sorted order but F_4 = F_1 + F_3. In that case if we can simply swap F_1 and F_2 to get the required sequence and the string is dynamic.
For example: F = (1, 2, 3, 4). Here 3 = 1 + 2 but of course 4 \ne 2 + 3. If we swap 1 and 2 we will get (2, 1, 3, 4) where 3 = 2 + 1 and 4 = 1 + 3.
sort F
N = length of F
if N >= 4 and F[4] != F[2] + F[3]:
swap(F[1], F[2])
ok = True
if N >= 3:
for i in [3..N]:
if F[i] != F[i - 1] + F[i - 2]:
ok = False
if ok:
S is dynamic
else:
S is not dynamic
AUTHOR’S AND TESTER’S SOLUTION:
Author’s solution can be found here
Tester’s solution can be found here.
def dynamic_string(string):
count_list = [string.count(x) for x in set(string)]
count_list.sort()
check = 1
if len(count_list) < 3:
return 'Dynamic'
if count_list[2] != count_list[1] + count_list[0]:
count_list[0], count_list[1] = count_list[1], count_list[0]
for i in range(len(count_list)-1, 1, -1):
if count_list[i] != count_list[i-1] + count_list[i-2]:
check = 0
break
if check == 1:
return 'Dynamic'
else:
return 'Not'
output = ""
user_input = int(input())
for i in range(user_input):
to_check = input()
output += dynamic_string(to_check) + ' \n'
print(output)
I do get the Wrong Answer notification, but im really lost and stuck on what cases my code can’t handle properly. Any help or hints would be appreciated.
T = int(sys.stdin.readline().strip())
ans = []
for i in range(T):
x = sys.stdin.readline().strip()
ans.append(solve(x))
for j in range(T):
print(ans[j]) #solve(SI)
Why is this wrong. I used an extra flag variable to maintain a single occurence of True to replace the need of swapping. Which test cases does my code fail?
for t in range (int(input())):
s = list(input().strip())
r = sorted(s)
x = set(r)
a = []
flag = 0
count = 0
for n in x:
a.append(r.count(n))
val = sorted(a)
for k in range(2, len(val)):
if val[k] == val[k-1]+val[k-2]:
fib = True
if fib:
flag = 1
else:
fib = False
if fib or flag or len(x)<3:
print("Dynamic")
else:
print("Not")
#include #include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
string s;
cin>>s;
int l = s.length();
char a[l];
strcpy(a, s.c_str());
int sum[123];
for(int i=0;i<123;i++)
sum[i]=0;
for(int i=0;i<l;i++)
{
int v = (int)a[i];
sum[v]=sum[v]+1;
I think this problem can be solved using logic of AP Series.But our series will star from second element of series which is sort.Correct me if i am wrong.
please suggest were i am wrong
enter code here
#include<stdio.h>
#include<string.h>
#include<ctype.h>
char a[1000001];
int main()
{
register int i,j,k,cnt,max,sum,sum2,l,n;
int t,b[27];
float s;
scanf("%d",&t);
However, it incorrectly determines that the string “aaaabcccxxxxxxxxxxyyyyyyyyzwp” is NOT dynamic. However, the non-zero counts for this string are, in sorted order, 1 1 1 1 3 4 8 10. Clearly 1 + 3 == 4 here, so it appears this should be dynamic. Am I missing something, or is your test data simply not complete?