Faster solution to compute magic numbers

Question

There are N doors with a number on each door. You have a golden key(K) and you can open with it only doors on which the numbers are magic and can be reduced to the number of the key (With key 7 you can open doors on which the magic numbers can be reduced to 7). A number is magic if it can be reduce to a one digit number. The method to reduce the number is the following: turn each digit of the number to the subtraction of the digit from the max digit of the number. And repeat the process. For example: 1234->3210->123->210->12->10->1. Note that some numbers can't be reduced to a one digit number. For example: 1204->3240->1204->3240->1204... You have to find how many doors can be opened with the magic K key and the max even number. The input is N(number of doors), K(magic key) and numbers on each door. The output is the max even number and the number of doors that can be opened with K key.

7 ≤ N ≤ 10000
0 ≤ K ≤ 9

Each number on the doors is a 10-32800 number. There is at least one even number.

#include <stdio.h>
#include <stdlib.h>

int checkForZero( int number )
{
    while( number )
    {
        if( number % 10 == 0 )
        {
            return 1;
        }
        number /= 10;
    }
    return 0;
}

int findMaxDigit( int len ,int number[len] )//returns max digit of the number
{
    int digit = 0;
    int i;
    for( i = 0; i < len; i++ )
    {
        if( number[i] > digit )
        {
            digit = number[i];
        }
    }
    return digit;
}

int length(int arg)
{
    //returns number of digits of a number
    return snprintf(NULL, 0, "%d", arg) - (arg < 0);
}

int poww(int a)//returns 10 ^ a
{
    int c = 10, i;
    for(i = 1; i < a; i++)
    {
        c *= 10;
    }
    return c / 10;
}

int main()
{
    int N;//number of doors
    scanf( "%d", &N );
    int K;//magic key
    scanf( "%d", &K );
    int numberA[5] = {1};
    int doorsToOpen = 0;//number of doors that can be opened with K key
    int maxEvenNumber = 0;
    int i;
    for( i = 0; i < N; i++ )
    {
        int doorNumber;//number on the door
        scanf( "%d", &doorNumber );
        if( doorNumber > maxEvenNumber ) maxEvenNumber = doorNumber;
        int numberLength = length( doorNumber );
        //I assumed that every number that contains a `0` is no a magical number
        //except the powers of 10
        //100->11->0
        int power = poww( numberLength );
        //if the current number is not magical go to next door
        if( checkForZero( doorNumber ) && ( doorNumber != power )) continue;

        //put number in an array
        int j;
        for( j = numberLength - 1; j >= 0; j-- )
        {
            numberA[j] = doorNumber % 10;
            doorNumber /= 10;
        }

        while( numberLength > 1 )//If the number is not a one digit number
        {
            int maxDigit = findMaxDigit( numberLength, numberA );
            if( numberA[0] == 0 )//if the first digit of the number is 0 deletes it. [0][1][2] will turn into [1][2]
            {
                numberLength--;
                for( j = 0; j < numberLength; j++ )
                {
                    numberA[j] = numberA[j + 1];
                }
            }
            //transform the number
            for( j = 0; j < numberLength; j++ )
            {
                numberA[j] = maxDigit - numberA[j];
            }
            //create the number to check if it is equal to the initial number
            doorNumber = 0;//I will work with this number because i have saved it
            //save the transformed number from array to this variable
            for( j = 0; j < numberLength; j++ )
            {
                doorNumber *= 10; doorNumber += numberA[j];
            }
            if( doorNumber == K )
            {
                doorsToOpen++;
            }

        }
    }
    printf("%d", maxEvenNumber);
    printf("\n%d", doorsToOpen);
    return 0;
}

My code is working fine, but I need a faster solution. Could you please help me giving me some tips on how to make a faster algorithm to this problem?

Answer 1

This review will focus on style primarily, but performance and bug fixes are also a part of it.

---

The reduction algorithm is as follows:

/*
1. Find the largest digit in the input number.

Example: largest digit of 322 is 3.

Example: largest digit of 23521 is 5.

2. Create the minuend: it is the largest digit in the input number
                       concatenated digit_count(input_number) times.

Example: minuend of 322 is
             largest_digit(322) = 3
             digit_count(322) = 3
             333

Example: minuend of 2352 is
             largest_digit(2352) = 5
             digit_count(2352) = 4
             5555

2. Reduction is done by subtracting the input number from the previously created minuend.

Example: Reduce 1234

largest_digit(1234) = 4
digit_count(1234) = 4
minuend = 4444

  4444
- 1234
------
  3210

The output is 3210 after 1 reduction.

3. Repeat reductions until the number is one digit long.
*/

---

From that, we know that to reduce a number, we must simply subtract the concatenation of the largest digit x times, where x is the count of digits of your input number. Since we know that a digit is from 0 to 9, we can write the following function:

int make_repeated_int(int const val, int const size)
{
    static int const digit_multipliers[] =
    {
        0,
        1,              // 1
        11,             // 2
        111,            // 3
        1111,           // 4
        11111           // 5, stop here because max door # is 32800
    };
    return val * digit_multipliers[size];
}

