UVA Problem 1225 – Digit Counting Solution

UVA Problem 1225 – Digit Counting Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

This problem is very easy. For input N = 13, sequence is 12345678910111213. which are actually numbers from 1 to 13 without spaces.

1 2 3 4 5 6 7 8 9 10 11 12 13

For this problem just calculate how many times a digit appears in the sequence. The digits being 0 to 9.

Use counting sort to easily calculate occurrence of a digit. If a digit is greater than single digit than break it to a single digit and increment count.

Here i have given two solutions. One converts digits to character than counts them. The next one count each digit in the integer without converting to string.

 

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.


More Inputs of This Problem on uDebug.


Input:

2 
3 
13

 


Output:

0 1 1 1 0 0 0 0 0 0 
1 6 2 2 1 1 1 1 1 1

Code Using Character Count:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 1225 - Digit Counting
 * Technique: Counting sort characters, Integer to character conversion.
 */


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


#define N 200000

static char output[N];
static int outputNum[10];


int main() {

    int n;

    scanf("%d", &n);

    while( n-- ){

        int num;
        scanf("%d", &num);

        memset(outputNum, 0, sizeof outputNum);


        /**
         * Add the numbers to character array for easier counting.
         * If number is more then one digit it assign each digit to
         * a new location in char array. Although they are actually
         * reversed when positioning. But the order does not matter
         * in this problem. Just count each digit.
         *
         * It is possible to count with integers rather than using
         * char array. See the next code.
         */
        int k = 0;
        for(int i = 1; i <= num; ++i){

            int num = i;
            while(num){
                output[k++] = (num % 10) + '0';
                num /= 10;
            }
        }
        output[k] = '\0';


        /**
         * Use counting sort sort technique to position each
         * character to its equivalent integer location.
         */
        for(int i = 0; output[i]; ++i)
            ++outputNum[ output[i] - '0' ];


        for(int i = 0; i < 10; ++i){
            if(i) printf(" ");
            printf("%d", outputNum[i]);
        }
        printf("\n");
    }

	return 0;
}


Code Using Integer Count:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 1225 - Digit Counting
 * Technique: Counting sort characters, Integer to character conversion.
 */

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


static int outputNum[10];


int main() {

    int n;

    scanf("%d", &n);

    while( n-- ){

        int num;
        scanf("%d", &num);

        memset(outputNum, 0, sizeof outputNum);


        /**
         * It is possible to count the digits without convert char array.
         * Count each digit using counting sort technique.
         */
        int k = 0;
        for(int i = 1; i <= num; ++i){

            int num = i;
            while(num){
                ++outputNum[num % 10];
                num /= 10;
            }
        }


        for(int i = 0; i < 10; ++i){
            if(i) printf(" ");
            printf("%d", outputNum[i]);
        }
        printf("\n");
    }

	return 0;
}
Advertisements

One thought on “UVA Problem 1225 – Digit Counting Solution

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s