Learn-dsa..in 30 days!



























CC-13 : Multiply 2 numbers.

Description:

Given input Strings str1 and str2 which represents integer numbers, we need to multiply the same and return the result. Str1 and str2 can be positive or negative numbers, but do not contain decimals.

Test cases and expected outputs:

Input Parameters Expected outputs
str1="6";
str2="-5639"; 		-033834
str1="6890";
str2="5639"; 		38852710
str1="4328";
str2="-72"; 		-0311616
str1="4328";
str2="-0"; 		-000000
str1="0";
str2="-0"; 		-000

Pseudocode:

The java method should accept following input parameters: str1 (String) and str2(String).
Initialize int variable resLen to sum of lengths of str1 and str2.
Initialize an int array resRow with length resLen to store the intermediate and final result of the multiplication of str1 and str2.
Initialize an int array currRow with length resLen to store the intermediate result of the multiplication of one integer of str2 with str1.
Initialize int variable s2Pos to 0. We will use this to left offset result of every consecutive multiplication of str2’s integers with str1’s integers just as we do in manual multiplication.
Initialize int variable carry to 0. We will use it to store carry value whenever a column of numbers is added.
Initialize variable currIdx to 0. We will use this index while storing results of current multiplication to currRow.
Summary Algorithm: Follow same steps that are done while doing manual multiplication. Start from left of str2, extract the leftmost integer and multiply it by all integers in str2 starting from left most integer of str2. Store the left integer of result of multiplication in currRow. Store right integer of result of multiplication in carry and add it result of next multiplication of left most integer of str2 with next integer of str1. After multiplication of leftmost number of str2 and all numbers of str1, add currRow and resRow. Now repeat above steps with second last leftmost integer of str2 and all integers of str1. Keep repeating above steps till all integers of str2 are multiplied with all integers str1 one by one. Convert restRow to a String resStr. Check negative sign of str1 and str2 and accordingly assign negative sign to resStr. Return resStr as it the result of multiplication of str1 and str2.
Detailed Algorithm:
Iterate through str2 using for loop with idx2 as loop variable starting with str2.length() and decrement idx2 till we reach 0. This way we will traverse str2 from left and use the str2 integers to multiply with str1 integers:
Set currIdx=currRow.length-1.
Initialize currRow to 0s.
Using for loop, move currIdx left by count of s2Pos. This is done to left offset result of every consecutive multiplication of str2’s integers with str1’s integers just as we do in manual multiplication.
Next, Iterate through str1 using for loop with idx1 as loop variable starting with str1.length() and decrements idx1 till we reach 0. This way we will traverse str1 from left and can multiply current integer from str2 with all integers from str1 one by one:
Set int variable mult = str2.charAt(s2idx) * str1(s1idx) + carry.
Note: convert the characters into integers before multiplying above!!
Set currRow[currIdx]=mult % 10, this will save leftmost digit of mult to currRow[currIdx].
Set carry= mult /1 0, this will store the right digit of mult to carry.
Decrement currIdx by 1.
When above inner loop completes:
Set currRow[currIdx] to carry.
Add corresponding integers in resRow and currRow and store result of addition again in resRow.
Increment s2Pos by 1.
Once outer loop completes, resRow contains result of multiplication of integers in str1 and str2 (except handling of –/ negative signs).
Using StringBuilder convert resRow into String restStr.
Str1 or str2 could contain – negative sign. We need to handle this as follows:
If any one (only) of str1 or str2 start with a negative sign, append negative sign to start of resStr.
If both str1 and str2 do *not* start with negative sign, no need to add negative sign to resStr.
If both str1 and str2 *start* with negative sign, no need to add negative sign to resStr.
Now resStr contains the result of multiplication of integers in str1 and str2. Return resStr.

Code:

public String stringMultiply(String str1, String str2) {
	int resLen=str1.length()+str2.length();
	int[] resRow=new int[resLen];
	int[] currRow=new int[resLen];
	int s2Pos=0; int carry=0; int currIdx=0;
	for (int idx2=str2.length()-1; idx2 >=0; idx2--) {
		if (str2.charAt(idx2)=='-') continue;
		carry=0;
		currIdx=currRow.length-1;
		currRow=new int[resLen];
		for (int zIdx=0; zIdx < s2Pos; zIdx++) {
			currIdx--;
		}
		for (int idx1=str1.length()-1; idx1 >=0; idx1--) {
			if (str1.charAt(idx1)=='-') continue;
			int mult=(str2.charAt(idx2)-'0')*(str1.charAt(idx1)-'0')+carry;
			currRow[currIdx]=mult%10;
			carry=(int) mult/10;
			currIdx--;
		}
		currRow[currIdx]=carry;
		resRow=addRows(resRow, currRow);	
		s2Pos++;
	}
	StringBuilder sb=new StringBuilder();
	for (int idx=0; idx < resRow.length; idx++) {
		sb.append(resRow[idx]);
	}
	String resStr=sb.toString();
	char isNeg=' ';
		if (str1.charAt(0)=='-' && str2.charAt(0)=='-') {
		isNeg=' '; 
	}else {
		if (str1.charAt(0)=='-' || str2.charAt(0)=='-') {
		isNeg='-';
		}
	}
	resStr=isNeg+resStr;
 return resStr;
}

public int[] addRows(int[] resRow, int[] currRow) {
	int[] addedRow=new int[resRow.length];
	int carry=0;
	for (int idx=resRow.length-1; idx>=0; idx--) {
		addedRow[idx]=(resRow[idx]+currRow[idx]+carry)%10;
		carry=(int)(resRow[idx]+currRow[idx]+carry)/10;
	}	
	return addedRow;
}

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us