I have a very large number represented by a string. Say String n = "64772890123784224827" . I want to divide the number by 3 efficiently. How can I do it? Some implementations are given below which can find out remainder. But how to get the quotient efficiently?
In Java, the number can be represented with BigInteger and the division operation can be done on BigInteger. But that takes too much time. Please help me find out the efficient way to divide this large number by 3.
Well following is a very basic implementation to find out the remainder:
#include <bits/stdc++.h>
using namespace std;
int divideByN(string, int);
int main()
{
string str = "-64772890123784224827";
//string str = "21";
int N = 3;
int remainder = divideByN(str, N);
cout << "\nThe remainder = " << remainder << endl;
return 0;
}
int divideByN(string s, int n)
{
int carry = 0;
int remainder = 0;
for(int i = 0; i < s.size(); i++)
{
if(i == 0 && s.at(i) == '-')
{
cout << "-";
continue;
}
//Check for any illegal characters here. If any, throw exception.
int tmp = (s.at(i) - '0') + remainder * carry;
cout << (tmp / n);
if(tmp % n == 0)
{
carry = 0;
remainder = 0;
}
else
{
remainder = tmp % n;
carry = 10;
}
}
return remainder;
}
Based on some good answers, here is a minimal implementation using lookup table to find out the remainder:
#include <bits/stdc++.h>
using namespace std;
int divideByN_Lookup(string, int);
int lookup[] = { 0, 1, 2, 0, 1, 2, 0, 1, 2, 0 }; //lookup considering 3 as divisor.
int main() {
string str = "64772890123784224827";
int N = 3;
int remaninder_lookup = divideByN_Lookup(str, N);
cout << "Look up implementation of remainder = " << remaninder_lookup
<< endl;
return 0;
}
int divideByN_Lookup(string s, int n) {
int rem = 0;
int start = 0;
if (s.at(start) == '-')
start = 1;
for (unsigned int i = start; i < s.size(); i++)
rem = (rem + lookup[s.at(i) - '0']) % n;
return rem;
}
What about quotient? I know I can process all characters one by one and add the quotient to a char array or string. But what is the most efficient way to find out the quotient?
