-
Notifications
You must be signed in to change notification settings - Fork 0
/
factorial.c
169 lines (156 loc) · 4.02 KB
/
factorial.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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "math.h"
#include "ctype.h"
int result_size;
int number_size;
/* Take user input and process depending on cases below
Case 0: Input is a positive number with no leading 0s
Convert input into reverse order array of its digits.
Case 1: Input is positive but has leading 0s.
Convert input into reverse order array of its digits.
Once input is converted into the array number leading 0s are stripped off.
Case 2: Input is 0 or many 0s.
Convert input into reverse order array of its digits.
All 0s will then be stripped off leaving an empty output with number_size = 0.
Case 3: Input is a negative number.
Each char of the input is checked with isdigit().
"-" will not pass isdigit().
Set number_size to -1 to handle output in main().
Case 4: Input contains none digit numbers.
Acts the same as Case 3. */
int* array_convert()
{
char number[400];
scanf("%s", number);
number_size = strlen(number);
int* ptr = calloc(number_size, sizeof(int));
for (int i = (number_size - 1); i > -1; i--)
{
if (isdigit(number[i]) > 0)
{
ptr[number_size - 1 - i] = (int)(number[i] - '0');
}
else
{
printf("ERROR: Input is not a positive integer or 0\n");
number_size = -1;
return ptr;
}
}
// Get rid of leading 0s in input
for (int i = (number_size - 1); i > -1 ; i--)
{
if (ptr[i] == 0)
{
(number_size)--;
}
else
{
break;
}
}
ptr = realloc(ptr, (number_size * sizeof(int)));
return ptr;
}
// Subracts 1 from array number using long subtraction method
int* number_subtract(int* num)
{
num[0]--;
for (int i = 0; i < number_size - 1; i++)
{
if (num[i] < 0)
{
num[i] = 9;
num[i+1]--;
}
else
{
return num;
}
}
//check if subtractions left a leading 0 and get rid of it
if (num[number_size - 1] == 0)
{
number_size--;
num = realloc(num, (number_size * sizeof(int)));
}
return num;
}
// Multiplies two array numbers using column multiplication method
int* number_multiply(int* num1,int digits_num1, int* num2, int digits_num2)
{
// Determine maximum size of result
result_size = digits_num1 + digits_num2;
int* result = (int*)calloc(result_size, sizeof(int));
for (int i = 0; i < digits_num2; i++)
{
for (int j = 0; j < digits_num1; j++)
{
result[i+j] += num2[i] * num1[j];
// Check whether to carry over and do so if needed
int mod = floorf(result[i+j] / 10);
result[i+j+1] += mod;
result[i+j] -= 10 * mod;
}
}
//Get rid of leading 0s
for (int i = (result_size - 1); i > -1 ; i--)
{
if (result[i] == 0)
{
(result_size)--;
}
else
{
break;
}
}
result = realloc(result, (result_size * sizeof(int)));
free(num2);
return result;
}
int main()
{
// Take in user input and convert to array number_ptr
printf("Enter a number to factorial: ");
int* number_ptr = array_convert();
int* result_ptr;
// Check what case the input satified
if (number_size == -1)
{
// Input was not an allowed number
return 0;
}
else if (number_size == 0)
{
// Input was 0
result_ptr = malloc(sizeof(int));
result_size = 1;
result_ptr[0] = 1;
}
else
{
/* Input was an allowed number.
Copy number into result then take away 1 from number and begin loop which
sucessively multiplies result by number and takes 1 away from number until
number is 0 to calculate the factorial. */
result_ptr = malloc(number_size * sizeof(int));
result_size = number_size;
memcpy(result_ptr, number_ptr, number_size * sizeof(int));
number_ptr = number_subtract(number_ptr);
while (number_size > 0)
{
result_ptr = number_multiply(number_ptr, number_size, result_ptr, result_size);
number_ptr = number_subtract(number_ptr);
}
}
//Print resulting factorial
for (int i = (result_size - 1); i > -1; i--)
{
printf("%d", result_ptr[i]);
}
printf("\nDigits = %d\n", result_size);
free(number_ptr);
}