Lesson: 14
Problem: 10117
Title: Ones
Difficulty Level: 2.5
Date: Jan 9, 2009
Site: UVA
Solution:
Consider first sample input: 3,
output: 3, that is 111%3 = 0, number of ones = 3
for Second sample input: 7
output: 6, because 111111%7 =0, number of ones = 6
for Third sample input: 9901
output:12, becuase 111111111111%9901 = 0, number of ones = 12
Hope you get the problem.
For input 7,
first try 1, 1%7 != 0, so try again,
11, 11%7 != 0, so continue,
111, 111%7 != 0, continue
.
.
111111%7 = 0, so our answer 6, total number of ones.
If we try to build a number with one every time, the number raises to very big one and will not fit into any data type, then how can we solve this problem.
Have a close look,
1 % 7 = 1
11 % 7 = 4 that is, (1*10+1)%7 = 4
111 % 7 = 6 that is (4*10+1) %7 = 6
1111 % 7 = 5 that is (6*10+1)% = 5
11111%7 = 2, that is (2*10+1)%7 = 2
.
.
Do you get it ?
Source Code:
1 #include<stdio.h> 2 3 main() 4 { 5 int digit,n,i; 6 while(scanf("%d",&n)==1) 7 { 8 digit = 1; 9 for(i=1;i;) // while i!= 0 10 { 11 i = (i*10+1) % n; 12 digit++; // counting ones 13 } 14 printf("%d\n",digit); 15 } 16 return 0; 17 }