Dada una string de alfabetos en minúsculas. La tarea es verificar si la frecuencia de los alfabetos en esta string, después de organizarlos de cualquier manera posible, forma la Secuencia de Recaman (excluyendo el primer término).
Imprima «SÍ» si están en secuencia, de lo contrario, emita «NO».
Algunos términos iniciales de la Secuencia de Recaman son:
0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8….
Nota: No se considera el primer término de la Secuencia de Recaman ya que es cero.
Ejemplos:
Input : str = "dddeweecceee"
Output : YES
Frequency of 'd' => 3
Frequency of 'e' => 6
Frequency of 'w' => 1
Frequency of 'c' => 2
These frequencies form the first 4 terms of
Recaman's sequence => {1, 3, 6, 2}
Input : str = "geeksforgeeks"
Output : NO
Acercarse:
- Recorre la string y almacena la frecuencia de los caracteres en un mapa. Deje que el tamaño del mapa sea N después de almacenar la frecuencia.
- Ahora, haga una array e inserte los primeros N elementos de la secuencia de Recaman en ella.
- Ahora, recorra la array y verifique si los elementos de la array están presentes como una clave en el mapa (excluyendo la verificación de cero) .
- Si todos y cada uno de los elementos de la array están presentes en el mapa, emite «SÍ», de lo contrario, «NO».
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check whether frequency of
// characters in a string makes
// Recaman Sequence
#include <bits/stdc++.h>
using namespace std;
// Function to fill the array with first N numbers
// from Recaman's Sequence
int recaman(int arr[], int n)
{
// First term of the sequence is always 0
arr[0] = 0;
// Fill remaining terms using recursive
// formula
for (int i = 1; i <= n; i++) {
int temp = arr[i - 1] - i;
int j;
for (j = 0; j < i; j++) {
// If arr[i-1] - i is negative or
// already exists.
if ((arr[j] == temp) || temp < 0) {
temp = arr[i - 1] + i;
break;
}
}
arr[i] = temp;
}
}
// Function to check if the frequencies
// are in Recaman series
string isRecaman(string s)
{
// Store frequencies of characters
unordered_map<char, int> m;
for (int i = 0; i < s.length(); i++)
m[s[i]]++;
// Get the size of the map
int n = m.size();
int arr[n + 1];
recaman(arr, n);
int flag = 1;
// Compare vector elements with values in Map
for (auto itr = m.begin(); itr != m.end(); itr++) {
int found = 0;
for (int j = 1; j <= n; j++) {
if (itr->second == arr[j]) {
found = 1;
break;
}
}
if (found == 0) {
flag = 0;
break;
}
}
if (flag == 1)
return "YES";
else
return "NO";
}
// Driver code
int main()
{
string s = "geeekkkkkkss";
cout << isRecaman(s);
return 0;
}
Java
// Java program to check whether frequency of
// characters in a string makes Recaman Sequence
import java.util.HashMap;
import java.util.Map;
class GfG
{
// Function to fill the array with first
// N numbers from Recaman's Sequence
static void recaman(int arr[], int n)
{
// First term of the sequence is always 0
arr[0] = 0;
// Fill remaining terms using
// recursive formula
for (int i = 1; i <= n; i++)
{
int temp = arr[i - 1] - i;
for (int j = 0; j < i; j++)
{
// If arr[i-1] - i is negative or
// already exists.
if ((arr[j] == temp) || temp < 0)
{
temp = arr[i - 1] + i;
break;
}
}
arr[i] = temp;
}
}
// Function to check if the frequencies
// are in Recaman series
static String isRecaman(String s)
{
// Store frequencies of characters
HashMap <Character, Integer> m = new HashMap<>();
for (int i = 0; i < s.length(); i++)
if (m.containsKey(s.charAt(i)))
m.put(s.charAt(i), m.get(s.charAt(i))+1);
else
m.put(s.charAt(i), 1);
// Get the size of the map
int n = m.size();
int arr[] = new int[n + 1];
recaman(arr, n);
int flag = 1;
// Compare vector elements with values in Map
for (Map.Entry mapEle : m.entrySet())
{
int found = 0;
for (int j = 1; j <= n; j++)
{
if ((int)mapEle.getValue() == arr[j])
{
found = 1;
break;
}
}
if (found == 0)
{
flag = 0;
break;
}
}
if (flag == 1)
return "YES";
else
return "NO";
}
// Driver code
public static void main(String []args)
{
String s = "geeekkkkkkss";
System.out.println(isRecaman(s));
}
}
// This code is contributed by Rituraj Jain
Python3
# Python3 program to check whether # frequency of characters in a string # makes Recaman Sequence # Function to fill the array with first # N numbers from Recaman's Sequence def recaman(arr, n) : # First term of the sequence # is always 0 arr[0] = 0; # Fill remaining terms using # recursive formula for i in range(1, n + 1) : temp = arr[i - 1] - i; for j in range(i) : # If arr[i-1] - i is negative # or already exists. if ((arr[j] == temp) or temp < 0) : temp = arr[i - 1] + i; break; arr[i] = temp; # Function to check if the frequencies # are in Recaman series def isRecaman(s) : # Store frequencies of characters m = dict.fromkeys(list(s), 0); for i in range(len(s)) : m[s[i]] += 1; # Get the size of the map n = len(m); arr = [0] * (n + 1); recaman(arr, n); flag = 1; # Compare vector elements with # values in Map for keys in m.keys() : found = 0; for j in range(1, n + 1) : if (m[keys] == arr[j]) : found = 1; break; if (found == 0) : flag = 0; break; if (flag == 1) : return "YES"; else : return "NO"; # Driver code if __name__ == "__main__" : s = "geeekkkkkkss"; print(isRecaman(s)); # This code is contributed by Ryuga
C#
// C# program to check whether frequency of
// characters in a string makes Recaman Sequence
using System;
using System.Collections.Generic;
class GFG
{
// Function to fill the array with first
// N numbers from Recaman's Sequence
public static void recaman(int[] arr, int n)
{
// First term of the sequence is always 0
arr[0] = 0;
// Fill remaining terms using
// recursive formula
for (int i = 1; i <= n; i++)
{
int temp = arr[i - 1] - i;
for (int j = 0; j < i; j++)
{
// If arr[i-1] - i is negative or
// already exists.
if ((arr[j] == temp) || temp < 0)
{
temp = arr[i - 1] + i;
break;
}
}
arr[i] = temp;
}
}
// Function to check if the frequencies
// are in Recaman series
public static String isRecaman(String s)
{
// Store frequencies of characters
Dictionary<char,
int> m = new Dictionary<char,
int>();
for (int i = 0; i < s.Length; i++)
{
if (m.ContainsKey(s[i]))
m[s[i]]++;
else
m.Add(s[i], 1);
}
// Get the size of the map
int n = m.Count;
int[] arr = new int[n + 1];
recaman(arr, n);
int flag = 1;
// Compare vector elements with values in Map
foreach (KeyValuePair<char,
int> mapEle in m)
{
int found = 0;
for (int j = 1; j <= n; j++)
{
if (mapEle.Value == arr[j])
{
found = 1;
break;
}
}
if (found == 0)
{
flag = 0;
break;
}
}
if (flag == 1)
return "YES";
else
return "NO";
}
// Driver code
public static void Main(String[] args)
{
String s = "geeekkkkkkss";
Console.WriteLine(isRecaman(s));
}
}
// This code is contributed by
// sanjeev2552
Javascript
<script>
// Javascript program to check whether frequency of
// characters in a string makes
// Recaman Sequence
// Function to fill the array with first N numbers
// from Recaman's Sequence
function recaman(arr, n)
{
// First term of the sequence is always 0
arr[0] = 0;
// Fill remaining terms using recursive
// formula
for (var i = 1; i <= n; i++) {
var temp = arr[i - 1] - i;
var j;
for (j = 0; j < i; j++) {
// If arr[i-1] - i is negative or
// already exists.
if ((arr[j] == temp) || temp < 0) {
temp = arr[i - 1] + i;
break;
}
}
arr[i] = temp;
}
}
// Function to check if the frequencies
// are in Recaman series
function isRecaman(s)
{
// Store frequencies of characters
var m = new Map();
for (var i = 0; i < s.length; i++)
{
if(m.has(s[i]))
{
m.set(s[i], m.get(s[i])+1);
}
else
{
m.set(s[i], 1);
}
}
// Get the size of the map
var n = m.size;
var arr = Array(n+1).fill(0);
recaman(arr, n);
var flag = 1;
// Compare vector elements with values in Map
m.forEach((value, key) => {
var found = 0;
for (var j = 1; j <= n; j++) {
if (value == arr[j]) {
found = 1;
break;
}
}
if (found == 0) {
flag = 0;
}
});
if (flag == 1)
return "YES";
else
return "NO";
}
// Driver code
var s = "geeekkkkkkss";
document.write( isRecaman(s));
</script>
Producción:
YES
Publicación traducida automáticamente
Artículo escrito por Shashank_Sharma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA