Вводится число n. Нужно определить сколько "единичек" в отрезке [1..n]
Например для 10 это 2, для 50 - 14.
Похоже на довольно стандартную задачу, но как сделать не пойму...
Например для 10 это 2, для 50 - 14.
Похоже на довольно стандартную задачу, но как сделать не пойму...
От каждой цифры числа, кроме числа единиц, которая больше 1 отнимаем 1. Умножаем это число на 9. Складываем все + число единиц числа. Теперь от n+1 отнимем это число. Вуаля.
n=29 таким образом 1*9 + 9 = 18. Вычтите из n+1, и получаем 12
5394=9*9*9*4+2*9*9+8*9+4=5395-3154=2241
Относительно последней цифры: Если были цифры 1 до сих пор, мы включаем последнюю цифру, и добавляем 1, если это 0. Таким образом добавляем 4 для 5394, 1 для 5390, ничего для 5216,но добавляем 1 для 5391.
Пусть n=31874, тогда 2*9^4+1*9^3=13851, 31874+1-13851=18024.
Это подтверждает решение в лоб
#include <iostream>
inline bool valueContainsOne(int n)
{
do {
if (n % 10 == 1) {
return true;
}
} while (n /= 10);
return false;
}
int main()
{
int x;
do {
std::cin >> x;
} while (x < 1);
int result = 0;
for (; x >= 1; --x) {
if (valueContainsOne(x)) {
++result;
}
}
std::cout << result ;
}
long long f (long long num) {
if (num==0) return 0;
int len=0,first=0;
long long tmp=num;
while (tmp>0) {
if (tmp<10) first=tmp;
len++; tmp/=10;
}
long long res=0,md=1;
for (int i=0;i<len-1;i++) {
res+=md;
md*=10;
}
if (first==1) {
res+=(num-md+1);
} else {
res+=md;
}
return res;
}