fork download
copy 
  1. /* C++ program to find the
  2. smallest positive missing number */
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. /* Utility to swap to integers */
  7. void swap(int* a, int* b)
  8. {
  9. 	int temp;
  10. 	temp = *a;
  11. 	*a = *b;
  12. 	*b = temp;
  13. }
  14.  
  15. /* Utility function that puts all
  16. non-positive (0 and negative) numbers on left
  17. side of arr[] and return count of such numbers */
  18. int segregate(int arr[], int size)
  19. {
  20. 	int j = 0, i;
  21. 	for (i = 0; i < size; i++) {
  22. 		if (arr[i] <= 0) {
  23. 			swap(&arr[i], &arr[j]);
  24.  
  25. 			// increment count of
  26. 			// non-positive integers
  27. 			j++;
  28. 		}
  29. 	}
  30.  
  31. 	return j;
  32. }
  33.  
  34. /* Find the smallest positive missing number
  35. in an array that contains all positive integers */
  36. int findMissingPositive(int arr[], int size)
  37. {
  38. 	int i;
  39.  
  40. 	// Mark arr[i] as visited by
  41. 	// making arr[arr[i] - 1] negative.
  42. 	// Note that 1 is subtracted
  43. 	// because index start
  44. 	// from 0 and positive numbers start from 1
  45. 	for (i = 0; i < size; i++) {
  46. 		if (abs(arr[i]) - 1 < size && arr[abs(arr[i]) - 1] > 0)
  47. 			arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1];
  48.  
  49. 			cout<<arr[abs(arr[i]) - 1]<<" "<<abs(arr[i]) - 1<<endl;
  50. 	}
  51.  
  52. 	// Return the first index
  53. 	// value at which is positive
  54. 	for (i = 0; i < size; i++)
  55. 		if (arr[i] > 0)
  56.  
  57. 			// 1 is added because
  58. 			// indexes start from 0
  59. 			return i + 1;
  60.  
  61. 	return size + 1;
  62. }
  63.  
  64. /* Find the smallest positive missing
  65. number in an array that contains
  66. both positive and negative integers */
  67. int findMissing(int arr[], int size)
  68. {
  69.  
  70. 	// First separate positive
  71. 	// and negative numbers
  72. 	int shift = segregate(arr, size);
  73.  
  74. 	// Shift the array and call
  75. 	// findMissingPositive for
  76. 	// positive part
  77. 	return findMissingPositive(arr + shift,
  78. 							size - shift);
  79. }
  80.  
  81. // Driver code
  82. int main()
  83. {
  84. 	int arr[] = { 0, 10, 2, -10, -20 };
  85. 	int arr_size = sizeof(arr) / sizeof(arr[0]);
  86. 	int missing = findMissing(arr, arr_size);
  87. 	cout << "The smallest positive missing number is " << missing;
  88. 	return 0;
  89. }
  90.  
  91. // This is code is contributed by rathbhupendra
  92.  
Success #stdin #stdout 0.01s 5432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-112 9
-2 1
The smallest positive missing number is 1
https://ideone.com/bHKL2p
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!