Deficient Numbers

Question

I have found the following interesting challenge on the web:

Deficient Numbers
A number is considered deficient if the sum of its factors is less than twice that number.
For example: 10 is a deficient number because its factors are 1, 2, 5, 10 and their sum is 1 + 2 + 5 + 10 = 18 which is less than 10 * 2 = 20.
Challenges
Easy level: write a program to verify whether a given number is deficient or not.
Medium level: write a program to find all the deficient numbers in a range.
Hard level: given a number, write a program to display its factors, their sum and then verify whether it's deficient or not.

I implemented it in C:

#include <stdlib.h>
#include <stdio.h>
#define DEBUG 1

/*
  XXX EASY-OPTION IMPLEMENTATION
  A list data structure is used to store the factors of a given number.
  A simple boolean-like data type is then returned by the main isDeficient function.
*/

typedef enum bool bool;
enum bool {
  false, true
};

typedef struct ListElem ListElem;
struct ListElem {
    int value;
    ListElem* next;
};

typedef struct List List;
struct List {
  ListElem* head;
  int length;
};

List* listInit() {
  List* list = (List*) malloc(sizeof(List));
  list->head = NULL;
  list->length = 0;
  return list;
}

ListElem* listAppend(List* list, int elem) {
  ListElem* newHead = (ListElem*) malloc(sizeof(ListElem));
  newHead->value = elem;
  newHead->next = list->head;
  list->head = newHead;
  list->length++;
  return newHead;
}

void listPrint(List* list) {
  ListElem* head = list->head;
  printf("list > ");
  do {
    printf("%i ", head->value);
    head = head->next;
  } while (head != NULL);
  printf("\n");
}

void listSort(List* list) {
  int inactive = 0, debug = 0;
  while (inactive < list->length - 1) {
    inactive = 0;
    ListElem* previous = NULL;  // Initialise pointers...
    ListElem* current = list->head;
    ListElem* next = list->head->next;
    for (int i = 0; i < list->length - 1; i++) {
      if (current->value > next->value) {
        if (i != 0)
          previous->next = next;
        current->next = next->next;
        next->next = current;
        if (i == 0) // Update list head...
          list->head = next;
        inactive = 0;
        previous = next;
        next = current->next;
      } else {
        inactive++;
        previous = current;
        current = next;
        next = next->next;
      }
    }
    debug += list->length - 1;
  }
#if DEBUG
  printf("Debug info: sorting toke %i iterations.\n", debug);
#endif
}

bool isInList(List* l, int elem) {
  ListElem* listElem = l->head;
  for (int i = 0; i < l->length; i++) {
    int value = listElem->value;
    if (value == elem)
      return true;
    listElem = listElem->next;
  }
  return false;
}

List* findFactors(int n) {
  List* factors = listInit();
  int tempRes = 0;
  int debug = 1;
  listAppend(factors, 1);
  if (!(isInList(factors, n))) // Avoid duplicates only when n = 1...
    listAppend(factors, n);
  for (int d = 2; d <= n / 2; d++) { // The <= operator is necessary when n = 4 or the iterations don't start...
    if (!(n % d)) {
      tempRes = n / d;
      if (isInList(factors, tempRes))
        break;
      listAppend(factors, d);
      if (!(isInList(factors, tempRes))) // Avoid duplicate entries when the divisor and the result of the division are the same...
        listAppend(factors, tempRes);
    }
    debug++;
  }
#if DEBUG
  printf("Debug info: %i's factors found with %i iterations.\n", n, debug);
  listSort(factors);
  listPrint(factors);
#endif
  return factors;
}

int calculateSum(List* list) {
  int sum = 0;
  ListElem* listElem = list->head;
  for (int i = 0; i < list->length; i++) {
    sum += listElem->value;
    listElem = listElem->next;
  }
  return sum;
}

bool isDeficient(int n) {
  List* f = findFactors(n);
  if (calculateSum(f) < 2 * n)
    return true;
  return false;
}

// XXX MEDIUM-OPTION IMPLEMENTATION

List* findDeficients(int min, int max) {
  List* deficients = listInit();
  for (int i = min; i <= max; i++) {
    if (isDeficient(i))
      listAppend(deficients, i);
  }
  return deficients;
}

// XXX HARD-OPTION IMPLEMENTATION

int main(int argc, char* argv[]) {
  if (argc != 2) {
    printf("Error: arguments are not one!\n");
    return 0;
  }
  int n = atoi(argv[1]);
  List* facts = findFactors(n);
  printf("The factors of %i are:\n", n);
  listPrint(facts);
  int sum = calculateSum(facts);
  printf("Their sum is:\n%i\n", sum);
  if (sum < 2 * n)
    printf("%i IS deficient.\n", n);
  else
    printf("%i IS NOT deficient.\n", n);
  return 0;
}

