MINNUM - Minimum Number


  Problem Statement:

Prana has given a number. Now she wonder what will be the maximum number of digits that the sum of these digits is equals to the given number. After thinking sometimes she laughed at herself, cause the number is infinite.

Now your task is to find the minimum number of digits that the sum of these digits is equals to the given number.


The input contain a single integer N ( 0 ≤  N ≤ 1031 ). The input is terminated by a line containing -1.


Output a single line the number of digits that the sum of the digits is equals to the given number. See the sample input/output for exact formatting.

Sample Input/Output:

Sample Input

Sample Output






Explanation :

For the first test case given number is 11. Some possible way to make 11 is

7+4=11 which costs 2 digits.

2+3+6=11 which costs 3 digits.

1+2+3+5=11 which costs 4 digits.

1+2+3+0+5=11 which costs 5 digits.

So, here first example costs the minimum number of digits which is 2.

Note: There are no extra new lines between different numbers.

Problem setter: Abu Sufian, Dept. of CSE

Bangladesh University of Business and Technology (BUBT)

hide comments
sagnik_66: 2017-09-06 13:49:09

Implemented within 2 mins, then noticed that Java wasn't allowed.... Lol

candide: 2017-04-14 03:52:53

Elementary but tedious to get right, C is not Python! Tests are weak, for instance a file returning incorrectly 1000 (instead of 1002) to 9010 as input got accepted. The correct answer for 0 as input remains unclear (the valid answer is 0, not 1).

Last edit: 2017-04-14 16:57:28
madhavgaba: 2016-12-29 11:46:38

doing without big integer....really a workout!

sonu: 2016-11-06 13:07:57

if you are getting wa then do check for 92

topke: 2016-03-09 15:00:41

Clarify 0 test case, cause right answer by problem statement is 1

msainkhil: 2015-12-29 18:42:54

good questin, implemented my bigint

Satyam Mishra: 2015-07-26 12:06:31

Nice and easy one...
ACed in 1 go. :)

:.Mohib.:: 2015-07-22 15:07:16

Very good question.... :)
You need to write your own container...!! ;)

Last edit: 2015-07-22 17:37:12
vasayashwanth: 2015-07-13 09:37:23

test cases with answers:
0 0
1 1
10 2
82 10
892 100
8991 99
8992 1000

:D: 2015-02-12 20:12:17

Result for 0 is 0, as in you don't have to use any digits.

Added by:Shipu Ahamed
Time limit:1s
Source limit:3100B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C CPP C++ 4.3.2 PAS-GPC PAS-FPC