465 - Overflow

[neno_uci]

I did not find any special trick when I solved it, I just used some regular PASCAL functions like val and then checked the conditions, if you want a larger explanation, send me a private message or keep posting here if you want to, hope this helps,

Yandry.

[Rocky]

Can YOu Give Me Some Test Data???
I Think This Wiill Help Me.

THANK"S IN ADVANCE
Rocky

[Sedefcho]

Rocky,

I suggest you check the old threads about this problem.

Nevertheless, here is some test data for you and
for anyone who might need it.

I am not sure about several things.

1) Does the input contain negative numbers ? - I guess not

2) Does the input always contain SPACEs between the numbers
and the operation sign ( plus + ot multiply * ) - Well, I guess it
always contains such SPACEs but ... To be on the safe side consider
the opposite option too.

3) Does the input contain numbers in which leading zeros are
present ? I hope not but ... Again, who knows.


INPUT

Code: Select all

300 + 3
9999999999999999999999 + 11
2147483647 * 1 
2147483647 + 1 
0 * 1000000000000 
2147483648 * 0 
2000000000 + 2000000000 
1000000 * 1000000
2147483648 * -1
-1 * 2147483648
2147483647 * 2147483647
32768 * -65536 
0123232323232 * 2222222222222
000012 * 2222222222222
10000000000*10000
1002*10000

OUTPUT

Code: Select all

300 + 3
9999999999999999999999 + 11
first number too big
result too big
2147483647 * 1
2147483647 + 1
result too big
0 * 1000000000000
second number too big
2147483648 * 0
first number too big
2000000000 + 2000000000
result too big
1000000 * 1000000
result too big
2147483648 * -1
first number too big
-1 * 2147483648
second number too big
2147483647 * 2147483647
result too big
32768 * -65536
0123232323232 * 2222222222222
first number too big
second number too big
result too big
000012 * 2222222222222
second number too big
result too big
10000000000*10000
first number too big
result too big
1002*10000

[Rocky]

Thank's
I Think It Help Me....

Rocky

[Jemerson]

The input is bad, no negative Integer is allowed.

[jaracz]

my critical in/out was

Code: Select all

000000000000000000000000000000000000000000000000000000000000000000000009999999999999999999999999999999999999999999999999999999999 + 1

Regards

[jaracz]

There isn't any input like 123*5 or 123 *5 and so on

I did it like this

Code: Select all

