SHARE
TWEET

Untitled

a guest Oct 12th, 2019 16 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<inttypes.h>
  4. #include<stdbool.h>
  5. #include<string.h>
  6. #include<assert.h>
  7.  
  8. #define MAX_VAL 1000000
  9.  
  10. struct multiples_array {
  11.     uint32_t value;
  12.     uint32_t no_of_multiples;
  13. };
  14. typedef struct multiples_array multiples_array_t;
  15.  
  16. void take_input(multiples_array_t *const,uint32_t);
  17. void generate_multiples(multiples_array_t *const,uint32_t);
  18. const uint32_t find_maximum(multiples_array_t *const,uint32_t);
  19.  
  20. int main(void) {
  21.     uint32_t n;
  22.     printf("Enter the size of the array\n");
  23.     scanf("%"SCNu32,&n);
  24.     assert(n > 0 && n < 100001);
  25.     multiples_array_t *const data = calloc(n,sizeof(multiples_array_t));
  26.     if(data) {
  27.         take_input(data,n);
  28.         generate_multiples(data,n);
  29.         free(data);
  30.     } else {
  31.         fprintf(stderr,"Memory not allocated to *data pointer!\n");
  32.     }
  33.     return 0;
  34. }
  35.  
  36. void take_input(multiples_array_t *const data,uint32_t n) {
  37.     for(uint32_t i = 0; i < n; ++i) {
  38.         scanf("%"SCNu32,&(data[i].value));
  39.         data[i].no_of_multiples = 0;
  40.         assert((data[i].value) > 0 && (data[i].value) < (MAX_VAL + 1));
  41.     }
  42. }
  43.  
  44. void generate_multiples(multiples_array_t *const data,uint32_t n) {
  45.     uint32_t *const freq_data = calloc(MAX_VAL,sizeof(uint32_t));
  46.     /*  Iterating through each a[i] and before increamenting the freq[i], finding out how many multiples of a[i] I have encountered till now by parsing the freq_data[] upto the max_val.  
  47.     */    
  48.     if(freq_data) {
  49.         uint32_t max_val = 0;
  50.         for(uint32_t i = 0; i < n; ++i) {
  51.             if((data[i].value) > max_val) {
  52.                 max_val = data[i].value;
  53.             }
  54.             if(data[i].value == 1) {
  55.                 data[i].no_of_multiples = i;
  56.             } else if(data[i].value == max_val) {
  57.                 data[i].no_of_multiples += freq_data[max_val - 1];
  58.             } else if(data[i].value <= max_val) {
  59.                 for(uint32_t j = 1; ((data[i].value) * j) <= max_val; ++j) {
  60.                     (data[i].no_of_multiples) += freq_data[((data[i].value) * j) - 1];
  61.                 }
  62.             }
  63.             ++freq_data[(data[i].value) - 1];
  64.         }
  65.         for(uint32_t i = 0; i < n; ++i) {
  66.             printf("%"PRIu32" ",(data[i].no_of_multiples));
  67.         }
  68.         printf("\n");
  69.         free(freq_data);
  70.     } else {
  71.         fprintf(stderr,"Memory not allocated to *freq_data pointer!\n");
  72.     }
  73. }
  74.  
  75. const uint32_t find_maximum(multiples_array_t *const data,uint32_t n) {
  76.     uint32_t max = 0;
  77.     for(uint32_t i = 0; i < n; ++i) {
  78.         if((data[i].value) > max) {
  79.             max = data[i].value;
  80.         }
  81.     }
  82.     return max;
  83. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top