Suppose you are given an array with N elements with any integer values. You need to find the minimum number of elements of the array which must be changed so that array has all integer values between 1 and N(including 1, N).
Examples:
Input : arr[] = {1 4 5 3 7}
Output : 1
We need to replace 7 with 2 to satisfy
condition hence minimum changes is 1.
Input : arr[] = {8 55 22 1 3 22 4 5}
Output :3
We insert all elements in a hash table. We then iterate from 1 to N and check whether the element is present in the hash table. If it is not present then increment count. The final value of count will be the minimum changes required.
Implementation:
C++
// Count minimum changes to make array// from 1 to n#include <bits/stdc++.h>using namespace std;int countChanges(int arr[], int n){ // it will contain all initial elements // of array for log(n) complexity searching unordered_set<int> s; // Inserting all elements in a hash table for (int i = 0; i < n; i++) s.insert(arr[i]); // Finding elements to be changed int count = 0; for (int i = 1; i <= n; i++) if (s.find(i) == s.end()) count++; return count;}int main(){ int arr[] = {8, 55, 22, 1, 3, 22, 4, 5}; int n = sizeof(arr)/sizeof(arr[0]); cout << countChanges(arr, n); return 0;} |
Java
// Count minimum changes to // make array from 1 to n import java.util.Set;import java.util.HashSet;class GfG{ static int countChanges(int arr[], int n) { // It will contain all initial elements // of array for log(n) complexity searching Set<Integer> s = new HashSet<>(); // Inserting all elements in a hash table for (int i = 0; i < n; i++) s.add(arr[i]); // Finding elements to be changed int count = 0; for (int i = 1; i <= n; i++) if (!s.contains(i)) count++; return count; } // Driver code public static void main(String []args) { int arr[] = {8, 55, 22, 1, 3, 22, 4, 5}; int n = arr.length; System.out.println(countChanges(arr, n)); }}// This code is contributed by Rituraj Jain |
Python 3
# Count minimum changes to # make array from 1 to ndef countChanges(arr, n): # it will contain all initial # elements of array for log(n) # complexity searching s = [] # Inserting all elements in a list for i in range(n): s.append(arr[i]) # Finding elements to be changed count = 0 for i in range(1, n + 1) : if i not in s: count += 1 return count# Driver Codeif __name__ == "__main__": arr = [8, 55, 22, 1, 3, 22, 4, 5] n = len(arr) print(countChanges(arr, n))# This code is contributed # by ChitraNayal |
C#
// C# program to Count minimum changes to // make array from 1 to n using System;using System.Collections.Generic;class GfG{ static int countChanges(int []arr, int n) { // It will contain all initial elements // of array for log(n) complexity searching HashSet<int> s = new HashSet<int>(); // Inserting all elements in a hash table for (int i = 0; i < n; i++) s.Add(arr[i]); // Finding elements to be changed int count = 0; for (int i = 1; i <= n; i++) if (!s.Contains(i)) count++; return count; } // Driver code public static void Main(String []args) { int []arr = {8, 55, 22, 1, 3, 22, 4, 5}; int n = arr.Length; Console.WriteLine(countChanges(arr, n)); }}// This code is contributed by 29AjayKumar |
PHP
<?php // Count minimum changes to // make array from 1 to nfunction countChanges(&$arr, $n){ // it will contain all initial // elements of array for log(n) // complexity searching $s = array(); // Inserting all elements // in an array for ($i = 0; $i < $n; $i++) array_push($s, $arr[$i]); // Finding elements to be changed $count = 0; for ($i = 1; $i <= $n; $i++) if (!in_array($i, $s)) $count++; return $count;}// Driver Code$arr = array(8, 55, 22, 1, 3, 22, 4, 5);$n = sizeof($arr);echo countChanges($arr, $n);// This code is contributed // by ChitraNayal?> |
Javascript
<script>// Count minimum changes to // make array from 1 to n function countChanges(arr,n) { // It will contain all initial elements // of array for log(n) complexity searching let s = new Set(); // Inserting all elements in a hash table for (let i = 0; i < n; i++) s.add(arr[i]); // Finding elements to be changed let count = 0; for (let i = 1; i <= n; i++) if (!s.has(i)) count++; return count; } // Driver code let arr=[8, 55, 22, 1, 3, 22, 4, 5]; let n = arr.length; document.write(countChanges(arr, n)); // This code is contributed by rag2127 </script> |
Output
3
Complexities Analysis:
- Time Complexity: O(n)
- Auxiliary Space: 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!
