Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<stdlib.h>
- #include<inttypes.h>
- #include<stdbool.h>
- #include<string.h>
- #include<assert.h>
- #define MAX_VAL 1000000
- struct multiples_array {
- uint32_t value;
- uint32_t no_of_multiples;
- };
- typedef struct multiples_array multiples_array_t;
- void take_input(multiples_array_t *const,uint32_t);
- void generate_multiples(multiples_array_t *const,uint32_t);
- const uint32_t find_maximum(multiples_array_t *const,uint32_t);
- int main(void) {
- uint32_t n;
- printf("Enter the size of the array\n");
- scanf("%"SCNu32,&n);
- assert(n > 0 && n < 100001);
- multiples_array_t *const data = calloc(n,sizeof(multiples_array_t));
- if(data) {
- take_input(data,n);
- generate_multiples(data,n);
- free(data);
- } else {
- fprintf(stderr,"Memory not allocated to *data pointer!\n");
- }
- return 0;
- }
- void take_input(multiples_array_t *const data,uint32_t n) {
- for(uint32_t i = 0; i < n; ++i) {
- scanf("%"SCNu32,&(data[i].value));
- data[i].no_of_multiples = 0;
- assert((data[i].value) > 0 && (data[i].value) < (MAX_VAL + 1));
- }
- }
- void generate_multiples(multiples_array_t *const data,uint32_t n) {
- uint32_t *const freq_data = calloc(MAX_VAL,sizeof(uint32_t));
- /* 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.
- */
- if(freq_data) {
- uint32_t max_val = 0;
- for(uint32_t i = 0; i < n; ++i) {
- if((data[i].value) > max_val) {
- max_val = data[i].value;
- }
- if(data[i].value == 1) {
- data[i].no_of_multiples = i;
- } else if(data[i].value == max_val) {
- data[i].no_of_multiples += freq_data[max_val - 1];
- } else if(data[i].value <= max_val) {
- for(uint32_t j = 1; ((data[i].value) * j) <= max_val; ++j) {
- (data[i].no_of_multiples) += freq_data[((data[i].value) * j) - 1];
- }
- }
- ++freq_data[(data[i].value) - 1];
- }
- for(uint32_t i = 0; i < n; ++i) {
- printf("%"PRIu32" ",(data[i].no_of_multiples));
- }
- printf("\n");
- free(freq_data);
- } else {
- fprintf(stderr,"Memory not allocated to *freq_data pointer!\n");
- }
- }
- const uint32_t find_maximum(multiples_array_t *const data,uint32_t n) {
- uint32_t max = 0;
- for(uint32_t i = 0; i < n; ++i) {
- if((data[i].value) > max) {
- max = data[i].value;
- }
- }
- return max;
- }
Add Comment
Please, Sign In to add comment