Created
October 7, 2023 03:10
-
-
Save justinhj/027cae0759e3c786afee351e738315dd to your computer and use it in GitHub Desktop.
leetcode.com/problems/multiply-strings
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <ranges> | |
#include <algorithm> | |
using namespace std; | |
class Solution { | |
public: | |
string m2(string num1, int multiplier, int zeros) { | |
string out; | |
while(zeros > 0) { | |
out.push_back('0'); | |
zeros--; | |
} | |
int l1 = num1.length(); | |
int carry = 0; | |
while(l1 > 0) { | |
l1 --; | |
int v1 = num1[l1] - '0'; | |
int v2 = multiplier * v1 + carry; | |
if(v2 > 9) { | |
carry = v2 / 10; | |
v2 = v2 % 10; | |
} else { | |
carry = 0; | |
} | |
out.insert(out.begin(), v2 + '0'); | |
} | |
if(carry > 0) { | |
out.insert(out.begin(), carry + '0'); | |
} | |
return out; | |
} | |
string multiply(string num1, string num2) { | |
int l1 = num1.length(); | |
string out = "0"; | |
int zero = 0; | |
while(l1 > 0) { | |
l1 --; | |
int multiplier = l1 >= 0 ? num1[l1] - '0' : 1; | |
string result = m2(num2, multiplier, zero); | |
zero ++; | |
out = add(result, out); | |
} | |
// Check for all zeros | |
int i=0; | |
auto allZero = false; | |
while(i<out.length()) { | |
if(out[i] != '0') { | |
return out; | |
} | |
i++; | |
} | |
return "0"; | |
} | |
string add(string num1, string num2) { | |
int l1 = num1.length(); | |
int l2 = num2.length(); | |
string out = ""; | |
int carry = 0; | |
while(l1 > 0 || l2 > 0) { | |
l1 --; | |
l2 --; | |
int v1 = l1 >= 0 ? num1[l1] - '0' : 0; | |
int v2 = l2 >= 0 ? num2[l2] - '0' : 0; | |
int v3 = v1 + v2 + carry; | |
if(v3 > 9) { | |
carry = v3 / 10; | |
v3 -= 10; | |
} else { | |
carry = 0; | |
} | |
out.insert(out.begin(), v3 + '0'); | |
} | |
if(carry > 0) { | |
out.insert(out.begin(), carry + '0'); | |
} | |
return out; | |
} | |
}; | |
int main(int, char** args) { | |
auto m = new Solution(); | |
auto r1 = m->multiply("123", "456"); | |
auto r2 = m->multiply("923", "956"); | |
auto r3 = m->multiply("9133", "0"); | |
cout << "multiply 123 and 456 should be 56088 it is " << r1 << "\n"; | |
cout << "multiply 923 and 956 should be 882388 it is " << r2 << "\n"; | |
cout << "multiply 9133 and 0 should be 0 it is " << r3 << "\n"; | |
delete m; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment