Given a string of lowercase alphabets. The task is to check whether the frequency of alphabets in this string, after arranging in any possible manner, forms the Recaman’s Sequence(excluding the first term).
Print “YES” if they are in sequence, otherwise output “NO”.
Few starting terms of Recaman’s Sequence are:
0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8 ….
Note: First term of Recaman’s Sequence is not considered since it is zero.
Examples:
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 = "neveropen"
Output : NO
Approach:
- Traverse the string and store the frequency of the characters in a map. Let the size of the map be N after storing the frequency.
- Now, make an array and insert first N elements of Recaman’s sequence in it.
- Now, traverse the array and check if the elements of the array are present as a key in map (excluding the check for zero).
- If each and every element of array is present in map, output “YES”, otherwise “NO”.
Below is the implementation of the above approach:
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 Sequenceint 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 seriesstring 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 codeint 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 Sequenceusing 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 Sequencefunction 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 seriesfunction 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 codevar s = "geeekkkkkkss";document.write( isRecaman(s));</script> |
Output:
YES
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
