Getting an error “terminate called after throwing an instance of 'std::out_of_range'”

[philip92]

I am doing a challenge questions from LeetCode and I came across this question.

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"

Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"

Output: "56088"

Note:

1. The length of both num1 and num2 is < 110.

2. Both num1 and num2 contain only digits 0-9.

3. Both num1 and num2 do not contain any leading zero, except the number 0 itself.

4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

My code is working fine and getting the desired output. But I keep getting an error "terminate called after throwing an instance of 'std::out_of_range'"

string multiply(string num1, string num2) {
        
    long long int p = stoi(num1);
	long long int q = stoi(num2);
	long long int total = p * q;
	
    string a = to_string(total);
	return a;
    }

[dutch]

Casting one of p or q to long long int in the multiplication might fix your error.

However, it's unlikely that the "challenge" is meant to be solved like that, since it's not, you know, challenging. What if the input's are 50 digits long each? 64-bit ints can only hold up to about 40 decimal digits. Presumably you are meant to implement your own multiplication routine that works directly on the strings.

[philip92]

@dutch, Still I am getting an error "terminate called after throwing an instance of 'std::out_of_range' what(): stoi"

[Repeater]

@philip92

The task is deliberately designed such that you cannot do it simply by multiplying the two numbers together. You must solve this another way.

[jonnin]

4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

long long int p = stoi(num1);

read those 2 lines over and over until you see the problem.

[Albatross]

That suggests that whatever was passed to stoi is larger than what an integer can store (because yes, stoi returns an integer). Perhaps you meant to use stoll?

That said, dutch is definitely right that long long ints are not going to be enough. The giveaways are these lines in the problem description:

1. The length of both num1 and num2 is < 110.

4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

Meaning, in fact, even if long long ints were enough, this solution would be invalid.

-Albatross

[salem c]

I guess this isn't taught in schools any more.
https://www.wikihow.com/Do-Long-Multiplication

Perish the thought that a so-called "challenge" question could be solved by anything so simple as stoi() and a multiplication sign.

[jonnin]

Its tricky to do it yourself efficiently. Anyone with a few months of C++ can make a big int elementary school math program, but crawling over in base 10 (unnatural to the pc) a digit at a time is going to take all day. (Just learned this trying to do some math in python, which does integers exactly this way, and my 0.4 second c++ program became 45 seconds in py). (Yea, yea, scipy and C data type code is out there, and there are ways around the issue, just talking the base language). Doing it in a bitfield or the like takes some thinking.

[jonnin]

This got my creativity going so I tried (without looking *anything* up) to convert a string big int input into binary efficiently and work with it, and that was going to take more time than I had. So I went back to the 'what can I do over lunch' drawing board and noted some obvious things... a 64 bit int can hold any 32 bit int squared, for example, so if you want to safely multiply 2 chunks you can take 2 32 bit cuts out of the number and deal with the parts. And base 10 is easy to think in, so I did a really, really quick what if using 3 digits at a time (1000 based).
Everything I did is simple and direct approach, so as a beginner you should be able to follow this. The binary way is going to be more efficient, but its going to be more work too. Bumping it up to 10^8 instead of 10^3 and it will be 8 times faster than base 10, so not too bad for a coding 101 approach. I didn't fool with sign bit tracking here, that would go in the class if you expanded it. The multiply loop obviously is NOT optimized.
Anyway Phillip... if you are still here, see if this very crude approach answers your question. You can reverse stringify the chunks at the end. Doing that efficiently is annoying too, the built in tools are terrible and the code to do it right is obnoxious.

int main()
{
  const int base = 1000; //100000000 fits in 64 bit squared and seems like the best value
  const int logbase = 3; //the log base 10 of above. 
  
  string a = "1234567"; //couple of numbers to test with
  string b = "234567";
  uint64_t abi[5] = {0}; //big integers. this needs a class wrapper for operators etc later
  uint64_t bbi[5] = {0};
  uint64_t cbi[5] = {0}; 
  
  int i,j; //loop vars
      
  //convert text to big integer storage.
  for(i = 0; i < (a.length()/logbase); i++)
  {
	 abi[i] = stoi(a.substr(a.length()-logbase*(i+1),logbase)); 	 
  }  
  if(a.length()%logbase)
  {
	 int tmp = a.length()%logbase;
	 abi[i] = stoi(a.substr(0,tmp));
  }
      
  for(i = 0; i < (b.length()/logbase); i++)
  {
	 bbi[i] = stoi(b.substr(b.length()-logbase*(i+1),logbase));	 
  }
  if(b.length()%logbase)
  {
	 int tmp = b.length()%logbase;
	 bbi[i] = stoi(b.substr(0,tmp));
  }   
   
  //multiply   
  uint64_t cry = 0; //carry
  uint64_t tmp = 0; //intermediate
  for(i = 0; i < 3; i++) //need to figure out how many times to loop. 
  {
	  for(j = 0; j < 3; j++)//need to figure out how many times to loop. 
	  {
		 tmp  = bbi[i]*abi[j];  		
		 cbi[i+j] += (tmp+ cry);
		 cry = cbi[i+j]/base;
		 cbi[i+j] %= base;			
	  }
	   cbi[i+j] += cry;
	   cry = 0;
  }	  

  //print result.  note we are storing backwards.   
  cout << cbi[3]<<cbi[2]<<cbi[1]<<cbi[0];  
  //28958703552 output for 123456*234567 from calc.exe
  //289588677489 for 1234567 * 234567
    
}