Programming exercises: special numbers (problem solving ideas + code implementation)

【 Problem description 】

Define a particular number , Its left half is exactly the same as its right half , for example 2020, Its left half and right half are 20, Is a special number .

Be careful ： Numbers 202 Not a special number , Numbers 2112 It's not a special number .

Now, please find the interval [1,n] the n In number , How many special numbers are there .
【 Input form 】

Input integer n.

【 Output form 】

Output an integer , Indicates the interval [1,n] the n The number of particular digits in a number .

【 The sample input 】

22

【 Sample output 】

2

【 Sample explanation 】

[1,22] this 22 In number , Only 11 and 22 It's a special number , So output 2

【 Standard for evaluation 】

about 20% The data of , Guarantee 1<=n<=100

about 40% The data of , Guarantee 1<=n<=100000

about 60% The data of , Guarantee 1<=n<=1e9

about 100% The data of , Guarantee 1<=n<=1e18

Their thinking

The data range is too large to enumerate and judge every number
therefore Find the law of numbers
Each such special number is represented by a 1~1e9 Formed by numbers between
such as ：32 Can constitute a 3232,789 Can constitute a 789789…
Then you have to judge [0,n] Between how many such special numbers , Just judge that it is less than n What is the largest special number of
if n The number of digits of is odd , example ：n = 12345, that 10000 - 12345 There are no special numbers between them , So you can put n regard as 9999, Then we can know that there are 99 A special number
if n The number of digits is even , There are two situations .

1. The left is bigger than the right ： example ：4332, Then the biggest special number should be 4242（ Subtract one from the left half of the number ）
2. The left is smaller than the right ： example ：2345, Then the biggest special number should be 2323（ Is the left half of the number ）

From this we find the law of numbers , As for the code implementation n As a string input, it is more convenient to obtain the number of digits

Summary of experience

1. Get the number of digits of a large integer , When inputting, the input is string, adopt string.length() Get more convenient
2. string Convert to numbers

 Method 1 
#include <string>
string a;
int b = stoi(a); //  The string a Convert to numbers b

 Method 2 
#include <sstream>
string a;
stringstream stream(a);
int b;
stream >> b; //  The string a Convert to numbers b

3. character string string You can compare directly by the less than greater than symbol
4. string.substr(x, y) function , Intercept string from x Bit start y Characters （ First place is the first place 0 position ）

Code implementation

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <sstream>

using namespace std;

int main()
{
    
    string a;
    cin >> a;

    if(a.length() % 2)
    {
    
        for (int i = 0; i < (a.length() / 2); i ++) cout << 9;
    }
    else
    {
    
        string left = a.substr(0, (a.length() / 2));
        string right = a.substr(a.length() / 2, (a.length() / 2));

        if(left <= right) cout << left;
        else
        {
    
            // take string convert to int
            int b = 0;
            stringstream stream(left);
            stream >> b;
            cout << b - 1;
        }
    }
    return 0;
}