UVA 713 Adding Reversed Numbers Solution

UVA 713 Adding Reversed Numbers Solution

/*uva id: shoaib05
   Accepted Time: 0.000
*/

Procedure:

Take input as string.
Reverse the string.
build the string equal length by putting zeros at start.
Split the string and store in queue.

Input:
8000000001   length is 10
1000101         length is 7

max_length is 10.

Reverse the string 1000000008
                                    1010001
put zero and build equal length. 0001010001

str1 is 1000000008
str2 is 0001010001

Here I spilt the string by size 4 and store in queue.

Queue 1
0008
0000
rest of digits store in rem1=10

Queue 2
0001
0101
rest of digits store in rem2=00

Take string from queue1 and queue2, convert srings to number and add. If size exceed max size of 4 digit 9999 then subtract the sum value from 10000. put the subtract's value into result string. And set the carry flag. carry value will add with the next block of 4 digit.
result=subtract's value + result;

Another case:
If sum value is less than 4 digit then build it 4 digit by putting zeros at start position. 

1st block:
0008 convert to number and value is 8.
0001 convert to number and value is 1.
sum=8+1=9;
convert sum to string which is 9. Here size is 1. put 3 zeros and convert it to 4 digit. So, temp string is 0009

result=temp+result.//0009

2nd block:

0000 is 0.
0101 is 101.
sum=0+101=101.Convert string and build it 4 digit and this is 0101.

result=temp+result.//01010009.

queue's are become empty. end of loop.

if rem1 and rem2 s are not zero. Then convert to number and sum this number. If carry flag is true then add 1 with reminder's sum.
result=reminder's sum+result.

Critical Case:
if result length is less than max_length than add zero at the start position and become the length of result is max_length.

Reverse the result and remove the trail zeros.


Code:

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>

using namespace std;


string reverseString(string str)
{
int i=str.length(),j=0;
string temp=str;
while(i--)
{
temp[j++]=str[i];
}
return temp;
}

string intToString(int num)
{
string str="";
int mul=1,rem;
char ch;
while(num!=0)
{
rem=num%10;
num=num/10;
ch=(char)rem+48;
str.insert(0,1,ch);
}
return str;
}

int stringToInt(string str)
{
int sum=0,i,mul=1,len=str.length();
for(i=len-1;i>=0;i--)
{
sum+=(str[i]-48)*mul;
mul=mul*10;
}
return sum;
}

int trailZero(string str)
{
int index=0;
while(str[index]=='0')
{
index++;
}
return index;
}

int main()
{
int test;
string num1,num2,result,temp,temp1,temp2,rem1,rem2;
int len1,len2,index,val1,val2,i,lendif,len,val,piece,start,mod,zero_index,max_length;
queue<string>q1,q2;
bool carry;
cin>>test;
while(test--)
{
cin>>num1>>num2;

num1=reverseString(num1);
num2=reverseString(num2);

len1=num1.length();
len2=num2.length();


if(len1>len2)
{
lendif=len1-len2;
num2.insert(0,lendif,'0');
max_length=len1;
}
else if(len1<len2)
{
lendif=len2-len1;
num1.insert(0,lendif,'0');
max_length=len2;
}
else
max_length=len1;

len=num1.length();
piece=len/9;  // Block size is 9.
start=len;
val=1;
while(val<=piece)
{
start=start-9;
temp=num1.substr(start,9);
q1.push(temp);
temp=num2.substr(start,9);
q2.push(temp);
val++;
}
rem1="";
rem2="";
mod=len%9;
if(mod!=0)
{
rem1=num1.substr(0,mod);
rem2=num2.substr(0,mod);
}
carry=false;
result="";
while(!q1.empty())
{
val1=stringToInt(q1.front());
if(carry)
val1++;
q1.pop();
val2=stringToInt(q2.front());
q2.pop();
val=val1+val2;
if(val>999999999)
{
val=val-1000000000;
carry=true;
}
else
carry=false;
temp=intToString(val);
if(temp.length()<9)
{
temp.insert(0,9-temp.length(),'0');
}
result=temp+result;
}
if(mod!=0)
{
val=stringToInt(rem1)+stringToInt(rem2);
if(carry)
val++;

result=intToString(val)+result;
}
else if(carry)
result="1"+result;
if(result.length()<max_length)
{
lendif=max_length-result.length();
result.insert(0,lendif,'0');
}
result=reverseString(result);
zero_index=trailZero(result);
len=result.length()-zero_index;
result=result.substr(zero_index,len);
cout<<result<<endl;
}
return 0;
}



Critical Input:

9000100 //length is 7
1001

Procedure:

0010009 value is 10009
1001 value is 1001.
10009+1001=11010.
convert sum value to string 11010. 
convert result string max length string 0011010.
Revers the result 0101100.
Remove the trail zero. and result becomes 101100.





Comments

Post a Comment

Popular posts from this blog

uva 679 - Dropping Balls Solution

uva 679 - Dropping Balls Solution Algorithm: 1. convert (position-1)  to binary and store it to a string. 2. make the binary string length equal to the (depth-1) by adding zero(0) at start of the string. 3. reverse the binary string. 4. convert binary string to integer + power(2,depth-1). Example: depth=7; position=4; covert 4-1= 3 to binary. binary string is 11. make the string length 7-1=6 by adding 0. Updated string 000011. reverse the binary string and string is now 110000 convert binary string(110000) to integer. value is 48. calculate power_value=pow(2,7-1)=pow(2,6)=64. Answer is = 48 + 64=112. Code in C++: #include<iostream> #include<string> #include<algorithm> using namespace std; string convertDecimalToBinary(int num){ string result; while(num!=0){ if(num%2==1) result.insert(0,1,'1'); else result.insert(0,1,'0'); num=num/2; } return result; } int convertBinaryToDecimal(string &n...
Read more

uva 481 - What Goes Up Solution

uva 481 - What Goes Up Solution #include<iostream> #include<vector> using namespace std; void binary_search(int *arr, int search_value, int start, int end, int &index){ if (start == end){ index = start; return; } int mid = (start + end) / 2; if (arr[mid] == search_value){ index = mid; return; } else if (arr[mid + 1] == search_value){ index = mid + 1; return; } else if (arr[mid]<search_value && arr[mid + 1]>search_value){ index = mid + 1; return; } else if (arr[mid] > search_value){ binary_search(arr, search_value, start, mid, index); } else{ binary_search(arr, search_value, mid + 1, end, index); } } void calculate_lis(vector<int>&arr,vector<int>&result){ int *temp, i, max = 0, j, index, n = arr.size(), *res; temp = new int[n]; res = new int[n]; temp[0] = 0; for (i = 1; i < n; i++){ if (arr[temp[max]] < arr[i]){ res[i] = temp[max]; max++; ...
Read more

uva-10077 Solution --- The Stern-Brocot Number System

#include<iostream> using namespace std; int main(){ int input_num,input_den,left_num,left_den,right_num,right_den,cur_num,cur_den; while(cin>>input_num>>input_den){ if(input_num==1 && input_den==1) break; left_num=0; left_den=1; right_num=1; right_den=0; cur_num=cur_den=1; while(true){ if(cur_num== input_num && cur_den==input_den) break; if(cur_num*input_den < cur_den*input_num){ cout<<"R"; left_num=cur_num; left_den=cur_den; cur_num+=right_num; cur_den+=right_den; }else{ cout<<"L"; right_num=cur_num; right_den=cur_den; cur_num+=left_num; cur_den+=left_den; } } cout<<endl; } return 0; }
Read more