Thread: Most probably memory allocation issue

  1. #1
    Registered User
    Join Date
    Aug 2017
    Posts
    17

    Most probably memory allocation issue

    I think I've got the logic of the problem correctly(although a bit messy)

    Initally, I had done this with static variable of size 10 but the challenge is to take very large inputs (upto 10^100) so I went the dynamic way and stuck again

    So far I know, the error is lying after line no. 42 in the malloc of my struct num b. But I can't understand why.

    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #define MAXDIGITS 10000000000
    struct num
    {
        int ndigits;
        char *d;
    } a,b;
    int main(void)
    {
        a.ndigits=0;
        b.ndigits=0;
        a.d=(char*)malloc(MAXDIGITS*sizeof(char));
        b.d=(char*)malloc(MAXDIGITS*sizeof(char));
        int i,j,k,t,flag=0;
        scanf("%d",&t);
        fflush(stdin);
        while (t!=0)
        {
            char p,q,r,x;
            while(1)
            {
                scanf("%c",&x);
                if (x=='\n') break;
                //printf("%c",x);
                a.d[a.ndigits]=x;
                a.ndigits+=1;
            }
            //printf("\ndigits= %d",a.ndigits);
            //for(i=0;i<a.ndigits;i++)
            //printf("digit: \n%c",a.d[i]);
            for(i=0; i<a.ndigits; i++)
            {
                for(j=0; j<a.ndigits; j++)
                {
                    printf("\ni= %d j= %d",i,j);
                    if (i==j) continue;
                    p=a.d[i];
                    q=a.d[j];
                    r=(p-'0')*10+(q-'0');
                    printf("\np= %c q= %c r= %c",p,q,r);
                    if (r>=65 && r<=90)
                    {
                        flag=1;
                        int rf=0;
                        for(k=0; k<b.ndigits; k++){printf("%d",k);
                            if (r==b.d[k])
                            {
                                rf=1;
                                break;
                            }
                            }
                        if (rf!=1)
                        {
                            b.d[b.ndigits]=r;
                            b.ndigits+=1;
                            rf=0;
                        }
                    }
                }
            }
            for(i=0; i<b.ndigits-1; i++)
                for(j=0; j<b.ndigits-i-1; j++)
                    if (b.d[j] > b.d[j+1])
                    {
                        x=b.d[j];
                        b.d[j]=b.d[j+1];
                        b.d[j+1]=x;
                    }
            if(flag==1)
                for(i=0; i<b.ndigits; i++)
                    printf("%c",b.d[i]);
            else printf("\n");
            t--;
        }
        return 0;
    }

  2. #2
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    You mean 10 to the 10 (not 100), i.e., what most humanoids call "ten billion". Since you are mallocing two arrays of this size, I assume your machine has at least 20 gigabytes of memory. Lucky you! You should still test the return value of malloc just in case. My pathetic machine refuses to allocate that much memory.

    Most bipeds would also tell us what their program is supposed to do and give some sample input.

    I don't know what you're talking about on "line 42".

    Your indentation is weird. What does the end brace on line 52 match up with? (Actually, I see it now. Still.)

    a and b shouldn't be global. Declare them in main instead.

    Since there's no need for the cast, and sizeof(char) is 1 by definition, your malloc's can just be like:
    Code:
        a.d = malloc(MAXDIGITS);
    Use 'A' and 'Z' instead of 65 and 90. (Assuming that's what 65 and 90 mean.)

    Don't flush stdin. It's not portable, technically undefined. (It causes my machine to turn on the coffee maker.) You can eat the newline like this:
    Code:
        while (getchar() != '\n')
            ;
    Or, more correctly (since getchar could return EOF):
    Code:
        int c;
        while ((c = getchar()) != '\n' && c != EOF)
            ;
        // possibly handle an EOF ...
    Last edited by algorism; 09-01-2017 at 05:12 PM.
    Explode the sunlight here, gentlemen, and you explode the entire universe. - Plan 9 from Outer Space

  3. #3
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,750
    Quote Originally Posted by algorism View Post
    Use 'A' and 'Z' instead of 65 and 90. (Assuming that's what 65 and 90 mean.)
    Technically you shouldn't even be doing that in the sense that it's being used in this program:
    Code:
    if (r >= 'A' && r <= 'Z')
    is not portable as there is nothing in the standard that says 'Z' must be larger than 'A'

  4. #4
    Registered User
    Join Date
    Aug 2017
    Posts
    17
    Quote Originally Posted by algorism View Post
    You mean 10 to the 10 (not 100), i.e., what most humanoids call "ten billion". Since you are mallocing two arrays of this size, I assume your machine has at least 20 gigabytes of memory. Lucky you! You should still test the return value of malloc just in case. My pathetic machine refuses to allocate that much memory.

    Most bipeds would also tell us what their program is supposed to do and give some sample input.

    I don't know what you're talking about on "line 42".

    Your indentation is weird. What does the end brace on line 52 match up with? (Actually, I see it now. Still.)

    a and b shouldn't be global. Declare them in main instead.

    Since there's no need for the cast, and sizeof(char) is 1 by definition, your malloc's can just be like:
    Code:
        a.d = malloc(MAXDIGITS);
    Use 'A' and 'Z' instead of 65 and 90. (Assuming that's what 65 and 90 mean.)

    Don't flush stdin. It's not portable, technically undefined. (It causes my machine to turn on the coffee maker.) You can eat the newline like this:
    Code:
        while (getchar() != '\n')
            ;
    Or, more correctly (since getchar could return EOF):
    Code:
        int c;
        while ((c = getchar()) != '\n' && c != EOF)
            ;
        // possibly handle an EOF ...
    I know I am being unreasonable when the constraints are so huge but that's what's given as constraints. Here's a screenshot:
    Most probably memory allocation issue-nz5gep6-png
    Sorry, I forgot to add sample input and output.
    Input:
    4
    65
    566
    11
    1623455078

    Output:
    A
    AB

    ACDFGHIJKLNPQRSTUVW
    ---
    I edited my code accordingly(removed fflush() and malloc problems) but it still doesn't help.
    Code:
    #include<stdio.h>#include<stdlib.h>
    #define MAXDIGITS 10000000000
    struct num
    {
        int ndigits;
        char *d;
    } a,b;
    int main(void)
    {
        a.ndigits=0;
        b.ndigits=0;
        a.d=malloc(MAXDIGITS);
        b.d=malloc(MAXDIGITS);
        int i,j,k,t,flag=0;
        scanf("%d",&t);
        //fflush(stdin);
        getchar();
        while (t!=0)
        {
            char p,q,r,x;
            int c;
            while((c = getchar()) != '\n' && c != EOF)
            {
                //scanf("%c",&x);
                if (c=='\n') break;
                //printf("%c",x);
                a.d[a.ndigits]=c;
                a.ndigits+=1;
            }
            //printf("\ndigits= %d",a.ndigits);
            //for(i=0;i<a.ndigits;i++)
            //printf("digit: \n%c",a.d[i]);
            for(i=0; i<a.ndigits; i++)
            {
                for(j=0; j<a.ndigits; j++)
                {
                    printf("\ni= %d j= %d",i,j);
                    if (i==j) continue;
                    p=a.d[i];
                    q=a.d[j];
                    r=(p-'0')*10+(q-'0');
                    printf("\np= %c q= %c r= %c",p,q,r);
                    if (r>='A' && r<='Z')
                    {
                        flag=1;
                        int rf=0;
                        for(k=0; k<b.ndigits; k++){printf("%d",k);
                            if (r==b.d[k])
                            {
                                rf=1;
                                break;
                            }
                            }
                        if (rf!=1)
                        {
                            b.d[b.ndigits]=r;
                            b.ndigits+=1;
                            rf=0;
                        }
                    }
                }
            }
            for(i=0; i<b.ndigits-1; i++)
                for(j=0; j<b.ndigits-i-1; j++)
                    if (b.d[j] > b.d[j+1])
                    {
                        x=b.d[j];
                        b.d[j]=b.d[j+1];
                        b.d[j+1]=x;
                    }
            if(flag==1)
                for(i=0; i<b.ndigits; i++)
                    printf("%c",b.d[i]);
            else printf("\n");
            t--;
        }
        return 0;
    }

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,068
    Your constraints are there to make you think, by putting the brute force method out of reach.

    You need to think first, not reach for the keyboard and try to malloc 10gb
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Registered User
    Join Date
    Aug 2017
    Posts
    17
    Quote Originally Posted by Salem View Post
    Your constraints are there to make you think, by putting the brute force method out of reach.
    You need to think first, not reach for the keyboard and try to malloc 10gb
    So, I am supposed to think of getting the desired output without storing the input? Or by only partially storing the input?

    EDIT1 - I rethought my approach to this problem as Salem said. Obviously, I can't store such a huge number. How about I create a struct that stores the characters entered(i.e 0 to 9) and its frequency in another integer array? So that wouldn't really exceed memory limitations I suppose. I'll type out a code and put it in here later. Thanks again people
    Last edited by Iiz; 09-02-2017 at 05:46 AM.

  7. #7
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    Quote Originally Posted by Iiz View Post
    I edited my code accordingly(removed fflush() and malloc problems) but it still doesn't help.
    You didn't fix the "malloc problems" since you didn't test the return value to see if it's non-NULL. That's obviously the most important thing. The other changes don't really change anything at all ... obviously. Jesus.

    And you still haven't bothered to tell us what the f the f'ing thing is supposed to do! If there is an online description, then link to that. Why does 4 yield A; why does 65 yield AB; what the hell is going on?
    Explode the sunlight here, gentlemen, and you explode the entire universe. - Plan 9 from Outer Space

  8. #8
    Registered User
    Join Date
    Aug 2017
    Posts
    17
    Quote Originally Posted by algorism View Post
    You didn't fix the "malloc problems" since you didn't test the return value to see if it's non-NULL. That's obviously the most important thing. The other changes don't really change anything at all ... obviously. Jesus.

    And you still haven't bothered to tell us what the f the f'ing thing is supposed to do! If there is an online description, then link to that. Why does 4 yield A; why does 65 yield AB; what the hell is going on?
    oh.
    Really sorry to be a bother and getting on your nerves. I'll try to fix the malloc problem soon but for now, the problem didn't really need a dynamic allocation. I'll surely update it and in due time. Here's the link to the problem: Contest Page | CodeChef
    Shall I post my solution as well?

  9. #9
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    Quote Originally Posted by Iiz View Post
    oh.
    Really sorry to be a bother and getting on your nerves. I'll try to fix the malloc problem soon but for now, the problem didn't really need a dynamic allocation. I'll surely update it and in due time. Here's the link to the problem: Contest Page | CodeChef
    Shall I post my solution as well?
    I'm sorry for getting peeved. I couldn't comprehend what your program was trying to do. It was obviously putting the digits together in every possible way and comparing them to ascii codes for the letters 'A' to 'Z', but I couldn't understand why.

    Sure, post your program. Does it pass the tests on the code chef site?

    BTW, I notice that the actual limit is 10 to the 100000 (not 10 to the ten billion), so you could've malloced that much memory, but it would have taken too long for the program to run and there's obviously a much simpler way to solve the problem.
    Explode the sunlight here, gentlemen, and you explode the entire universe. - Plan 9 from Outer Space

  10. #10
    Registered User
    Join Date
    Aug 2017
    Posts
    17
    Quote Originally Posted by algorism View Post
    I'm sorry for getting peeved. I couldn't comprehend what your program was trying to do. It was obviously putting the digits together in every possible way and comparing them to ascii codes for the letters 'A' to 'Z', but I couldn't understand why.

    Sure, post your program. Does it pass the tests on the code chef site?

    BTW, I notice that the actual limit is 10 to the 100000 (not 10 to the ten billion), so you could've malloced that much memory, but it would have taken too long for the program to run and there's obviously a much simpler way to solve the problem.
    Nah, it's fine. You're helping people voluntarily it's ok to get angry ^^
    Anyway, I am posting a screenshot that my program worked. Idk what are the policies of this site but sharing solved code isn't allowed but it's mostly similar to the one I've posted but I don't need to malloc space.
    Most probably memory allocation issue-unknown-png
    I'll edit this after the contest gets over. I am doing another one which is exceeding the time limit so I'll probably concentrate on that one first. Thanks for all the tips on structs and malloc

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory allocation issue
    By SeldinG in forum C Programming
    Replies: 14
    Last Post: 03-12-2016, 01:20 AM
  2. Memory Allocation?
    By A36 in forum C++ Programming
    Replies: 13
    Last Post: 08-29-2014, 12:54 PM
  3. Memory Allocation
    By Goku in forum C Programming
    Replies: 13
    Last Post: 02-20-2013, 09:01 PM
  4. Array allocation issue
    By dxfoo in forum C++ Programming
    Replies: 14
    Last Post: 06-22-2010, 11:11 AM
  5. memory allocation
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 06-09-2002, 01:23 PM

Tags for this Thread