while(gets(line))
    {
        if(!strlen(line)){printf("\n");continue;}
        printf("%s\n",line);
        sscanf(line,"%s %c %s",&a,&sign,&b);
...

[tuman]

please help me.I m undone.I dont know what r the other tricks?I hv done what i can do.The last step is posting my code to u.

//Code deleted after AC

[Solaris]

Think of cases where digits in the input number are greater than 15. e.g.

Code: Select all

564651354687965135846587984354861384 + 332132132132132154684768465413654654684

You may consider storing the given number as a string.

[tuman]

thnx solaries ,anyway i hv done this.
Yes i should hv taken input as string.Though this prog does not need big integer.Any way thanx once again. But i would also like to thank Tanvir (Aatel) for notifying me this problem.

[rmotome]

I have used all the test data in the forum but I still get wrong answer; here is my program.

#include<iostream>
#include<functional>
#include<algorithm>
#include<iterator>
#include<string>
#include<sstream>
#include<climits>
#include<cassert>
using namespace std;
#define LIM 2147483647
int main()
{
long long n1,n2,n3;
string s,t;
char c;
while(getline(cin,t)){
cout<<t<<endl;
istringstream in(t);
in>>n1>>c>>n2;
if(n1>LIM)
cout<<"first number too big"<<endl;
if(n2>LIM)
cout<<"second number too big"<<endl;
if(c=='+'){
n3=n1+n2;
if(n3>LIM)
cout<<"result too big"<<endl;
}
if(c=='*'){
n3=n1*n2;
if(n3>LIM)
cout<<"result too big"<<endl;
}
}
}

I am using LIM to disregard any ambiguity about whether to use INT_MAX or LONG_MAX (defined int climits)

[mf]

Try this input:

Code: Select all

999999999999999999999999999999 * 999999999999999999999999999999
4294967296 * 4294967296
4294967295 * 4294967295
999999999999999999999999999999 * 0

Correct output:

Code: Select all

999999999999999999999999999999 * 999999999999999999999999999999
first number too big
second number too big
result too big
4294967296 * 4294967296
first number too big
second number too big
result too big
4294967295 * 4294967295
first number too big
second number too big
result too big
999999999999999999999999999999 * 0
first number too big

[Iffat]

i can't find where is the bug in my code
i hv checked all test cases in the board but still WA.....

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<sstream>
#include<ctype.h>
#include<math.h>

using namespace std;
long long  max = 2147483647;
char str[100000000];


int main()
{
	string s;
	char c;
	
	while(gets(str)){
		s=str;
		
		
		long long  a=0,b=0,j,len,aflag=0,bflag=0,res,i,n,f;
		f=0;
		j=0;
		len=s.length();
		for(i=len;i>=0;i--){
			if(isdigit(s[i])>0 && f==1){
				a+=(s[i]-'0')*pow(10,j);
				aflag=1;
				j++;
			}
			else if(isdigit(s[i])>0 && f==0){
				b+=(s[i]-'0')*pow(10,j);
				j++;
				bflag=1;
			}
			else if(s[i]=='-'){
				if(bflag==1 && aflag==0){
					b=b*(-1);
				}
				else if(bflag==1 && aflag==1){
					a=a*(-1);
				}

			}
			else if(isspace(s[i])>0 && j!=0){
				j=0;
				f=1;
			}
			else if(s[i]=='+'){
				c='+';
				j=0;
				f=1;
			}
			else if(s[i]=='*'){
			c='*';
			j=0;
			f=1;
			}
		}
		//cout<<a<<endl<<b<<endl;
		cout<<s<<endl;
		
	if(c=='+')res=a+b;
	else if(c=='*')res=a*b;
	
	if(a>max)printf("first number too big\n");
	if(b>max)printf("second number too big\n");
	if(res>max)printf("result too big\n");
	else continue;
	}
	return 0;
}

plzz help me
thanx in advance

[emotional blind]

your a and b variable may overflow for inputs > 2^63 -1

[tanvir_cse]

Cant understand whay WA.Pls reply me . I have done this code using Big Number Summation and Big Number multiplication.
Then comparing the result length with the value "2147483647" .. But still WA WA WA WA WA WA

Is my input-Output format is correct ??? Need answer urgent

#include<stdio.h>
#include<ctype.h>
#include<string.h>

void BigMul(char *s1, char*s2, char *result);
void string_filter(char *s1, char*s2);
void Bigsum (char *str1,char *str2, char *sum);
void Rev(char *s);
void Big_sum (char *str1,char *str2, char *sum);

int main(void)
{
int i,m,len1,len2,maxlen,reslen;
char s1[1000],s2[1000],res[1000],c,result[1000], str[1000];

char max[]="2147483647";
maxlen=10;
while( true )
{
gets(str);
m=0;
for(i=0; ; i++)
{
if( str=='+' || str=='*' )
{
c=str;
break;
}

if(str==' ')
continue;

s1[m++]=str;
}
s1[m]='\0';

m=0;

for(++i; str ; i++)
{
if( str=='+' || str=='*' )
break;

if(str==' ')
continue;

s2[m++]=str;
}
s2[m]='\0';
//puts(s1); puts(s2);

string_filter(s1,s2);
len1=strlen(s1);
len2=strlen(s2);

if(c=='+')
Big_sum(s1,s2,res);
else if(c=='*')
BigMul(s1, s2, res);

reslen=strlen(res);
if(len1>maxlen)
{
printf("first number too big\n");
}
else if( len1==maxlen)
{
if( strcmp(max,s1) ==-1 )
{
printf("first number too big\n");
}
}

if(len2>maxlen)
{
printf("second number too big\n");
}
else if( len2==maxlen)
{
if( strcmp(max,s2) ==-1 )
{
printf("second number too big\n");
}
}

if(reslen>maxlen)
{
printf("result too big\n");
}
else if( reslen==maxlen)
{
if( strcmp(max,res) ==-1 )
{
printf("result too big\n");
}
}


}


}




void Big_sum (char *str1,char *str2, char *sum)
{
char ans[1000] ;
int carry=0, i , x ,j,m=0 ;

string_filter(str1 , str2);
i=strlen(str1)-1;
j=strlen(str2)-1;

while(i>=0 && j>=0)
{
x=str1[i]-'0'+str2[j]-'0'+carry;
ans[m]=(x%10)+'0' ;
carry = (x/10) ;
m++;
i--;
j--;
}

if(j==-1)
{
while(i>=0)
{
x=str1[i]-'0'+carry ;
ans[m++]=(x%10) +'0' ;
carry=(x/10);
i--;
}
}
else
{
while(j>=0)
{
x=str2[j]-'0'+carry ;
ans[m++]=(x%10) +'0' ;
carry=(x/10);
j--;
}
}

if(carry)
{
ans[m++]=carry+'0' ;
ans[m]='\0' ;
}
else
ans[m]='\0';

Rev(ans);
strcpy(sum,ans);

}



void BigMul(char *s1, char*s2, char *result)
{
char temp[10000], res[1000],n1[1000],sum[1000];
int a,b,i,k,carry=0,j,x,n,cross;

string_filter(s1 , s2);

if(s1[0]=='\0' || s2[0]=='\0')
{
strcpy(result,"0");
}
else
{

a=strlen(s1);
b=strlen(s2);

if(a < b)
{
strcpy(temp,s1);
strcpy(s1,s2);
strcpy(s2,temp);
a=strlen(s1);
b=strlen(s2);
}
cross=0;

for(j=b-1; j>=0; j--)
{
if(cross>=1)
{
for(k=0; k<cross; k++)
n1[k]='0';
}
else
k=0;
carry=0;

for(i=a-1; i>=0; i--,k++)
{
x=(((s2[j]-'0')*(s1[i]-'0'))+carry)%10;
n1[k]=x+'0';
carry=(((s1[i]-'0')*(s2[j]-'0'))+carry)/10;
}
if(carry)
n1[k++]=carry+'0';
n1[k]='\0';

if(cross==0)
{
for(n=0; n<k; n++)
sum[n]='0';
sum[n]='\0';
Rev(sum);
}
Rev(n1);
//puts(n1);
//strcpy(str1,n1);
Bigsum(n1 , sum , res);
strcpy(sum,res);
cross++;
}

strcpy(result, sum);
}

}


void string_filter(char *s1, char*s2) //removing leading zeros
{
int i,j,k;
char temp[1000];

for(i=0; s1[i]=='0'; i++);
for(j=i,k=0; s1[j]; j++)
temp[k++]=s1[j];

temp[k]='\0';
strcpy(s1,temp);

for(i=0; s2[i]=='0'; i++);
for(j=i,k=0; s2[j]; j++)
temp[k++]=s2[j];

temp[k]='\0';
strcpy(s2,temp);


}



void Bigsum (char *str1,char *str2, char *sum)
{
char ans[1000] ;
int carry=0, i , x ,j,m=0 ;
i=strlen(str1)-1;
j=strlen(str2)-1;

while(i>=0 && j>=0)
{
x=str1[i]-'0'+str2[j]-'0'+carry;
ans[m]=(x%10)+'0' ;
carry = (x/10) ;
m++;
i--;
j--;
}

if(j==-1)
{
while(i>=0)
{
x=str1[i]-'0'+carry ;
ans[m++]=(x%10) +'0' ;
carry=(x/10);
i--;
}
}
else
{
while(j>=0)
{
x=str2[j]-'0'+carry ;
ans[m++]=(x%10) +'0' ;
carry=(x/10);
j--;
}
}

if(carry)
{
ans[m++]=carry+'0' ;
ans[m]='\0' ;
}
else
ans[m]='\0';

Rev(ans);
strcpy(sum,ans);

}


void Rev(char *s)
{
char temp[10000];
int i,j=0;

for(i=strlen(s)-1; i>=0; i--,j++)
{
temp[j]=s[i];
}
temp[j]='\0';
strcpy(s,temp);

}