-
Notifications
You must be signed in to change notification settings - Fork 2
/
q0043.c
86 lines (83 loc) · 2.24 KB
/
q0043.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//
// q0043.c
// LeetCode
//
// Created by NowOrNever on 22/10/2019.
// Copyright © 2019 DoubleL. All rights reserved.
//
#include "q0043.h"
#include "../common.h"
//43. Multiply Strings
//Medium
//
//840
//
//368
//
//Favorite
//
//Share
//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:
//
//The length of both num1 and num2 is < 110.
//Both num1 and num2 contain only digits 0-9.
//Both num1 and num2 do not contain any leading zero, except the number 0 itself.
//You must not use any built-in BigInteger library or convert the inputs to integer directly.
//Accepted
//181,730
//Submissions
//608,813
char* multiply(char* num1, char* num2) {
if ((strlen(num2) == 1 && num2[0] == '0') || (strlen(num1) == 1 && num1[0] == '0')) {
char *result = calloc(2, sizeof(char));
result[0] = '0';
return result;
}
#define Question43Len 110
char *result = calloc(Question43Len * 2, sizeof(char));
int resultReverse[Question43Len * 2];
memset(resultReverse, 0, sizeof(int) * Question43Len * 2);
long resultLen = 0;
for (long i = strlen(num2) - 1; i >= 0; i--) {
int extra = 0;
long offset = strlen(num2) - 1 - i;
int currentNumber = num2[i] - '0';
// printf("%c",num2[i]);
for (long j = strlen(num1) - 1; j >= 0; j--) {
resultReverse[offset] += (num1[j] - '0') * currentNumber + extra;
extra = resultReverse[offset] / 10;
resultReverse[offset] %= 10;
offset++;
}
if (extra) {
resultReverse[offset] = extra;
offset++;
}
if (resultLen < offset) {
resultLen = offset;
}
}
char *p = result;
for (long i = resultLen - 1; i >= 0 ; i--) {
*p++ = resultReverse[i] + '0';
}
return result;
}
int question43(){
char *num1 = "111111111";
char *num2 = "111111111";
// "9133","0"
char *result = multiply(num1, num2);
printf("\n the result of %s multiply %s is %s\n", num1, num2, result);
return 0;
}