This allows the creation of 4444 from make_repeated_int(4, 4) or 555 from make_repeated_int(5, 3). This is might or might not be faster (I haven't timed it) than calling your poww() function. The main reason for its existence is having small pieces of reusable code.

---

We also know that we must determine the largest digit in a number. So we write the following branchless max of two values function:

#include <limits.h>

// source: https://stackoverflow.com/q/514435/2296177
int max(int const a, int const b)
{
    int mask = a - b;
    mask = mask >> ((sizeof(a) * CHAR_BIT) - 1);
    return a + ((b - a) & mask);
}

User Adriano Repetti notes that the right shift is not fully portable. Please look into this if your requirements require it to be.

---

We now have enough utility functions to create a reduce function:

#include <stdlib.h>
#include <stdint.h>

typedef struct
{
    int reduction;
    uint8_t size;
} reduce_t;

reduce_t reduce(int const n)
{
    uint8_t size = 0;
    int max_digit = 0;

    int quot = n;
    for (div_t div_res = div(quot, 10); quot != 0; div_res = div(quot, 10))
    {
        ++size;
        max_digit = max(max_digit, div_res.rem);
        quot = div_res.quot;
    }

    reduce_t r = { make_repeated_int(max_digit, size) - n, size };
    return r;
}

Inside <stdlib.h>, we find the div() function which returns both the remainder as well as the division result. This function internally is likely to use processor specific instructions so that only one operation (division) is required to get both the remainder and quotient. Your compiler might perform this optimization, but let's not leave it to chance.

Note that per Tamoghna Chowdhury's suggestion, we use uint8_t and int8_t for clarity.

---

However, we know that reduction can fail for certain numbers, so we'll make a helper function that attempts to reduce a number:

#include <stdbool.h>
#include <stdint.h>

typedef struct
{
    int8_t reduction; // the reduced number is always 1 digit long, save space
    bool is_reduced;
} try_reduce_t;

try_reduce_t try_reduce(int const n)
{
    reduce_t r = reduce(n);
    for (reduce_t c = reduce(r.reduction); c.size > 1; c = reduce(r.reduction))
    {
        if (c.size == r.size && r.reduction < c.reduction)
        {
            try_reduce_t tr = { .is_reduced = false };
            return tr;
        }
        r = c;
    }
    try_reduce_t tr = { r.reduction, true };
    return tr;
}

Two reductions are performed every loop to check whether we're stuck with an irreducible number.

For reductions that would loop infinitely, we can deduce two properties:

1. Every two iterations, the digit length of the reduction must be smaller.

2. Reduction 3 will give us the same value as reduction 1, so you could check against that as well.

The condition of option 2 looks like this inside try_reduce():

// this detects whether we're stuck or not
if (r.reduction == reduce(c.reduction).reduction) { ... }

Either is fine, but option 1 is faster (after measuring) so option 2 is discarded.

---

We need to test whether a certain door is openable by a certain key. Using the previous building blocks, that's easy to implement:

bool is_openable(int const door_number, int const key)
{
    try_reduce_t tr = try_reduce(door_number);
    return tr.is_reduced && tr.reduction == key;
}

---

Your main() function now looks like this:

#include <stdio.h>

int main()
{
    int N = 32800;
    int K = 1;

    int openable_door_count = 0;
    for (int i = 10; i < N; i++)
    {
        if (is_openable(i, K))
        {
            ++openable_door_count;
        }
    }
    printf("%d\n", openable_door_count);
}

This finds the number of doors that can be opened by key \$K = 1\$ in the range \$[10, 32800]\$.

As a general note, please note that identifiers that end with _t are reserved by POSIX, so be careful if you're including POSIX headers (if you are, remove the _t part to be safe).

Answer 2

1. Don't use an ASCII-representation of the number, as it is inefficient for your task. The printf()-family of functions is quite heavyweight.

2. Your termination-condition is wrong:

   You can land in a cycle without ever coming back to the starting number.

   You can easily check whether further reducing is pointless: If a reduction neither reduces the number nor its maximum digit, you are in a cycle.

3. Find better names for your functions. Doing so makes the code more descriptive and lets you remove now useless comments.
   checkForZero() => hasZeroDigit() findMaxDigit() => largestDigit() length() => countDigits() poww() => pow10()

4. Check whether scanf() succeeded and gave you an acceptable number. Among others, you don't handle negative numbers.

5. return 0; is implicit for main() since C99.

---

#define BASE 10
static unsigned largestDigit(unsigned n) {
    unsigned result = 0;
    while(n) {
        if(result < n % BASE)
            result = n % BASE;
        n /= BASE;
    }
    return result;
}

// Reduce argument fully (< BASE) or until caught in loop (>= BASE)
unsigned reduce(unsigned n) {
    unsigned max, oldMax = BASE, oldN;
    while(n >= BASE && ((max = largestDigit(n)) < oldMax || n < oldN)) {
        unsigned big = max;
        do big = BASE * big + max;
        while(big < n);
        oldN = n;
        n = big - n;
        oldMax = max;
    }
    return n;
}

Answer 3

Your code is not working fine.

Firstly, it prints the maximum number, not the maximum even number (you can check it by running it on the input 2 2 31 16).

Secondly, it's not that it's slow. It never terminates for some input. If the doorNumber is 342, your code goes into an infinite loop as the number transformation go as follows: 342 -> 102 -> 120 -> 102 -> ...

How to fix? The first bug is easy to fix (just update the maximum when the number is even). You can fix the second bug by building a graph for all numbers (with an edge a -> b if a goes to b in one step) explicitly and traversing using, for instance, depth-first search and carefully checking for the cycles.