PROBLEM LINK:Setter: Aleksa Plavsic DIFFICULTY:Cakewalk PREREQUISITES:Brute Force PROBLEM:Given an integer $N$, find smallest number $X > N$ such that $X$ contains digit 3 at least 3 times. SUPER QUICK EXPLANATION
EXPLANATIONLet us call a number valid if it contains digit 3 at least 3 times, else invalid. Let us begin with most basic Solution which runs a loop from $N+1$ to Infinity, and breaks the loop as soon as a valid number is found. But we may expect this solution to time out, right??. Now, Brace yourselves for the next line. This solution runs easily within time limit. Now you will ask me to prove how, so here it goes. Consider a set of $1000$ elements consisting of $X \in [N+1, N+1000]$. Now, observe two things.
Hence, it can be proved that checking for next $1000$ values will always find the required answer. Worst case would be realized on case such as $333$, as the smallest valid number after $333$ is $1333$. If you want a formal proof, it can also be proved using modulo finite fields. Counting number of occurrences of digit 3 in $N$. Complexity: Bonus Problems Find $X>N$ such that $X$ contains digit $a$ atleast $b$ times. What would be time complexity? Can you improve it? A General Technique Though this problem can be solved using brute force, There's a different technique which can also solve this problem, Called Digit DP. An interesting similar problem of Digit DP can be found here. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :) asked 18 Aug, 12:52

Video solution (in C++, Java, Python and BASH): https://youtu.be/Enbht_Uf1CE answered 20 Aug, 09:10

include<bits stdc++.h="">using namespace std; bool threeThrees(int n) { int count=0; while(n>0) { if (n%10==3) count++; n/=10; }
} void solve() { int n; cin>>n;
cout<<n<<endl; }="" int="" main()="" {="" int="" t;="" cin="">>t;
return 0; } answered 20 Aug, 06:50

//what is wrong in this code? include<iostream>include<string>using namespace std; int main() {
answered 24 Aug, 18:30

@admin Can you please disable the MOSS for such cakewalk problems. I had to face the (infamous ?) points penalty just because some other random dude happened to have used the exact same code structure. Please, this is so frustrating. The solutions in question are  answered 27 Aug, 18:03