What about it? In particular, I would like to ask you for a feedback about the List structure and the sorting function. Is their code readable and understandable? Could it be improved with regard to performance?

Answer 1

The algorithm:

1. Well, findFactors is far too inefficient. Better do a prime-factoring, and then create the list of all factors from that.

2. If you need to do enough prime-factorings, consider pre-calculating all candidate primes, be it during or before compilation or before use.

3. Only use a list if you have to: Using and when needed realloc-ing a dynamically-allocated array is far more efficient and simpler in most cases. And it allows you to rely on qsort() for sorting.

Your code:

1. Avoid over-long lines, as horizontal scrolling kills readability. Yes, your IDE might allow for longer lines without scrolling or auto-wrapping, but it still makes things difficult. Even if everyone used an IDE on a big screen and gave the code-window the full screen-width, it slows reading considerably.

2. If you use the preprocessor for configuration, allow overriding by pre-defining.
   This:

   #define DEBUG 1
   

   becomes

   #ifndef DEBUG
   #define DEBUG 1
   #endif
   

3. You might want to upgrade to C99, then you will have a true boolean type. If you don't, stay with an integer. Emulating a true boolean type with an enum instead is painful.

4. If you want to introduce a typedef-name for a struct- / enum-name, consider merging that:

   typedef struct ListElem ListElem;
   struct ListElem {
       int value;
       ListElem* next;
   };
   

   becomes:

   typedef struct ListElem {
       int value;
       struct ListElem* next;
   } ListElem;
   

5. Anyway, the customary name for a ListElem is ListNode, which though the same length avoids curious abbreviations.

6. "Do I cast the result of malloc?" No, we are writing C here.

7. Getting any resource, even memory, can fail. Handle it, don't ignore it.

8. Also, prefer sizeof expr over sizeof(TYPE), doing so couples size requested and the use of the memory, making errors less likely, whether at first writing or after re-factoring.

9. listAppend() is mis-named, it should be listPrepend(). I also wonder why it returns the new node, which the caller probably doesn't care about, and can easily and efficiently get anyways.

10. listPrint() has Undefined Behaviour for an empty list. findDeficients() for example can result in an empty list.

11. listSort() doesn't really have to re-order the nodes to sort the values. Not doing so allows for some simplification.

12. There is no reason to use the lists size to iterate over the whole list. That way, your code gets simpler and more efficient:

    bool isInList(List* l, int v) {
        for (ListElem* p = l->head; p; p = p->next)
            if (p->value == v)
                return true;
        return false;
    }
    

    The same holds for calculateSum().

13. If you have to choose one of two expressions, you should remember that's what the conditional operator cond ? true_exp : false_exp excells at.

14. Consider marking all internal functions static to avoid exporting the symbol and encourage inlining.

15. Please output diagnostic messages to stderr instead of stdout, so the caller can separate them easily.

16. The error-message for wrong use should explain proper use. argv[0] contains the program-name for that. Try to follow convention with your text.

Some comments about the challenge:

1. The second level is only harder than the first if you take advantage of efficiencies of scale, as you should.
2. The last level is only harder if you insist on sorted output, and didn't use any container earlier.

Answer 2

in main(), there is a call to calculateSum() then checking if the sum is < 2n, etc.

However, that same determination is made in the function: isDeficient()

for this:

typedef enum bool bool;
enum bool {
  false, true
};

you might want to use the header file: stdbool.h

ISO C forbids forward references to enums

regarding:

List* list = (List*) malloc(sizeof(List));

1) in C, the returned type is void*, which can be assigned to any pointer. Casting just clutters the code, making it more difficult to understand, debug, etc

2) the heap allocation functions: malloc calloc and realloc can fail, so should always check (!=NULL) the returned value to assure the operation was successful

The use of a linked list is 'overkill' Suggest a simple array

regarding:

    debug++;
}
#if DEBUG

using multiple symbols those only difference is capitalization can be very confusing (to the person reading the code) Suggest using unique names

for ease of readability and understanding: 1) Suggest using an indent width of 4 spaces as 2 spaces is very difficult to distinguish when using variable width fonts. 2) separate code blocks: for if else while do...while switch case default via a single blank line. 3) separate functions by 2 or 3 blank lines (be consistent)

There is no provision in the code to input a 'range' of values to use for finding deficients.

regarding:

int n = atoi(argv[1]);

the function: atoi() does not indicate if an error occurred. Suggest using: strtol() as that does indicate when an error occurred

regarding:

#define DEBUG 1

it is much more flexible to use -DDEBUG as a parameter to the compile statement rather than hardcoding the value in the source code