dmilicev

smallest positive integer that does not occur.c

Nov 21st, 2021 (edited)
377
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  
  3.     smallest positive integer that does not occur.c
  4.  
  5.     Version with array sort using the qsort() function.
  6.  
  7.     Task:
  8.     https://www.facebook.com/groups/cprogramming123/permalink/4468570053231257/
  9.  
  10.  
  11.     You can find all my C programs at Dragan Milicev's pastebin:
  12.  
  13.     https://pastebin.com/u/dmilicev
  14.  
  15. */
  16.  
  17. #include <stdio.h>
  18. #include <stdlib.h>
  19.  
  20. // Function to print array arr of n integers
  21. void PrintArray(char text[],int arr[],int n){
  22.     int i;
  23.  
  24.     printf("%s",text);
  25.     for(i=0;i<n;i++)
  26.         printf("%5d", arr[i]);
  27.  
  28.     printf("\n\n");
  29. }
  30.  
  31. //comparing function for quick sort
  32. int cmpfunc (const void *a, const void *b) {
  33.    return ( *(int*)a - *(int*)b );
  34. }
  35.  
  36. int solution( int arr[], int n){
  37.     int i, num=0, max=0;
  38.  
  39.     for(i=0; i<n; i++){
  40.         while(arr[i]<=0 && i<n-1){  // skip no positive values
  41.             printf("\n skipped i=%2d   arr[%d]= %2d   arr[%d]= %2d   max = %d \n", i, i, arr[i], i+1, arr[i+1], max);
  42.             i++;
  43.         }
  44.  
  45.         if( i<n && max<arr[i] )     // find current max integer
  46.             max=arr[i];
  47.  
  48.         if ( i<n-1 ){
  49.             printf("\n         i=%2d   arr[%d]= %2d   arr[%d]= %2d   max = %d \n", i, i, arr[i], i+1, arr[i+1], max);
  50.  
  51.             if( i<n-1 && arr[i+1]-arr[i]>1 ){
  52.                 num=max+1;
  53.                 break;
  54.             }
  55.         }
  56.     }
  57.  
  58.     if( num<=0 )
  59.         num=max+1;
  60.  
  61.     return num;
  62. }
  63.  
  64.  
  65. int main(){
  66.     int arr[] = {1,3,6,4,1,2};
  67. //    int arr[] = {1, 2, 3};
  68. //    int arr[] = {-1, -3};
  69. //    int arr[] = {-1, 2, -3};
  70. //    int arr[] = {-1, 4, -3, 2};
  71. //    int arr[] = {-1, 2, -3, 4};
  72. //    int arr[] = {0, 0, 0, 0};
  73.     int n=sizeof(arr)/sizeof(arr[0]);
  74.  
  75.     printf("\n n = %d \n", n);
  76.  
  77.     PrintArray("\n        arr = ", arr, n);
  78.  
  79.     qsort( (void*)arr, n, sizeof(arr[0]), cmpfunc );
  80.  
  81.     PrintArray("\n sorted arr = ", arr, n);
  82.  
  83.     printf("\n\n Smallest positive integer that does not occur in arr is %d . \n\n", solution(arr,n) );
  84.  
  85.     return 0;
  86. }
  87.  
RAW Paste Data Copied