abc186_c - Unluck 7
19 Dec 2020 — Tags: brute_force,math — URLTry all numbers from [1, n] and check if they contain $7$ in their octal or
decimal representation.
Time complexity: $O(n \log{n})$
Memory complexity: $O(1)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
bool bad(int n, int base)
{
while (n)
{
if ((n % base) == 7)
return true;
n /= base;
}
return false;
}
int solve(int n)
{
int ans = n;
for (int i = n; i > 0; --i)
if (bad(i, 10) or bad(i, 8))
ans--;
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n;
cin >> n;
cout << solve(n) << endl;
return 0;
}