fork download
copy 
  1. // C++ program for the above approach
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define MAXN 100001
  7.  
  8. // Function to construct array B[] that
  9. // stores MEX of array A[] excluding A[i]
  10. void constructMEX(int arr[], int N)
  11. {
  12. 	// Stores elements present in arr[]
  13. 	int hash[MAXN] = { 0 };
  14.  
  15. 	// Mark all values 1, if present
  16. 	for (int i = 0; i < N; i++) {
  17.  
  18. 		hash[arr[i]] = 1;
  19. 	}
  20.  
  21. 	// Initialize variable to store MEX
  22. 	int MexOfArr;
  23.  
  24. 	// Find MEX of arr[]
  25. 	for (int i = 1; i < MAXN; i++) {
  26. 		if (hash[i] == 0) {
  27. 			MexOfArr = i;
  28. 			break;
  29. 		}
  30. 	}
  31.  
  32. 	// Stores MEX for all indices
  33. 	int B[N];
  34.  
  35. 	// Traverse the given array
  36. 	for (int i = 0; i < N; i++) {
  37.  
  38. 		// Update MEX
  39. 		if (arr[i] < MexOfArr)
  40. 			B[i] = arr[i];
  41.  
  42. 		// MEX default
  43. 		else
  44. 			B[i] = MexOfArr;
  45. 	}
  46.  
  47. 	// Print the array B
  48. 	for (int i = 0; i < N; i++)
  49. 		cout << B[i] << ' ';
  50. }
  51.  
  52. // Driver Code
  53. int main()
  54. {
  55. 	// Given array
  56. 	int arr[] = { 0 ,1 ,3 ,0};
  57.  
  58. 	// Given size
  59. 	int N = sizeof(arr)
  60. 			/ sizeof(arr[0]);
  61.  
  62. 	// Function call
  63. 	constructMEX(arr, N);
  64. 	return 0;
  65. }
  66.  
Success #stdin #stdout 0.01s 5376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 1 2 0
https://ideone.com/ddtIId
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!