@@weaponkid1121 did not go through with it. they wanted me to interview for SRE/SWE instead and as well as move to the coast. I would rather be remote without on-call, so not worth my time right now.
@@Hank-ry9bz because you are obviously capable of converting strings to integers and then multiplying them. This question has zero use in the real world. And if you want to talk about the benefits that come from finding a different non-trivial solution, you can easily find those benefits elsewhere
def multiplyStrings(num1: str, num2: str) -> str: if num1 == "0" or num2 == "0": return "0" # Reverse strings for easier index handling num1 = num1[::-1] num2 = num2[::-1] # Initialize an array to hold the results of multiplication product = [0] * (len(num1) + len(num2)) # Multiply each digit and accumulate the results for i in range(len(num1)): for j in range(len(num2)): product[i + j] += (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0')) # Handle carry product[i + j + 1] += product[i + j] // 10 product[i + j] %= 10 # Remove leading zeros from the result while len(product) > 1 and product[-1] == 0: product.pop() # Convert the product array back to a string return ''.join(map(str, product[::-1]))
because we need to calculate the div and mod after adding the new digit in~ that's why the first version doesn't work!! 👍 Thank you for the always-awesome video!!!
your explanation is nice. But, I dont really get the point of this problem, from leetcode. the problem itself is very loosely defined. The problem statement gives a serious constraint "do not use any built-in BigInteger library or convert the inputs to integer directly." But, we eventually have to convert each digit into integer using builtin int(); otherwise we need to write a multiplication table by hand. the solution provided by leetcode also use int() somehow.
basically they want you solve it without using predefined functions. This is a very common problem asked in interview as it only need elementary maths knoweldge. Also, in C/C++ there is no bigint class.
I see your point. It seems this question is multiplying a number by just adding up all the multiplications of the digits- which is the algorithm: but it seems kind of pointless because its not doing anything new.
@@ShubhamKumar-ex3nk I converted each of the strings to an int using ASCII and then multiplied, but the this way takes too much run time when the inputs are very long numers like "2222222222222222222222222222222222", why is NeetCode's way faster?
a lot of the so-called solutions on leetcode are actually cheats where it is a one liner where you convert to int, mult, then convert back. It is more interesting to avoid that even though it technically works, and challenge yourself. E.g, try to do it in other bases, binary, hex or make it work in general so base 7, whatever
I thought the point of this question was to implement Karatsuba's or some other purely typographical algorithm. However, doing something like that would require you to implement addition and maybe subtraction too which I am too lazy to do.
I dont think you can use type casting to int, you have to use a dict to map strings to integers. Otherwise you could have a one line solution: return str(int(num1) * int(num2))
@NeetCode - Shouldn't the carry digit also be after adding digit to res[i1+i2] , i.e. I think it should be res[i1+i2+1] = res[i1+i2] // 10 after the res[i1+i2]+=digit is calculated. e.g. if we have 278 x 4 ------- 312 So the final cdigit is 3 , only when we do 31//10 i.e. after adding digit which is 28+3(previous carry) Whereas if we do digit // 10 as shown in code, the final carry could be 28//10 = 2
I feel lines 12 to 14 can be rewritten like this to be more intuitive: res[i1+i2+1] += ((res[i1+i2] + digit) // 10) res[i1+i2] = (res[i1+i2] + digit) % 10
Great Solution @NeetCode ! I do have a question tho: My first intuition is to some how convert string to int, multiply, then convert back to string. Since the problem state "Note: You must not use any built-in BigInteger library or convert the inputs to integer directly", I use "ord()" to manipulate character by character in a string to get integer. Something like this class Solution: def multiply(self, num1: str, num2: str) -> str: if num1 == "0" or num2 == "0": return "0" int1 = 0 int2 = 0 # convert string to int for n in num1: int1 = int1 * 10 + (ord(n) - ord('0')) for n in num2: int2 = int2 * 10 + (ord(n) - ord('0')) int_res = int1 * int2 res = "" while int_res: remainder = int_res % 10 res = res + str(remainder) int_res = int_res // 10 return res[::-1] Is this cheating for an interview questions? Edit: nvm lol, int1 and int2 after conversion will be very big if we got a very big integer, although it does not state directly in the prompt but the interviewer can ban this approach. Python3 has no cap on max_int values, but Python2 or C++ has max values in int which can also cause overflow.
I also did the same as you. 1. I don't understand why NeetCode uses this whole algorithm if using the int and str functions are allowed and you could just return str(int(num1) * int(num2)) 2. why is NeetCode's algorithm faster than our way of converting the string to int using ASCII and then multiplying.
"You can not use any built-in library to convert the inputs directly into integers."- yeah but we still have to convert the digits to int so not completely true
Here is a much cleaner solution i just came up with: def multiply(self, num1: str, num2: str) -> str: res = 0 num1 = num1[::-1] num2 = num2[::-1] for i in range(len(num1)): for j in range(len(num2)): res += (int(num1[i]) * 10**i) * (int(num2[j]) * 10**j) return str(res)
Here is AI's response on this: "While this solution would work correctly for the given examples and produce the right answer, it doesn't meet all the problem constraints. The main issue is that it relies on Python's ability to handle large integers, which is precisely what the problem is asking you to implement manually. A valid solution should perform the multiplication digit by digit, handling the carries manually, and work with the numbers as strings throughout the process, only converting to integers at the single-digit level."
if we really could use int()...we could just do: class Solution: def multiply(self, num1: str, num2: str) -> str: num1, num2 = int(num1), int(num2) product = num1*num2 return str(product)
I think its less confusing to just reconstruct the integers, multiply, then stringify again, digits is a dictionary mapping str to num, "0" : 0, "1":1, etc 10^0 = 1, 10^1 = 10, etc. We use this to reconstruct number "123" => (3*1) + (2*10) + (1*100) = 123 def to_int(s): # manual conversion res = 0 for i in range(len(s)-1,-1,-1): num = digits[s[i]] i = len(s) - (i+1) # convert to power, 1st is 0th power, then 1st power res += (num * (10**i)) return res first = to_int(num1) second = to_int(num2) return str(first*second)
one question : i did it a different way in question its mention that we should not convert str to int directly (in sense of not using the int() function but i created a func using a different method (not using int() so can i do it that way Here's the code: pls correct me if its i am wrong and not abiding rules of problm(P.S : solution is accepted. Just asking whether it is alowd to do it like this ) class Solution: def multiply(self, num1: str, num2: str) -> str: def str_to_int(strnum: str): mul = 1 number = 0 for element in reversed(strnum): digit = (ord(element))%48 number = number + mul*digit mul = mul*10 return number return str((str_to_int(num1))*(str_to_int(num2)))
I think you are better off using a dict mapping strings to ints for each digit 0-9 and then multiplying by 1*10^n for obtaining an int. multiply the 2. then use % 10 and / 10 to extract each digit and then return the string (reversed) code in python3: def multiply(self, num1: str, num2: str) -> str: if num1 == "0" or num2 == "0": return "0" out = "" int1, int2 = 0, 0 intmult = 1 digits = {"0": 0, "1": 1, "2": 2, "3": 3, "4": 4, "5": 5, "6": 6, "7": 7, "8": 8, "9": 9} for i in range(len(num1) - 1, -1, -1): # back to front int1 += intmult*digits[num1[i]] intmult *= 10 intmult = 1 for i in range(len(num2) - 1, -1, -1): # back to front int2 += intmult*digits[num2[i]] intmult *= 10 intout = int1 * int2 while intout > 0: out += str(intout % 10) intout //= 10 return out[::-1]
These questions are so stupid. Getting ready for my Google interview and questions like these make me want to do horrible things.
same bestie same
How'd the Google interview go?
@@weaponkid1121 did not go through with it. they wanted me to interview for SRE/SWE instead and as well as move to the coast. I would rather be remote without on-call, so not worth my time right now.
in what way are they stupid?
@@Hank-ry9bz because you are obviously capable of converting strings to integers and then multiplying them. This question has zero use in the real world. And if you want to talk about the benefits that come from finding a different non-trivial solution, you can easily find those benefits elsewhere
Can't get over the fact that I forgot how to do multiplication by hand...
I would sadly never be able to figure this out in an interview on the spot...hah great explanation though
This is such an elegant solution and explanation. Thank you.
def multiplyStrings(num1: str, num2: str) -> str:
if num1 == "0" or num2 == "0":
return "0"
# Reverse strings for easier index handling
num1 = num1[::-1]
num2 = num2[::-1]
# Initialize an array to hold the results of multiplication
product = [0] * (len(num1) + len(num2))
# Multiply each digit and accumulate the results
for i in range(len(num1)):
for j in range(len(num2)):
product[i + j] += (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
# Handle carry
product[i + j + 1] += product[i + j] // 10
product[i + j] %= 10
# Remove leading zeros from the result
while len(product) > 1 and product[-1] == 0:
product.pop()
# Convert the product array back to a string
return ''.join(map(str, product[::-1]))
Excellent explanation over the youtube. It is one of the best youtube channels for DSA. I love it!
Actually the most important part which NeetCode himself metioned at 17:50 that missed will make this video's value reduce by half.
Hello Wilson, why can't we just return str(int(num1)* int(num2)) ? Like what is the bigger lesson here?
Leetcode be like: "There's a reason why u were taught these in elementary school. How dare you forget these" :)
because we need to calculate the div and mod after adding the new digit in~ that's why the first version doesn't work!! 👍 Thank you for the always-awesome video!!!
your explanation is nice. But, I dont really get the point of this problem, from leetcode. the problem itself is very loosely defined. The problem statement gives a serious constraint "do not use any built-in BigInteger library or convert the inputs to integer directly." But, we eventually have to convert each digit into integer using builtin int(); otherwise we need to write a multiplication table by hand. the solution provided by leetcode also use int() somehow.
basically they want you solve it without using predefined functions. This is a very common problem asked in interview as it only need elementary maths knoweldge. Also, in C/C++ there is no bigint class.
I see your point. It seems this question is multiplying a number by just adding up all the multiplications of the digits- which is the algorithm: but it seems kind of pointless because its not doing anything new.
@@ShubhamKumar-ex3nk I converted each of the strings to an int using ASCII and then multiplied, but the this way takes too much run time when the inputs are very long numers like "2222222222222222222222222222222222", why is NeetCode's way faster?
a lot of the so-called solutions on leetcode are actually cheats where it is a one liner where you convert to int, mult, then convert back. It is more interesting to avoid that even though it technically works, and challenge yourself. E.g, try to do it in other bases, binary, hex or make it work in general so base 7, whatever
Great arrangement for the code and explanation.
I thought the point of this question was to implement Karatsuba's or some other purely typographical algorithm. However, doing something like that would require you to implement addition and maybe subtraction too which I am too lazy to do.
Hi NeetCode. I can use ascii code to convert right ?
You can use lstrip('0') instead of while loop to remove 0's after you convert it to a string btw
I dont think you can use type casting to int, you have to use a dict to map strings to integers. Otherwise you could have a one line solution:
return str(int(num1) * int(num2))
No bro this solution won't work num1 or num2 maybe size of long long int but in the problem u can't use bigint library
nums1 and nums2 are strings. How did you multiply two strings without converting them into int first?
can we use the ord function or not allowed?
very informative!
Wonderful explanation ❤️
@NeetCode - Shouldn't the carry digit also be after adding digit to res[i1+i2] , i.e. I think it should be res[i1+i2+1] = res[i1+i2] // 10 after the res[i1+i2]+=digit is calculated.
e.g. if we have
278 x
4
-------
312
So the final cdigit is 3 , only when we do 31//10 i.e. after adding digit which is 28+3(previous carry)
Whereas if we do digit // 10 as shown in code, the final carry could be 28//10 = 2
the 3 was calculated in the previous iteration and already stored in res for that index. thats why we are adding to res (+=) instead of assigning(=)
This is unnecessarily complex
well explained man!
you could have reduced the number of times you have to use reverse using slicing if you looped in reverse and and modifying index
Love the problem, but wish they would find a way to enforce the no-big-int requirement.
return str(int(num1)* int(num2)) ..........i felt so bad doing this way
Even me
We should note that the last value of res[i1+i2+1] could have double digit, but that's acceptable
Can someone please explain the last change he made to those three lines? It would be helpful.
The previous lines cause some digit to have tens place.
I feel lines 12 to 14 can be rewritten like this to be more intuitive:
res[i1+i2+1] += ((res[i1+i2] + digit) // 10)
res[i1+i2] = (res[i1+i2] + digit) % 10
Is the time complexity for this O(N * M)?
Initially I was baffled , without conversation to int how we are going to proceed but cleared in the end.
but he did convert each digit with int()
I really really hate these pointless string questions... Great explanation though
Hey nice video. Hope you solve above problem using divide and conquer and post it😅.
What a strange question. I just reimplemented multiplication. I think that is O(1) in space?
Except you're not allowed to use int(digit) to convert a number...
u can just make a map and the rest of the code is basically the same
key = char value = int
instead of int(num1[i1]) it would just be map[num1[i1]]
Great Solution @NeetCode ! I do have a question tho: My first intuition is to some how convert string to int, multiply, then convert back to string. Since the problem state "Note: You must not use any built-in BigInteger library or convert the inputs to integer directly", I use "ord()" to manipulate character by character in a string to get integer. Something like this
class Solution:
def multiply(self, num1: str, num2: str) -> str:
if num1 == "0" or num2 == "0":
return "0"
int1 = 0
int2 = 0
# convert string to int
for n in num1:
int1 = int1 * 10 + (ord(n) - ord('0'))
for n in num2:
int2 = int2 * 10 + (ord(n) - ord('0'))
int_res = int1 * int2
res = ""
while int_res:
remainder = int_res % 10
res = res + str(remainder)
int_res = int_res // 10
return res[::-1]
Is this cheating for an interview questions?
Edit: nvm lol, int1 and int2 after conversion will be very big if we got a very big integer, although it does not state directly in the prompt but the interviewer can ban this approach. Python3 has no cap on max_int values, but Python2 or C++ has max values in int which can also cause overflow.
I also did the same as you.
1. I don't understand why NeetCode uses this whole algorithm if using the int and str functions are allowed and you could just return str(int(num1) * int(num2))
2. why is NeetCode's algorithm faster than our way of converting the string to int using ASCII and then multiplying.
@@WaldoTheWombat You cant do that as theyve mentioned a note that You should not use built in BigInt Libraries..
Wonderful solution but this code isn't passing all the test cases.
Well i am commenting at the start of the video itself, can't we simply convert the strings into linked list and multiply and return their answer
C# Implementaiton for above code ( All test cases passed )
public class Solution
{
public string Multiply(string num1, string num2)
{
return AppHelper.Multiply(num1,num2);
}
}
public static class AppHelper
{
public static void ReverseString(ref string s1,ref string s2)
{
char[] charArray1 = s1.ToCharArray();
Array.Reverse(charArray1);
s1= new string(charArray1);
char[] charArray2 = s2.ToCharArray();
Array.Reverse(charArray2);
s2 = new string(charArray2);
}
public static string Multiply(string num1 ,string num2)
{
if (num1 == "0" || num2 == "0")
{
return "0";
}
List res = new List();
for(int k=0;k
Lol I understood the problem to not convert strings to ints at all, so I made product and addition lookup tables 🤦♂
even i have done the same.. felt so uncomfortable
Can we have a video on 790. Domino and Tromino Tiling .
"You can not use any built-in library to convert the inputs directly into integers."- yeah but we still have to convert the digits to int so not completely true
People forget , even a layman can use buildt in stuff to do everything
Python spoils people man
Here is a much cleaner solution i just came up with:
def multiply(self, num1: str, num2: str) -> str:
res = 0
num1 = num1[::-1]
num2 = num2[::-1]
for i in range(len(num1)):
for j in range(len(num2)):
res += (int(num1[i]) * 10**i) * (int(num2[j]) * 10**j)
return str(res)
You are using a int function bro..Which is wrong maybe..
Here is AI's response on this:
"While this solution would work correctly for the given examples and produce the right answer, it doesn't meet all the problem constraints. The main issue is that it relies on Python's ability to handle large integers, which is precisely what the problem is asking you to implement manually.
A valid solution should perform the multiplication digit by digit, handling the carries manually, and work with the numbers as strings throughout the process, only converting to integers at the single-digit level."
I hate this question with passion
what if res[i1+i2+1] >=10?
Loved it man! Could you make a video on 271 Encode and Decode Strings?
bro 271 is so easy why u wanted that specific problem
Thanks
my c++ solution without array and reversing step:
class Solution {
public:
string multiply(string num1, string num2) {
int n1 = num1.size();
int n2 = num2.size();
int n = n1 + n2;
int s = n - 1;
string ans = "";
for(int i = 0; i < n; i++) ans += "0";
for(int i = n1 - 1; i >= 0; i--) {
int carry = 0;
for(int j = n2 - 1; j >= 0; j--) {
int prod = (ans[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0') + carry;
ans[i + j + 1] = prod % 10 + '0';
carry = prod / 10;
}
ans[i] = ((ans[i] - '0') + carry) + '0';
}
for(int i = 0; i < ans.length(); i++)
if(ans[i] != '0') return ans.substr(i, ans.length());
return "0";
}
};
what is the complexity of this?
if we really could use int()...we could just do:
class Solution:
def multiply(self, num1: str, num2: str) -> str:
num1, num2 = int(num1), int(num2)
product = num1*num2
return str(product)
Thanks:)
This is difficult... math algorithms ugh
why didn't we used -> return int(s1)*int(s2) instead???
This is very smart but the question is questionable at best
I think its less confusing to just reconstruct the integers, multiply, then stringify again,
digits is a dictionary mapping str to num, "0" : 0, "1":1, etc
10^0 = 1, 10^1 = 10, etc. We use this to reconstruct number
"123" => (3*1) + (2*10) + (1*100) = 123
def to_int(s): # manual conversion
res = 0
for i in range(len(s)-1,-1,-1):
num = digits[s[i]]
i = len(s) - (i+1) # convert to power, 1st is 0th power, then 1st power
res += (num * (10**i))
return res
first = to_int(num1)
second = to_int(num2)
return str(first*second)
Description says Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.
@@jeffkalltheway very right, guess I missed that somehow
return str(int(num1)*int(num2))
beats 90% in runtime and 80 % in memory
Are you blind ?
Sorry but you shouldnt use any kind of built-in type casting methods. It's clearly mentioned in note in the problem description
Awful problem
one question :
i did it a different way in question its mention that we should not convert str to int directly (in sense of not using the int() function but i created a func using a different method (not using int() so can i do it that way Here's the code:
pls correct me if its i am wrong and not abiding rules of problm(P.S : solution is accepted. Just asking whether it is alowd to do it like this )
class Solution:
def multiply(self, num1: str, num2: str) -> str:
def str_to_int(strnum: str):
mul = 1
number = 0
for element in reversed(strnum):
digit = (ord(element))%48
number = number + mul*digit
mul = mul*10
return number
return str((str_to_int(num1))*(str_to_int(num2)))
return str(int(num1)*int(num2)) ?
Yep.... hahaha
Nice solution 😊
Absolutely hate this problem
I think you are better off using a dict mapping strings to ints for each digit 0-9 and then multiplying by 1*10^n for obtaining an int. multiply the 2. then use % 10 and / 10 to extract each digit and then return the string (reversed)
code in python3:
def multiply(self, num1: str, num2: str) -> str:
if num1 == "0" or num2 == "0":
return "0"
out = ""
int1, int2 = 0, 0
intmult = 1
digits = {"0": 0, "1": 1, "2": 2, "3": 3, "4": 4, "5": 5, "6": 6, "7": 7, "8": 8, "9": 9}
for i in range(len(num1) - 1, -1, -1):
# back to front
int1 += intmult*digits[num1[i]]
intmult *= 10
intmult = 1
for i in range(len(num2) - 1, -1, -1):
# back to front
int2 += intmult*digits[num2[i]]
intmult *= 10
intout = int1 * int2
while intout > 0:
out += str(intout % 10)
intout //= 10
return out[::-1]
First condition is wrong
if u dont wanna use int function
use
digit = Mmap[num1[i1]] * Mmap[(num2[i2])]
where Mmap mapes every char 1-9 to it's corresponding integer.