Official

C - Doubled Editorial by en_translator


Due to the constraints \(N < 10^{12}\), checking each integer from \(1\) through \(N\) if it is a repetition leads to TLE.
However, there are at most \(6\) digits in the repeated integer, so we can exhaustively search for the repeated integers.
The time complexity is \(O(\sqrt N)\).

Otherwise, it can be solved in an \(O(\log N)\) time if we perform binary search for repeated integer, or in an \(O(1)\) time even without binary search.

Sample Code (C++)

#include <iostream>
#include <string>
using namespace std;
using ll = long long;

int main(){
    ll N;
    cin >> N;
    for(ll i = 1; ; i++) if(stoll(to_string(i) + to_string(i)) > N){
        cout << i - 1 << endl;
        return 0;
    }
}

Sample Code (Python)

N = int(input())
for i in range(1, 1000001):
    if int(str(i) * 2) > N:
        print(i - 1)
        exit()

posted:
last update: