Numbers with Unique Digits – Solution

Posted on by

I hope you came up with an interesting solution for this month’s Exercise, one different from my own. The goal is to output unique values from zero through ten billion, values where no two digits repeat.

The core of my solution is to convert the number into a string. I then scan the string for repeating digits. This process takes place in a function, digit_scan(), which returns TRUE or FALSE based on the presence of repeating digits. I tried putting this scan in the main() function, but the code became overly complex. The digit_scan() function resolved many issues.

2023_11-Exercise.c

#include <stdio.h>
#include <string.h>

#define MAX 11
#define TRUE 1
#define FALSE 0

int digit_scan(long a)
{
    int size,x,y;
    char digits[MAX];

    /* convert to a string */
    snprintf(digits,MAX,"%ld",a);
    /* obtain value size */
    size = strlen(digits) + 1;
    /* scan the digits */
    for( x=0; x<size-2; x++ )
    {
        for( y=x+1; y<size-1; y++ )
        {
            if( digits[x] == digits[y] )
            {
                /* not unique */
                return(FALSE);
            }
        }
    }
    return(TRUE);
}

int main()
{
    int unique;
    long v;

    unique = 0;
    for( v=0; v<10000000000; v++ )
    {
        if( digit_scan(v) )
        {
            printf("%ld\n",v);
            unique++;
        }
    }
    printf("%d unique values\n",unique);

    return(0);
}

Three defined constants are declared: MAX, which represents the maximum number of digits in the largest value, ten billion. Then TRUE and FALSE for return values from the digit_scan() function, which make the code more readable.

The digit_scan() function uses the snprintf() function to convert the value passed (long int variable a) to a string. Placeholder %ld is required to deal with long integers. The string’s length is saved in variable size, which is used in the nested for loops to scan the value.

The nested for loops work like a bubble sort, comparing each digit in the number with every other digit. Here is where I’m certain a better solution is available, though I couldn’t think of one. As soon as two digits match in the inner loop, FALSE is returned. Otherwise, if the scan completes with no matches, TRUE is returned meaning the value contains unique digits.

The main() function features a loop that processes values zero through ten billion. An if test calls the digit_scan() function. When true, the unique value is output and the unique counter incremented.

The sample run outputs 8,877,691 lines of text and takes my computer 26 minutes to complete, but it works. I’m eager to see other solutions, specifically a method to scan the number for unique digits. I shall be delighted to review such solutions because I assume they exist.

One thought on “Numbers with Unique Digits – Solution”

  1. Here is another solution, submitted by reader Markus:

    a quick first improvement to your solution would use the fact that snprintf() returns the number of bytes written, so there is no need for a following strlen():

    size = snprintf(digits,MAX,"%ld",a) + 1;

    But why convert to a string at all? We could just extract the digits from the number and check for duplicates. For this, we use a simple lookup table: 

    #include 

#define TRUE     1
#define FALSE    0
#define NUM      (1000 * 1000 * 1000 * 10)

int
digit_scan(long a)
{
    int table[10] = {0};

    while (a > 0) {
        int d = a % 10;
        if (table[d]) return FALSE;
        table[d] = 1;
        a /= 10;
    }

    return TRUE;
}

int
main(void)
{
    int unique = 0;
    for (long v = 0; v < NUM; v++) {
        if (digit_scan(v)) {
            unique++;
        }
    }
    printf("%d unique values\n", unique);

    return 0;
}

Leave a Reply