The given problem is simple but even though couldn’t solve it.Can someone help me with following problem…
‘4’ and ‘7’ as Magic numbers. The numbers containing only magic numbers are also magical. Given a magic number N,what could be the next magical number greater than the given number.
problem link is:http:www.codechef.com/ALKH2012/problems/NMAGIC/
hello dawdler i am also beginner but was able to solve this question.
it is given that magic number can only contain 4 or 7 as digit only.
for example
4474 --> 4477
4477 --> 4744
777 --> 4444
so you have only two case
when you have one of digit as 4 (example 1,2)
read from last digit and change 7 to 4 and 4 to 7 stop when
you change 4 to 7 for first time
when all digit consist of digit (example 3)
7 only
answer will be number consiting of all digit as 4 but of
length +1 than original
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
int t;
char a[150];
cin>>t;
while(t--) { char a[150];
cin>>a;
int l=strlen(a),flag=0;
for(int i=0;i<l;i++)
{
if(a[i]=='4')
{
flag=1;
break;
}
}
if(flag==0)
{ for(int i=0;i<=l;i++)
cout<<'4';
cout<<endl;
}
if(flag==1)
{ int first=0;
for(int i=l-1;i>=0&&first==0;i--)
{
if(a[i]=='4'&&first==0)
{
a[i]='7';
first=1;
}
if(a[i]=='7'&&first==0)
{
a[i]='4';
}
}
for(int i=0;i<l;i++)
cout<<a[i];
cout<<endl;
}
}
return 0;
}You have to find the next magical number greater then the given magical number. Think about it just like bigint additions. First reverse the string. Then Check the digits. If it is 4, then directly change it to 7 and the reverse of the new string will be your answer. But if the digit is 7 you will have to change it to 4 but now you will have to keep an extra flag to also change the next digit. This happens because of a carry. After all the digits have been checked, you will have to check if the flag is true. If so then add another digit 4 to the end of the string. The reverse of this string will be your answer. Hope this helps.
@nirajs…i figured out the both cases but i could not implement them…
i tried using array and then change the digits and finally print then new formed array…
help me with the implementation of it in C/C++
@flaminrage BIGINT…I guess u implemented your logic in Java right? otherwise it’s difficult to handle that range of data in C/C++
No, I didn’t use bigint. I used C++. I just told you to think about the idea of considering the number as a string or bigint and how you would normally use addition operations on it. You just need to apply that logic carefully.
@flaminrage and @nirajs could you all pls the share the code with me…
it would be really helpful for me…I m getting difficulties in implementing the logic…
The logic is same as explained by others:
int main(void)
{
int T;
char c[10000],*p;
scanf("%d",&T);
while(T--)
{
p=c;
cin>>c;
while(*(p+1)) *p++;
while((*p!='4')&&(p>=c)) *p--='4';
if(p>=c) {*p='7';cout<<c<<"\n";}
else cout<<'4'<<c<<"\n";
}
return 0;
}
this code will also implement the logic accurately i guess:
int main(){
int len,len1;
int j,i,flag=1;
int t;
char digit[1000000],newd[1000000];
flag=1;
gets(digit);
strcpy(newd,digit);
len=strlen(digit);
i=len-1;
len1=len;
while(len) {
if(digit[i]==‘4’) {
flag=0;
newd[i]=‘7’;
printf("%s\n",newd);
break;
}
else {
newd[i]=‘4’;
i–;
}
len–;
}
if(flag==1) {
for(j=0;j<len1+1;++j) { printf(“4”); }
}
return 0;
}
@yash thanks for the code…perfectly written program…
and by the way how did to align those lines of code to post here…i tried but couldnot…
#include
#include
#include
using namespace std;
char ch[110];
short int t,l,i;
int main()
{
cin>>t;
getchar();
while(t–)
{
gets(ch);
l=strlen(ch);
for(i=l-1;i>=0;i–)
if(ch[i]==‘4’)
break;
if(i==-1)
{
cout<<‘4’;
for(i=0;i<l;i++)
cout<<‘4’;
}
else
{ch[i]=‘7’;
for(i=i+1;i<l;i++)
{
ch[i]=‘4’;
}
for(i=0;i<l;i++)
cout<<ch[i];}
cout<<endl;
}
}
//wats wrng in it satisfies evry thing still wrng ans
//pls give a test case which gives a wrng ans pls
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
char a[160];
scanf("%s",a);
int n=strlen(a);
int flag=0;
for(int i=n-1;i>=0;i--)
{
if(a[i]==4)
{
a[i]=7;
flag=1;
break;
}
}
if(flag==0)
printf("4");
printf("%s\n",a);
}
return 0;
}here is my code
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
int t;
char a[150];
cin>>t;
while(t--) { char a[150];
cin>>a;
int l=strlen(a),flag=0;
for(int i=0;i<l;i++)
{
if(a[i]=='4')
{
flag=1;
break;
}
}
if(flag==0)
{ for(int i=0;i<=l;i++)
cout<<'4';
cout<<endl;
}
if(flag==1)
{ int first=0;
for(int i=l-1;i>=0&&first==0;i--)
{
if(a[i]=='4'&&first==0)
{
a[i]='7';
first=1;
}
if(a[i]=='7'&&first==0)
{
a[i]='4';
}
}
for(int i=0;i<l;i++)
cout<<a[i];
cout<<endl;
}
}
return 0;
}“4<= N<=10^100”
you should have taken char ch[1000];
thanks dude
i removed those # lines but still not working…
I submitted the below program…but i am getting wrong answer so pls…show me the test cases where my program doesn’t work…
#include<stdio.h>
int main()
{
long long int n;
int c=0,i,t;
scanf("%d",&t);
while(t--)
{
scanf("%lld",&n);
c=0;
while(n%10!=4 && n>0)
{
n=n/10;
c++;
}
if(n!=0)
printf("%lld",n+3);
if(n==0)
c++;
for(i=0;i<c;i++)
printf("4");
}
return 0;
}4<=n<=10^100
You cannot store it in long long int since the no. of digits in n>=100.
use char* to store the value.
@bitfield You need to use character array to store that range of data(10^100)…no data type in C/C++ can handle it directly…so i guess your program is showing wrong answer since you have used long long int…