Minimum array elements to be changed to make Recaman’s sequence
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 required int 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 code int 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 approach import 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 required static 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 code public 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 approach def 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 required def 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 code arr = [ 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 approach function 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 required function 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 code var arr = [7, 11, 20, 4, 2, 1, 8, 6 ]; var n = arr.length; document.write( recamanArray(arr, n)); </script> |
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).
Contact Us