BFTT - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 2

Setter: Aleksa Plavsic
Tester: Hussain
Editorialist: Taranpreet Singh

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

  •   Check for next 1000 numbers, print the smallest one which contains digit 3 at least 3 times.
    

EXPLANATION

Let 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.

  • The last 3 digits of each number in set differ, since consecutive numbers differ by 1 each
  • There will exist a number ending with 333 in set. This number will always be valid since it contains digit 3 at least 3 times, So we don’t need to search beyond this number.

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.

Click to view

int cnt = 0; while(n != 0){ if(n%10==3)cnt++; n/=10; }

Complexity:
Since we check 1000 values per test case, and counting Number of occurrences of digit 3 takes \log_{10} N time, Time Complexity is O(1000*T*{\log_{10} N}).

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
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

1 Like

Video solution (in C++, Java, Python and BASH): https://youtu.be/Enbht_Uf1CE

2 Likes

//what is wrong in this code?

#include
#include
using namespace std;
int main()
{

int t;
cin>>t;
for(int p=0;p<t;p++)
{  int i;
	long long int n;
	cin>>n;
	long long int a[18];
	int j=n;int k=0;int count=0;
	while(j)
	{
		a[k]=j%10;
		if(a[k]==3)
		{
		count++;}
		j=j/10;
		k++;
		
		
	}//cout<<"k"<<k<<endl;
//	cout<<count<<endl;
		
	//	for(i=k-1;i>=0;i--)
	//	cout<<a[i]<<endl;
	//	cout<<"a"<<endl;
	if(n>=333)
	{
	
	if(count>=3 &&  k>count)
	{ int i=0;
//	cout<<"here"<<endl;
	while(a[i]==3)
	{
		i++;
		
		
	}//cout<<"i"<<i<<endl;
		a[i]=a[i]+1;
		for(i=k-1;i>=0;i--)
		cout<<a[i];
		cout<<endl;
	}
	else if(k<=count&&count>=3)
	cout<<"1"<<n<<endl;
	
	else if(count<3 && k>3)
	{//cout<<"here";
		int c=3-count;
		i=0;
		while(c )
		{    if(a[i]!=3)
			{
			a[i]=3;c--;}
			i++;
		}
		
		
		
		
		for(i=k-1;i>=0;i--)
		cout<<a[i];
		cout<<endl;
	}
	else if(count<3 && k<=3)
	{//cout<<"here";
		int c=3-count;
		i=0;
		while(c )
		{    if(a[i]!=3)
			{
			a[i]=3;c--;}
			i++;
		}
		
		
		
		cout<<"1";
		for(i=k-1;i>=0;i--)
		cout<<a[i];
		cout<<endl;
	}
	
}
else
cout<<"333"<<endl;}}

@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 -

https://www.codechef.com/viewsolution/19786629

https://www.codechef.com/viewsolution/19801288

for i in range(int(input())):
n=int(input())
for j in range(n+1,2*1000000000):
if(str(j).count(‘3’)==3):
print(j)
break
#why this code is not correct?

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
long int n,m,s;
int c=0,r;
cin>>n;
m=n+1;
while(1)
{
c=0;
s=m;
do
{
r=s%10;
if(r==3)
c++;
s=s/10;
}while(s);
if(c==3)
{
cout<<m<<endl;
break;
}
m=m+1;
}
}
return 0;
}

what is the mistake in this code

What is the error in this code?

#include <stdio.h>

int main()
{
int a, n;
scanf("%d", &a);
for(int i=0; i<a; i++)
{
scanf("%d", &n);
int ans=0;

    int b;
    for(b=n+1; b>0; b++)
    {
        int t=0;
        int d=b;
        while(d>0)
        {
            int c=d%10;
            if(c==3)
            {
                t++;
            }
            d=d/10;
        }
        if(t==3)
        {
            ans=b;
            b=0;
            break;
        }
    }
    printf("%d\n", ans);
}
return 0;

}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int characters(ll n) {
	ll counter = 0;
	while(n > 0) {
		n /= 10;
		counter++;
	}
	return counter;
}

int count(ll x) {
	ll sum = 0;
	for(int i = 1; i <= x; i++) 
	sum += i;
	return sum;
}

int check(ll n) {
	ll cnt = 0;
	while(n > 0) {
		if(n % 10 == 3) {
			cnt++;
		}
		n /= 10;
	}
	return cnt;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin >> t;
	while(t--) {
		ll n;
		cin >> n;
		for(int i = n + 1;; i++) {
			if(check(i) >= 3) {
				cout << i << endl;
				break;
			}
		}
	}
}

//This program of mine is throwing a runtime error TLE, how can i resolve the issue by making the solution better. Help needed! Thanks.program in ide
#include
using namespace std;

int main() {
// your code goes here
int t,c=0;
long long int n;
cin>>t;
while(t>0)
{
cin>>n;
while(n++)
{
long long int temp=n;
while(n!=0)
{
if(n%10==3){
c=c+1;
n=n/10;
}
}
if(c>=3)
{
cout<<temp<<endl;
break;
}
}
t–;
}
return 0;
}

What wrong with this code somebody help?

#include <bits/stdc++.h>
using namespace std;
#define deci(n) fixed<<setprecision(n)
#define modulo 1000000007

typedef long long ll;

int main(){
int t;
cin>>t;
while(t–){
ll n,i,j;
cin>>n;
for(i = n+1;; ++i){
int c = 0;
j=i;
while(j){
if(j%10==3)
++c;
j=j/10;
}
if(c==3)
break;
}
cout<<i<<endl;
}
return 0;
}

Write
if(c>=3) in place of (c==3)
because in question we have to find a number having 3 atleast 3 times

Hey,
I really hoped that my brute force approach wont work, but it did anyways.
Did anyone do it sans brute force? I really think that can be done and link given in the editorial to a similar problem is broken.

T hanks