题目描述

一个整数如果按从低位到高位的顺序，奇数位（个位、百位、万位 ⋯ ）上的数字是奇数，偶数位（十位、千位、十万位 ⋯ ）上的数字是偶数，我们就称之为 “好数”。

给定一个正整数 N，请计算从 1 到 N 一共有多少个好数。

样例

输入: 24
输出: 7

算法

(暴力枚举)

只需要枚举1到n每一个数字并判断

时间复杂度$O(n*lg(n))$

C++ 代码

#include<iostream>

using namespace std;

bool judge(int x){
    int tmp = x;
    int idx = 1;//用idx表示目前是奇数位还是偶数位
    //idx = 1代表当前位置和当前位置的数应该mod2余1, idx = 0代表mod2余0
    while(tmp){
        if((tmp % 10) % 2 != idx){//如果当前数字末位mod2不等于idx即不是好数
            return false;
        }
        idx = 1 - idx;// 1 - 0 = 1, 1 - 1 = 0交替变换
        tmp /= 10;
    }
    return true;
}

int main(){
    int n, ans = 0;
    cin >> n;
    for(int i = 1; i <= n; i++){
        if(judge(i)) ans++;
    }
    cout << ans << endl;

    return 0;
}