Given an array with N distinct elements. The task is to find the minimum number of elements to be changed in the array such that, the array contains first N Lucas Sequence terms. Lucas terms may be present in any order in the array.
Examples:
Input: arr[] = {29, 1, 3, 4, 5, 11, 18, 2}
Output: 1
Explanation: 5 must be changed to 7, to get first N(8) terms of Lucas Sequence. Hence, 1 change is requiredInput: arr[] = {4, 2, 3, 1}
Output: 0
Explanation: All elements are already first N(4) terms in Lucas sequence.
Approach:
- Insert first N(size of input array) Lucas Sequence terms in a set.
- Traverse array from left to right and check if array element is present in the set.
- If it is present that remove it from the set.
- Minimum changes required is the size of the final remaining set.
Below is the implementation of the above approach:
C++
// C++ program to find the minimum number// of elements to be changed in the array// to make it a Lucas Sequence#include <bits/stdc++.h>using namespace std;// Function that finds minimum changes to// be made in the arrayint lucasArray(int arr[], int N){ set<int> s; // a and b are first two // lucas numbers int a = 2, b = 1; int c; // insert first n lucas elements to set s.insert(a); if (N >= 2) s.insert(b); for (int i = 0; i < N - 2; i++) { s.insert(a + b); c = a + b; a = b; b = c; } set<int>::iterator it; for (int i = 0; i < N; i++) { // if lucas element is present in array, // 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[] = { 7, 11, 22, 4, 2, 1, 8, 9 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call cout << lucasArray(arr, N); return 0;} |
Java
// Java program to find the minimum number// of elements to be changed in the array// to make it a Lucas Sequenceimport java.util.HashSet;import java.util.Set;class GfG { // Function that finds minimum changes // to be made in the array static int lucasArray(int arr[], int n) { HashSet<Integer> s = new HashSet<>(); // a and b are first two lucas numbers int a = 2, b = 1, c; // insert first n lucas elements to set s.add(a); if (n >= 2) s.add(b); for (int i = 0; i < n - 2; i++) { s.add(a + b); c = a + b; a = b; b = c; } for (int i = 0; i < n; i++) { // if lucas element is present in array, // 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[] = { 7, 11, 22, 4, 2, 1, 8, 9 }; int n = arr.length; System.out.println(lucasArray(arr, n)); }}// This code is contributed by Rituraj Jain |
Python3
# Python 3 program to find the minimum number# of elements to be changed in the array# to make it a Lucas Sequence# Function that finds minimum changes to# be made in the arraydef lucasArray(arr, n): s = set() # a and b are first two # lucas numbers a = 2 b = 1 # insert first n lucas elements to set s.add(a) if (n >= 2): s.add(b) for i in range(n - 2): s.add(a + b) c = a + b a = b b = c for i in range(n): # if lucas element is present in array, # remove it from set if (arr[i] in s): s.remove(arr[i]) # return the remaining number of # elements in the set return len(s)# Driver codeif __name__ == '__main__': arr = [7, 11, 22, 4, 2, 1, 8, 9] n = len(arr) print(lucasArray(arr, n))# This code is contributed by# Surendra_Gangwar |
C#
// C# program to find the minimum number// of elements to be changed in the array// to make it a Lucas Sequenceusing System;using System.Collections.Generic;class GFG { // Function that finds minimum changes // to be made in the array static int lucasArray(int[] arr, int n) { HashSet<int> s = new HashSet<int>(); // a and b are first two lucas numbers int a = 2, b = 1, c; // insert first n lucas elements to set s.Add(a); if (n >= 2) s.Add(b); for (int i = 0; i < n - 2; i++) { s.Add(a + b); c = a + b; a = b; b = c; } for (int i = 0; i < n; i++) { // if lucas element is present in array, // 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(String[] args) { int[] arr = { 7, 11, 22, 4, 2, 1, 8, 9 }; int n = arr.Length; Console.WriteLine(lucasArray(arr, n)); }}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript program to find the minimum number// of elements to be changed in the array// to make it a Lucas Sequence// Function that finds minimum changes to// be made in the arrayfunction lucasArray(arr, n){ var s = new Set(); // a and b are first two // lucas numbers var a = 2, b = 1; var c; // insert first n lucas elements to set s.add(a); if (n >= 2) s.add(b); for (var i = 0; i < n - 2; i++) { s.add(a + b); c = a + b; a = b; b = c; } for (var i = 0; i < n; i++) { // if lucas element is present in array, // remove it from set s.delete(arr[i]) } // return the remaining number of // elements in the set return s.size;}// Driver codevar arr = [7, 11, 22, 4, 2, 1, 8, 9 ];var n = arr.length;document.write( lucasArray(arr, n));</script> |
Output
3
Complexity Analysis:
- Time Complexity: O(N * log(N))
- Auxiliary Space: O(N)
Share your thoughts in the comments
