# UVA Problem 1225 – Digit Counting Solution

UVA Problem 1225 – Digit Counting Solution:

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;

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;

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;
}
```