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;
}

---

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 ...

---

Quote:

---

Originally Posted by algorism

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'

Quote:

---

Originally Posted by algorism

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:
Attachment 15194
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;
}

---

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

Quote:

---

Originally Posted by Salem

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 :D

Quote:

---

Originally Posted by Iiz

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?

Quote:

---

Originally Posted by algorism

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?

Quote:

---

Originally Posted by Iiz

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.

Quote:

---

Originally Posted by algorism

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.
Attachment 15196
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 :D