Given an array arr[] of N elements. The task is to find the minimum number of elements to be changed in the array such that the array contains first N Recaman’s Sequence terms. Note that Recaman terms may be present in any order in the array.
First few terms of Recaman’s Sequence are:
0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8, …..
Examples:
Input: arr[] = {44, 0, 2, 3, 9}
Output: 2
N = 5 and first 5 Recaman Numbers are 0, 1, 3, 6 and 2
44 and 9 must be replaced with 6 and 1
Hence 2 changes are required.
Input: arr[] = {0, 33, 3, 1}
Output: 1
Approach:
- Insert first N Recaman’s Sequence terms in a set.
- Traverse the array from left to right and check if array element is present in the set.
- If current element is present in the set that remove it from the set.
- Minimum changes required is the size of the final reduced set.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;int recamanGenerator(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 that returns minimum changes requiredint recamanArray(int arr[], int n){ // Set to store first n Recaman numbers unordered_set<int> s; // Generate and store // first n Recaman numbers int recaman[n]; recamanGenerator(recaman, n); // Insert first n Recaman numbers to set for (int i = 0; i < n; i++) s.insert(recaman[i]); for (int i = 0; i < n; i++) { // If current element of the array // is present in the set auto it = s.find(arr[i]); if (it != s.end()) s.erase(it); } // Return the remaining number of // elements in the set return s.size();}// Driver codeint main(){ int arr[] = { 7, 11, 20, 4, 2, 1, 8, 6 }; int n = sizeof(arr) / sizeof(arr[0]); cout << recamanArray(arr, n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{static int recamanGenerator(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; } return 0;}// Function that returns minimum changes requiredstatic int recamanArray(int arr[], int n){ // Set to store first n Recaman numbers Set<Integer> s=new HashSet<Integer>(); // Generate and store // first n Recaman numbers int recaman[]=new int[n+1]; recamanGenerator(recaman, n); // Insert first n Recaman numbers to set for (int i = 0; i < n; i++) s.add(recaman[i]); for (int i = 0; i < n; i++) { // If current element of the array // is present in the set if (s.contains(arr[i])) s.remove(arr[i]); } // Return the remaining number of // elements in the set return s.size();}// Driver codepublic static void main(String args[]){ int arr[] = { 7, 11, 20, 4, 2, 1, 8, 6 }; int n = arr.length; System.out.print( recamanArray(arr, n));}}// This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approachdef recamanGenerator(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): temp = arr[i - 1] - i j = 0 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 that returns minimum # changes requireddef recamanArray(arr, n): # Set to store first n Recaman numbers s = dict() # Generate and store # first n Recaman numbers recaman = [0 for i in range(n)] recamanGenerator(recaman, n) # Insert first n Recaman numbers to set for i in range(n): s[recaman[i]] = s.get(recaman[i], 0) + 1 for i in range(n): # If current element of the array # is present in the set if arr[i] in s.keys(): del s[arr[i]] # Return the remaining number of # elements in the set return len(s)# Driver codearr = [7, 11, 20, 4, 2, 1, 8, 6 ]n = len(arr)print(recamanArray(arr, n))# This code is contributed# by mohit kumar |
C#
// C# implementation of the approach using System;using System.Collections.Generic; class GFG { static int recamanGenerator(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; } return 0; } // Function that returns minimum changes required static int recamanArray(int []arr, int n) { // Set to store first n Recaman numbers HashSet<int> s=new HashSet<int>(); // Generate and store // first n Recaman numbers int[] recaman=new int[n+1]; recamanGenerator(recaman, n); // Insert first n Recaman numbers to set for (int i = 0; i < n; i++) s.Add(recaman[i]); for (int i = 0; i < n; i++) { // If current element of the array // is present in the set if (s.Contains(arr[i])) s.Remove(arr[i]); } // Return the remaining number of // elements in the set return s.Count; } // Driver code static void Main() { int []arr = { 7, 11, 20, 4, 2, 1, 8, 6 }; int n = arr.Length; Console.Write( recamanArray(arr, n)); } } // This code is contributed by mits |
Javascript
<script>// Javascript implementation of the approachfunction recamanGenerator(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 that returns minimum changes requiredfunction recamanArray(arr, n){ // Set to store first n Recaman numbers var s = []; // Generate and store // first n Recaman numbers var recaman = Array(n).fill(0); recamanGenerator(recaman, n); // push first n Recaman numbers to set for (var i = 0; i < n; i++) s.push(recaman[i]); s.sort((a,b)=> b-a) for (var i = 0; i < n; i++) { // If current element of the array // is present in the set if(s.includes(arr[i])) { s.splice(s.indexOf(arr[i]), 1); } } // Return the remaining number of // elements in the set return s.length;}// Driver codevar arr = [7, 11, 20, 4, 2, 1, 8, 6 ];var n = arr.length;document.write( recamanArray(arr, n));</script> |
Output:
3
Time Complexity: O(n*n)
Auxiliary Space: O(n), The space complexity of the recamanGenerator function is O(n) because it creates an array of size n to store the Recaman sequence. The space complexity of the recamanArray function is O(n) because it creates an unordered set of size n to store the first n Recaman numbers. Hence, the overall space complexity of the function is O(n).
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
