Given an array arr[] of N integer elements, the task is to change the minimum number of elements of this array such that it contains first N terms of the Catalan Sequence. Thus, find the minimum changes required.
First few Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …..
Examples:
Input: arr[] = {4, 1, 2, 33, 213, 5}
Output: 3
We have to replace 4, 33, 213 with 1, 14, 42 to make first 6 terms of Catalan sequence.
Input: arr[] = {1, 1, 2, 5, 41}
Output: 1
Simply change 41 with 14
Approach:
- Take an unordered multiset. Insert first N terms of Catalan sequence in this multiset.
- Traverse the array from left to right. Check if the array element if present in the multiset. If it is present, then remove that element from the multiset.
- After traversing the array, the minimum changes required will be equal to the size of the multiset.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define MAX 100000#define ll long long int// To store first N Catalan numbersll catalan[MAX];// Function to find first n Catalan numbersvoid catalanDP(ll n){ // Initialize first two values in table catalan[0] = catalan[1] = 1; // Fill entries in catalan[] using recursive formula for (int i = 2; i <= n; i++) { catalan[i] = 0; for (int j = 0; j < i; j++) catalan[i] += catalan[j] * catalan[i - j - 1]; }}// Function to return the minimum changes requiredint CatalanSequence(int arr[], int n){ // Find first n Catalan Numbers catalanDP(n); unordered_multiset<int> s; // a and b are first two // Catalan Sequence numbers int a = 1, b = 1; int c; // Insert first n catalan elements to set s.insert(a); if (n >= 2) s.insert(b); for (int i = 2; i < n; i++) { s.insert(catalan[i]); } unordered_multiset<int>::iterator it; for (int i = 0; i < n; i++) { // If catalan element is present // in the array then remove it from set 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[] = { 1, 1, 2, 5, 41 }; int n = sizeof(arr) / sizeof(arr[0]); cout << CatalanSequence(arr, n); return 0;} |
Java
import java.util.HashSet;// Java implementation of the approach class GFG1 { static int MAX = 100000; // To store first N Catalan numbers static long catalan[] = new long[MAX]; // Function to find first n Catalan numbers static void catalanDP(long n) { // Initialize first two values in table catalan[0] = catalan[1] = 1; // Filong entries in catalan[] // using recursive formula for (int i = 2; i <= n; i++) { catalan[i] = 0; for (int j = 0; j < i; j++) { catalan[i] += catalan[j] * catalan[i - j - 1]; } } } // Function to return the minimum changes required static int CatalanSequence(int arr[], int n) { // Find first n Catalan Numbers catalanDP(n); HashSet<Integer> s = new HashSet<Integer>(); // a and b are first two // Catalan Sequence numbers int a = 1, b = 1; int c; // Insert first n catalan elements to set s.add(a); if (n >= 2) { s.add(b); } for (int i = 2; i < n; i++) { s.add((int) catalan[i]); } for (int i = 0; i < n; i++) { // If catalan element is present // in the array then remove it from 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[] = {1, 1, 2, 5, 41}; int n = arr.length; System.out.print(CatalanSequence(arr, n)); }} // This code contributed by Rajput-Ji |
Python3
# Python3 implementation of# the approach MAX = 100000; # To store first N Catalan numbers catalan = [0] * MAX; # Function to find first n # Catalan numbers def catalanDP(n) : # Initialize first two values # in table catalan[0] = catalan[1] = 1; # Fill entries in catalan[] # using recursive formula for i in range(2, n + 1) : catalan[i] = 0; for j in range(i) : catalan[i] += (catalan[j] * catalan[i - j - 1]); # Function to return the minimum # changes required def CatalanSequence(arr, n) : # Find first n Catalan Numbers catalanDP(n); s = set(); # a and b are first two # Catalan Sequence numbers a = 1 ; b = 1; # Insert first n catalan # elements to set s.add(a); if (n >= 2) : s.add(b); for i in range(2, n) : s.add(catalan[i]); temp = set() for i in range(n) : # If catalan element is present # in the array then remove it # from set if arr[i] in s : temp.add(arr[i]) s = s - temp ; # Return the remaining number # of elements in the set return len(s); # Driver code if __name__ == "__main__" : arr = [1, 1, 2, 5, 41]; n = len(arr) print(CatalanSequence(arr, n)); # This code is contributed by Ryuga |
C#
// C# implementation of the approach using System;using System.Collections.Generic;class GFG1 { static int MAX = 100000; // To store first N Catalan numbers static long[] catalan = new long[MAX]; // Function to find first n Catalan numbers static void catalanDP(long n) { // Initialize first two values in table catalan[0] = catalan[1] = 1; // Filong entries in catalan[] // using recursive formula for (int i = 2; i <= n; i++) { catalan[i] = 0; for (int j = 0; j < i; j++) { catalan[i] += catalan[j] * catalan[i - j - 1]; } } } // Function to return the minimum changes required static int CatalanSequence(int []arr, int n) { // Find first n Catalan Numbers catalanDP(n); HashSet<int> s = new HashSet<int>(); // a and b are first two // Catalan Sequence numbers int a = 1, b = 1; // Insert first n catalan elements to set s.Add(a); if (n >= 2) { s.Add(b); } for (int i = 2; i < n; i++) { s.Add((int)catalan[i]); } for (int i = 0; i < n; i++) { // If catalan element is present // in the array then remove it from set if (s.Contains(arr[i])) { s.Remove(arr[i]); } } // Return the remaining number of // elements in the set return s.Count; } // Driver code public static void Main() { int []arr = {1, 1, 2, 5, 41}; int n = arr.Length; Console.WriteLine(CatalanSequence(arr, n)); }} // This code contributed by mits |
PHP
<?php// PHP implementation of the approach $MAX = 1000;// To store first N Catalan numbers $catalan = array_fill(0, $MAX, 0);// Function to find first n Catalan numbers function catalanDP($n) { global $catalan; // Initialize first two values in table $catalan[0] = $catalan[1] = 1; // Filong entries in catalan[] // using recursive formula for ($i = 2; $i <= $n; $i++) { $catalan[$i] = 0; for ($j = 0; $j < $i; $j++) { $catalan[$i] += $catalan[$j] * $catalan[$i - $j - 1]; } }}// Function to return the minimum // changes required function CatalanSequence($arr, $n) { global $catalan; // Find first n Catalan Numbers catalanDP($n); $s = array(); // a and b are first two // Catalan Sequence numbers $a = $b = 1; // Insert first n catalan elements to set array_push($s, $a); if ($n >= 2) { array_push($s, $b); } for ($i = 2; $i < $n; $i++) { array_push($s, $catalan[$i]); } $s = array_unique($s); for ($i = 0; $i < $n; $i++) { // If catalan element is present // in the array then remove it from set if (in_array($arr[$i], $s)) { unset($s[array_search($arr[$i], $s)]); } } // Return the remaining number of // elements in the set return count($s);}// Driver code $arr = array(1, 1, 2, 5, 41);$n = count($arr);print(CatalanSequence($arr, $n));// This code contributed by mits?> |
Javascript
<script>// Javascript implementation of the approachvar MAX = 100000// To store first N Catalan numbersvar catalan = Array(MAX);// Function to find first n Catalan numbersfunction catalanDP(n){ // Initialize first two values in table catalan[0] = catalan[1] = 1; // Fill entries in catalan[] using recursive formula for (var i = 2; i <= n; i++) { catalan[i] = 0; for (var j = 0; j < i; j++) catalan[i] += catalan[j] * catalan[i - j - 1]; }}// Function to return the minimum changes requiredfunction CatalanSequence(arr, n){ // Find first n Catalan Numbers catalanDP(n); var s = []; // a and b are first two // Catalan Sequence numbers var a = 1, b = 1; var c; // push first n catalan elements to set s.push(a); if (n >= 2) s.push(b); for (var i = 2; i < n; i++) { s.push(catalan[i]); } s.sort((a,b)=>b-a); for(var i =0; i<n; i++) { // If catalan element is present // in the array then remove it from set if(s.includes(arr[i])) { s.pop(arr[i]); } } // Return the remaining number of // elements in the set return s.length;}// Driver codevar arr = [1, 1, 2, 5, 41 ];var n = arr.length;document.write( CatalanSequence(arr, n));</script> |
Output:
1
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!
