3
\$\begingroup\$

I was lucky enough to stumble into this task during a job interview. I was gently guided to use string reversals and a few other things to speed up my process. I kept thinking that I wouldn't have done it the way I was coached. It bothered me enough that I went home and coded up my version.

How could I improve this code?

* EDIT * added a size_t for carry. Reduced the number of calles of strlen().

Rules:

  • Program must be in C
  • Can't use atoi, and only basic types
  • Must be able to add arbitrarily large numbers
  • Output must be a string

Example usage:

addbig 12345678901234567891234567891234567890123456789123456789  9876543210987654321098765432198765432109876543210987654321

Here's the code I came up with:

#include <stdio.h>   // printf
#include <stdlib.h>  // malloc
#include <string.h>  // strlen


char * addStrings(char* string1, char* string2) {
  char *maxString = string1;
  char *minString = string2;

  // Override our larger if we were wrong.
  if (strlen(string1) < strlen(string2)) {
    maxString = string2;
    minString = string1;
  }

  int maxSize =  strlen(maxString);

  // Allocate enough storage to include our carry and the null char at the end.
  char * myResult = malloc(maxSize + 2);

  // Null terminate the string
  myResult[maxSize + 1] = 0;

  size_t carry = 0;
  int mindex = strlen(minString) - 1;

  char x = 0;

  // One loop.  Avoid -std=c99 flag
  int i = maxSize - 1;
  for (; i >= 0; i--) {
    // Default our char
    x = maxString[i] - '0';
    // We still have something left to add.
    if (mindex >= 0){
      x = x + (minString[mindex] - '0');
      mindex--;
    } 

    if (carry) x++;

    if (x >= 10) {
      x -= 10;
      carry = 1;
    } else {
      carry = 0;
    }

    myResult[i + 1] = x + '0';
  }
  // Take care of any leftover carry.
  if (carry) myResult[0] = '1';

  return myResult;
}  // END addStrings()



int main(int argc, char **argv) {
  if (argc < 2) {
    printf("Usage: %s num1 num2\n", argv[0]);
    printf("Utility for big numbers.");
    printf("Adds num1 to num2, for any length of numbers.\n");
    return 1;
  }

  char * result = addStrings(argv[1], argv[2]);

  // Removing the initial space allocated by storage if we didn't overflow
  printf("%s\n", (result[0] == ' ') ? result + 1 : result);

  if (result) {
    free(result);
    return 0;
  }

  // Returned an error state, memory not freed.
  return -1;
}
\$\endgroup\$
  • \$\begingroup\$ You only need 2 strlen calls, not 4. \$\endgroup\$ – Pieter Witvoet May 13 '16 at 7:02
2
\$\begingroup\$

Function Error

  1. What is myResult[0] when carry == 0?

    if (carry) myResult[0] = '1';
    

Improvements

  1. As code is not changing the the contents of the string, use const for potential compiler optimization and clarity to reviewers that code is in fact not changing the characters.

    // char * addStrings(char* string1, char* string2) 
    char * addStrings(const char* string1, const char* string2) 
    
  2. Code that allocates memory should clearly say that as a comment and/or function name.

    // Returns an allocated string representing the sum of .... 
    char * addStrings(
    // or
    char * addStrings_alloc(
    
  3. Really big strings can exceed length INT_MAX. Use size_t for indexing arrays and string lengths. size_t is the return type of strlen().

    // int maxSize =  strlen(maxString);
    size_t maxSize =  strlen(maxString);
    
    // int i = maxSize - 1;
    // for (; i >= 0; i--) {
    size_t i;
    for (i = maxSize; i > 0; ) {
      i--;
    
  4. Check the return value of malloc()

    char * myResult = malloc(maxSize + 2);
    if (myResult == NULL) return NULL;
    
  5. No need for carry to besize_t`.

    // size_t carry = 0;
    int carry = 0;
    
  6. No provision for - numbers. (or ones with a leading '+')

  7. No provision for trimming leads '0' in answer with input like addStrings("007", "007")

  8. No provision for non-digits as in addStrings("x", "007")

  9. Simplification

       // x = maxString[i] - '0';
       // if (carry) x++;
       x = maxString[i] - '0' + carry;
    
  10. Below processing should have happened in the function.

      // Removing the initial space allocated by storage if we didn't overflow
      ... (result[0] == ' ') ? result + 1 : result)
    

Minor

  1. Nomenclature. size is the size need for the array. length is the length of the string (not counting the null character). Suggest maxLength.

    // int maxSize =  strlen(maxString);
    int maxLength =  strlen(maxString);
    
  2. Why the comment? Seems unneeded // Avoid -std=c99 flag

  3. No provision for NULL input addStrings(NULL, "007") - but then NULL is not a valid string. For an interview question, I'd at least suggest that inputs may need sanitizing before use.

  4. Style: Even single if() are easier to debug/maintain with {}

    // if (carry) myResult[0] = '1';
    if (carry)  {
      myResult[0] = '1';
    }
    
  5. Test driver simplification. free(NULL) is OK.

    // if (result) {
    //  free(result);
    //  return 0;
    //}
    free(result); 
    
  6. Test driver function error - off by 1

    // if (argc < 2) {
    if (argc < 3) {
    // or better 
    if (argc != 3) {
    
  7. I'd expect code to be tested and give a reasonable (or a least defined) result with addStrings("", "7") and addStrings("", "")

\$\endgroup\$
  • \$\begingroup\$ Seriously great response! #1 was a bug I introduced late last night after I core dumped freeing the memory allocated in the function. Apparently the pointer arithmetic loses the malloc accounting details, which is why #10 is that way. Why did you structure the size_t for loop that way? \$\endgroup\$ – MrMowgli May 12 '16 at 20:30
  • \$\begingroup\$ @MrMowgli size_t is some unsigned type. size_t i = maxSize - 1; for (; i >= 0; i--) { is always true - infinite loop. \$\endgroup\$ – chux - Reinstate Monica May 12 '16 at 20:44
  • \$\begingroup\$ Got it. But why break out the i--? \$\endgroup\$ – MrMowgli May 12 '16 at 20:58
  • \$\begingroup\$ @MrMowgli The i-- is just the first statement in the for loop. Could use for (i = maxSize; i-- > 0; ) { ... } 6.00001 or half-a-dozen of the other. It is a style issue. \$\endgroup\$ – chux - Reinstate Monica May 12 '16 at 21:15
  • \$\begingroup\$ Rather why not --i in the loop? \$\endgroup\$ – MrMowgli May 12 '16 at 21:15
0
\$\begingroup\$

Malloc allocates uninitialized memory. You need to memset it unless you enjoy dealing with undefined behavior.

char * myResult = malloc(maxSize + 2);
memset(myResult, 0, maxSize + 2);
\$\endgroup\$
  • 1
    \$\begingroup\$ Aside from bug noted Function Error #1 the memset() is not needed. When zero filling is needed, simple to use calloc(). \$\endgroup\$ – chux - Reinstate Monica May 12 '16 at 20:46
  • \$\begingroup\$ No need to. All the requested memory is initialized later anyway. \$\endgroup\$ – David Foerster May 13 '16 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.