FALSNUM - Editorial

editorial
, ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Daanish Mahajan
Tester: Felipe Mota
Editorialist: Aman Dwivedi

DIFFICULTY

Cakewalk

PREREQUISITES

Observation

PROBLEM:

Chef’s friend gave him a wrong number W containing N+1 digits and said that the actual number A is the largest possible number that can be obtained from deleting exactly one digit of W. The chef was able to find A but forgot W.

Given A, find the smallest possible number W of length N+1 without leading 0's that is consistent with the story above. We can show that there is always at least one such W consistent with the story.

EXPLANATION:

We have a number A consisting of N digits. Our goal is to find the smallest number W of length N+1 by inserting a single digit on A.

Depending on the first digit of A there can be two cases, which are:

Case 1: The first digit of A is greater than 1

  • Best Position to Insert a Digit

    Let us see which is the best position to insert a new digit on the number A. Since the newly formed number will always consist of N+1 digits, irrespective of where we insert a digit. Hence we can say the smallest number is also lexicographically smallest too.

    Since the first digit of a number is greater than 1, then if we don’t insert a new digit at the beginning, we will always end up with a number W with the first digit same as that of A.

    As the first digit of the number A is greater than 1, that means we always have a choice to obtain a number W such that whose first digit is smaller than that of A. That is only possible when we insert a new digit at the beginning.

    Hence the best position to insert a digit, in this case, is at beginning of the number A.

  • Best Digit to Insert

    Since we are inserting a digit at the beginning then we can’t insert 0 as we don’t want leading zeroes. As the next smaller digit is 1, we would insert 1 at the beginning in this case.

Case 2: The first digit of A is 1

  • Best Position to Insert a Digit

    As the first digit is already 1, then it is not optimal to insert the new digit at the beginning. Remember the number is lexicographically smaller than the other when the first digit where it differs is less in that number.

    Hence we will find the digit which is greater than 0 in the given number A (excluding the first digit of number A). If we find such a digit then we will insert a digit 0 before that digit making it lexicographically smallest.

    If there exists no such digit then we would be obtaining a number in the form of 10^{N+1}, which is a smaller number possible in N+1 digits.

  • Best Digit to Insert

    Since we are not inserting a digit at the beginning hence we can insert 0, which is the minimum possible digit.

TIME COMPLEXITY:

O(1) per test case

SOLUTIONS:

Setter
Tester
Editorialist 
#include<bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
  string s;
  cin>>s;

  if(s[0]=='1')
    s[0]='0';
  
  cout<<1<<s<<"\n";

}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int t;
  cin>>t;

  while(t--)
    solve();

return 0;
}
1 Like
2

Why it is giving wrong answer :confused:?

#include<stdio.h>
int main()
{
int t;
scanf("%d",&t);
while(t–)
{
int n,num,l =0,i;
scanf("%d",&n);
num = n;
while(num > 0)
{
l++;
num = num/10;
}

 int a[l];
 num = n;
 for(i = l-1; i>=0;i--)
 {
 	a[i] = num%10;
     num = num/10;
 }


	if(a[0] > 1)
	printf("1%d\n",n);
	
	else
    {
  		printf("1");
  		a[0] =0;
  		
	for(i =0;i<l;i++)
	printf("%d",a[i]);
	
	printf("\n");
   }
	
}

}

4
5

When you get your input, say

1
9876543211

‘n’ cannot hold such a big number since it is of type int. That is why it is being stored incorrectly.

6

#include
using namespace std;
#include
int main() {
int t;
cin>>t;
while(t–){
longlong int a;
cin>>a;
string str = to_string ( a ) ;
if(str[0]==‘1’)
{
str[0]=‘0’;
}
cout<<“1”+str;
cout<<endl;
}
return 0;
}

I am too getting the WA I don’t know what might be the problem
in I had taken integer as an input as per the question but still WA

7

Why the input is taken in string format in editorialist’s solution, as asked in question it’ll be integer. I also was thinking to take in string but due to question’s mention I didn’t did and end up with a WA.
@cherry0697 is it fine to take input this way??

1 Like
8

What is wrong with my code?
Please help

#include
using namespace std;
typedef long long int ll;

void solve(string s){
string ans="";
if(s[0]==‘1’){
ans.push_back(s[0]);
ans.push_back(‘0’);
ans+=s.substr(1);
}
else{
ans.push_back(‘1’);
ans+=s;
}
cout<<ans<<endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;cin>>t;
while(t–){
ll a;cin>>a;
string s=to_string(a);
solve(s);
}
}

9

As mentioned in the ques we need to take an integer not string, “Each test case contains a single line of input, an integer A” But the solutions are got accepted by taking input as strings
Please check the issue

10

you should try all possibilities by taking constraints into consideraton

11

As mentioned in the ques we need to take an integer not string, “Each test case contains a single line of input, an integer A” But the solutions are got accepted by taking input as strings…This is unfair. I have lost my ratings drastically because of the error of question setter. Please do something codechef. @cherry0697

12

why have you used ll a and cin a?? you just had to input the string.
NOTE: please format your code before posting in the discuss forum as it becomes easier to debug your code

13

It was never mentioned that you have to take input in the form of integer only.It was just mentioned like each line of input contains an integer.

14

yup the input formt was inappropriate that cause a lot of misunderstanding (rather this was a very simple problem) but these things happen ( Bade bade deshon mein aaisi choti choti baatein … hoti rehti hai) dont be frustate just enjoy.