patterncMinor
Adding two numbers, each digit as a single element of array
Viewed 0 times
eacharraynumbersaddingtwosingleelementdigit
Problem
After failing to answer an interview question, I went back home and coded the answer for my own improvement.
The questions was: Given two arrays containing a number, but with each element of the array containing a digit of that number, calculate the sum and give it in the same format.There must be no leading zeros in the resulting array.
My main concern is that I am being redundant with my logic, or that my code is not clear.
```
int sumOfTwo(int a1,int a2, int lengthOfA1, int lengthOfA2, int lengthDest) {
//I assume there is error checking for null pointers, etc.
int *answer;
int maxSize, minSize, diff;
int a1IsLongest = TRUE;
if(lengthOfA1 > lengthOfA2) {
maxSize = lengthOfA1;
minSize = lengthOfA2;
a1IsLongest = TRUE;
}
else {
maxSize = lengthOfA2;
minSize = lengthOfA1;
a1IsLongest = FALSE;
}
diff = maxSize - minSize;
answer = malloc(maxSize * sizeof(int));
int i, extraTen, result;
extraTen = 0;
*lengthDest = maxSize;
//printf("This is lengthDest: %d\n", *lengthDest);
for (i = maxSize-1; i >= 0; i--) {
//add numbers, check if bigger than 10
//check if arrays are of different sizes we want to access
//the end from each, so need to account for this.
if(diff == 0) {
//arrays are equal in size
result = a1[i] + a2[i] + extraTen;
extraTen = 0;
}
else{
//arrays are different sizes
if(! ((i - diff) = 10) {
//check if at beginning of array
if(i == 0) {
maxSize = maxSize + 1;
*lengthDest = maxSize;
//printf("This is lengthDest: %d\n", *lengthDest);
//overflowing, need to realloc
int temp = malloc(maxSize sizeof (int));
int j;
//copy old elements into new array
The questions was: Given two arrays containing a number, but with each element of the array containing a digit of that number, calculate the sum and give it in the same format.There must be no leading zeros in the resulting array.
My main concern is that I am being redundant with my logic, or that my code is not clear.
```
int sumOfTwo(int a1,int a2, int lengthOfA1, int lengthOfA2, int lengthDest) {
//I assume there is error checking for null pointers, etc.
int *answer;
int maxSize, minSize, diff;
int a1IsLongest = TRUE;
if(lengthOfA1 > lengthOfA2) {
maxSize = lengthOfA1;
minSize = lengthOfA2;
a1IsLongest = TRUE;
}
else {
maxSize = lengthOfA2;
minSize = lengthOfA1;
a1IsLongest = FALSE;
}
diff = maxSize - minSize;
answer = malloc(maxSize * sizeof(int));
int i, extraTen, result;
extraTen = 0;
*lengthDest = maxSize;
//printf("This is lengthDest: %d\n", *lengthDest);
for (i = maxSize-1; i >= 0; i--) {
//add numbers, check if bigger than 10
//check if arrays are of different sizes we want to access
//the end from each, so need to account for this.
if(diff == 0) {
//arrays are equal in size
result = a1[i] + a2[i] + extraTen;
extraTen = 0;
}
else{
//arrays are different sizes
if(! ((i - diff) = 10) {
//check if at beginning of array
if(i == 0) {
maxSize = maxSize + 1;
*lengthDest = maxSize;
//printf("This is lengthDest: %d\n", *lengthDest);
//overflowing, need to realloc
int temp = malloc(maxSize sizeof (int));
int j;
//copy old elements into new array
Solution
I see some things that may help you improve your code.
Use
The
Show all required headers
The code uses
Use
This code contains lines like this:
However, there are already
Fix formatting
The indentation is not consistent, and in one case, there's a space between
Simplify your code
There are a number of extra variables and comparisons to determine which array is larger. Why not instead simply assume that
Assume a convenient data structure unless otherwise specified
It's not clear whether you were told that the data structure had the least significant or most significant digit first or whether either had leading zeroes. The most convenient data structure would actually be to store the data with the least significant digit first, as I'll demonstrate in the next suggestion.
Allocate memory only once
The current code allocates some memory and then may allocate again if more is needed, copying the elements from the old to the new array. There are several strategies that would allow you to allocate memory only once.
The first is to note that the maximum additional memory required would be exactly one
The second would be to determine if a carry will be required and allocate space accordingly. One way to do that would be to make two passes through the data.
The other possibility is to adjust the allocated length after calculation. This could be done very simply using the
Prefer "less expensive" to "more expensive" operations
If the digits are decimal digits (not stated, but assumed), then the largest possible sum will be 9+9=18, so the largest possible carry value is 1. If the resulting value is greater than 10, the current code uses this code:
The
Check for memory allocation failure
Calls to
Putting it all together
Here's a version incorporating all of these suggestions:
Test harness
```
#include
#include
#include
#include
// sumOfTwo() goes here
void printnum(const int *num, int len, int desiredlen)
{
for (; desiredlen > len; --desiredlen) {
printf(" ");
}
for (num += len - 1; len; --len, --num) {
printf("%u", *num);
}
puts("");
}
struct number {
int len;
int digits[5];
};
struct test {
struct number n1, n2, expected;
};
struct test tests[] = {
{ { 1, {9} }, { 1, {9} }, { 2, { 8, 1 } }},
{ { 3, {8, 9, 9}}, {2, {1, 9}}, { 4, { 9, 8, 0, 1}}},
{ { 3, {8, 9, 9}}, {3, {0, 0, 1}}, { 4, {8, 9, 0, 1}}},
};
bool doTest(const struct test* t) {
int lengthDest;
int *answer = sumOfTwo(t->n1.digits, t->n2.digits, t->n1.len, t->n2.len, &lengthDest);
printnum(t->n1.digits, t->n1.len, 5);
printnum(t->n2.digits, t->n2.len, 5);
puts("-----");
printnum(answer, lengthDest, 5);
if (lengthDest != t->expected.len) {
free(answer);
return false;
}
for (int i = 0; i expected.digits[i] != answer[i]) {
free(answer);
return false;
}
}
free(answer);
return true;
}
int main()
{
int testcount = sizeof(tests) / size
Use
const where practicalThe
sumOfTwo() function doesn't (and probably shouldn't) modify the passed integer arrays, so they should be declared const.Show all required headers
The code uses
malloc and free but the code does not show a the required include file. For code reviews (and job interviews!), it's best to list the required includes. This code needs only:#include Use
stdbool.h when neededThis code contains lines like this:
int a1IsLongest = TRUE;However, there are already
bool types and values supported in the stdbool.h header. Prefer those to non-standard types and values. The line above would then be:bool a1IsLongest = true;Fix formatting
The indentation is not consistent, and in one case, there's a space between
else and the following { but in other case there's no space. Which convention you use is less important than choosing one and following it consistently.Simplify your code
There are a number of extra variables and comparisons to determine which array is larger. Why not instead simply assume that
a1 is longer than or equal in length to a2 and then make that true? It would simplify the code a lot. For example, one could start the code this way:if (lengthOfA1 < lengthOfA2) {
// swap the arguments to ensure a1 is not shorter than a2
int *temp = a1;
int templen = lengthOfA1;
a1 = a2;
lengthOfA1 = lengthOfA2;
a2 = temp;
lengthOfA2 = templen;
}Assume a convenient data structure unless otherwise specified
It's not clear whether you were told that the data structure had the least significant or most significant digit first or whether either had leading zeroes. The most convenient data structure would actually be to store the data with the least significant digit first, as I'll demonstrate in the next suggestion.
Allocate memory only once
The current code allocates some memory and then may allocate again if more is needed, copying the elements from the old to the new array. There are several strategies that would allow you to allocate memory only once.
The first is to note that the maximum additional memory required would be exactly one
int and to simply allocate enough space for that, with the understanding that there would be, potentially, a leading zero in the answer.The second would be to determine if a carry will be required and allocate space accordingly. One way to do that would be to make two passes through the data.
The other possibility is to adjust the allocated length after calculation. This could be done very simply using the
realloc function. Prefer "less expensive" to "more expensive" operations
If the digits are decimal digits (not stated, but assumed), then the largest possible sum will be 9+9=18, so the largest possible carry value is 1. If the resulting value is greater than 10, the current code uses this code:
answer[i] = result % 10;The
% operator typically does a division which is computationally expensive on many platforms. Better is to simply use subtraction and the fact that the carry can only possibly be equal to 1 or 0.if (result >= 10) {
result -= 10;
carry = 1;
}Check for memory allocation failure
Calls to
malloc can fail. Robust code should check for that and handle the out-of-memory condition appropriately.Putting it all together
Here's a version incorporating all of these suggestions:
int *sumOfTwo(const int *a1, const int *a2, int lengthOfA1, int lengthOfA2, int *lengthDest)
{
if (lengthOfA1 = 10) {
val -= 10;
carry = 1;
} else {
carry = 0;
}
*digit = val;
}
return result;
}Test harness
```
#include
#include
#include
#include
// sumOfTwo() goes here
void printnum(const int *num, int len, int desiredlen)
{
for (; desiredlen > len; --desiredlen) {
printf(" ");
}
for (num += len - 1; len; --len, --num) {
printf("%u", *num);
}
puts("");
}
struct number {
int len;
int digits[5];
};
struct test {
struct number n1, n2, expected;
};
struct test tests[] = {
{ { 1, {9} }, { 1, {9} }, { 2, { 8, 1 } }},
{ { 3, {8, 9, 9}}, {2, {1, 9}}, { 4, { 9, 8, 0, 1}}},
{ { 3, {8, 9, 9}}, {3, {0, 0, 1}}, { 4, {8, 9, 0, 1}}},
};
bool doTest(const struct test* t) {
int lengthDest;
int *answer = sumOfTwo(t->n1.digits, t->n2.digits, t->n1.len, t->n2.len, &lengthDest);
printnum(t->n1.digits, t->n1.len, 5);
printnum(t->n2.digits, t->n2.len, 5);
puts("-----");
printnum(answer, lengthDest, 5);
if (lengthDest != t->expected.len) {
free(answer);
return false;
}
for (int i = 0; i expected.digits[i] != answer[i]) {
free(answer);
return false;
}
}
free(answer);
return true;
}
int main()
{
int testcount = sizeof(tests) / size
Code Snippets
#include <stdlib.h>int a1IsLongest = TRUE;bool a1IsLongest = true;if (lengthOfA1 < lengthOfA2) {
// swap the arguments to ensure a1 is not shorter than a2
int *temp = a1;
int templen = lengthOfA1;
a1 = a2;
lengthOfA1 = lengthOfA2;
a2 = temp;
lengthOfA2 = templen;
}answer[i] = result % 10;Context
StackExchange Code Review Q#123032, answer score: 5
Revisions (0)
No revisions yet.