pages:
  • 1
Daneshvar Amrollahi SAYS

Does anyone know the answer to the subj of this topic? I tried this code but it takes too much time:

#include<iostream>
#include <sstream>
#include <string>
using namespace std;

bool check(string a)
{
 bool check = true;
 for (int i=0;i<a.length();i++)
 {
     if (a[i]=='4')
        return false;
 }

 return true;
}

int main()
{
string s;
while (cin>>s)
{
      if (s=="0")
         return 0;

      unsigned long long int a = 0;

      unsigned long long int n;
      istringstream buffer(s);
      buffer>>n;    

      for (unsigned long long int i=1;i<=n;i++)
      {
          string str="";
          unsigned long long int k = i;
          while (k>0)
          {
                str+= (k%10)+48;
                k/=10;
          }

          if (check(str)==false)
             a++;

      }
      cout<<n<<": "<<n-a<<endl;

}
return 0;
}
AMiR SAYS

I haven't read your whole source code, but I guess it is not needed to use long long as it is much slower than int in some operations.

A.Araghian SAYS

I was stuck on this problem for some time too.

My approach to this problem was to treat the integer input as a string(e.g. str),then change every character bigger than 4 (e.g. x) to x-1 and keep the characters less than 4 as they were.Now you have a string which is in base 9(since every chacacter in it is now less than 9). All you have to do now is to convert it to base 10 again and you have your answer!

(proof of this is relatively obvious)

Daneshvar Amrollahi SAYS

Thanks for your answers. I got it.