3
\$\begingroup\$

A lucky number is defined as a positive integer whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not. I need to check if a given number is evenly divisible by any lucky number or not.

Now, suppose I want to add all Lucky Numbers under a given integer [N] to a vector, without using recursion. For the sake of simplicity, let N = 1000.

I came up with an approach to just check each digit of all the numbers under [N] by making separate loops for 1 digit numbers, 2 digit numbers etc.

for(int number=0;number<10;number++) {if(((number%10==4)||(number%10==7))) {lucky.push_back(number);}} //1 Digit Lucky Numbers
for(int number=10;number<100;number++) {if(((number%10==4)||(number%10==7))&&(((number/10)%10==7)||((number/10)%10==4))) {lucky.push_back(number);}} //2 Digit Lucky Numbers
for(int number=100;number<1000;number++) {if(((number%10==4)||(number%10==7))&&(((number/10)%10==7)||((number/10)%10==4))&&(((number/100)%10==7)||((number/100)%10==4))) {lucky.push_back(number);}} //3 Digit Lucky Numbers
for(int number=10;number<100;number++) {if(((number%10==4)||(number%10==7))&&(((number/10)%10==7)||((number/10)%10==4))&&(((number/100)%10==7)||((number/100)%10==4))&&(((number/1000)%10==7)||((number/1000)%10==4))) {lucky.push_back(number);}} //4 Digit Lucky Numbers

I was thinking that this could roughly be converted to something along these lines but I am not quite able to come up with what exactly to do.

for(number;number<10*itr_counter;number++)
    {
    if(((number%10*itr_counter==4)||(number%10*itr_counter==7))) {lucky.push_back(number);}
    itr_counter*=10;
    }

I basically want to check each digit of all 1 digit numbers by taking modulo 10 and checking if the digits are 4 or 7. Similarly for a number consisting of X digits, I am taking modulo and dividing the number by 10, 100 and so on to check against 4 or 7.

Can someone help me optimise the first block of code into something smaller and more efficient? Something along the lines of the second block of code would work.

The Program

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

int main()
{
int in_num;
cin>>in_num;

//This Part Needs to be Optimised
vector<int>lucky;
for(int number=0;number<10;number++) {if(((number%10==4)||(number%10==7))) {lucky.push_back(number);}} //1 Digit Lucky Numbers
for(int number=10;number<100;number++) {if(((number%10==4)||(number%10==7))&&(((number/10)%10==7)||((number/10)%10==4))) {lucky.push_back(number);}} //2 Digit Lucky Numbers
for(int number=100;number<1000;number++) {if(((number%10==4)||(number%10==7))&&(((number/10)%10==7)||((number/10)%10==4))&&(((number/100)%10==7)||((number/100)%10==4))) {lucky.push_back(number);}} //3 Digit Lucky Numbers
for(int number=10;number<100;number++) {if(((number%10==4)||(number%10==7))&&(((number/10)%10==7)||((number/10)%10==4))&&(((number/100)%10==7)||((number/100)%10==4))&&(((number/1000)%10==7)||((number/1000)%10==4))) {lucky.push_back(number);}} //4 Digit Lucky Numbers
//This Part Needs to be Optimised

int flag=0;
for(unsigned int index=0;index<lucky.size();index++)
    {
    if(in_num%lucky[index]==0) {flag=1; break;}
    }
if(flag==1) {cout<<"YES";}
else {cout<<"NO";}
return 0;
}
\$\endgroup\$
3
\$\begingroup\$

It is fairly straightforward to generate a vector with all the values. First, you should treat all the same length numbers as a group. The values 4 and 7 would be in a singledigit vector. To get the twodigit vector, simply go through the previous vector, multiplying each by 10 and then adding 4 to push back a value and add 7 to push back another value.

vector<int> lucky;
vector<int> current;
vector<int> next;
current.push_back(4);
current.push_back(7);
lucky.push_back(4);
lucky.push_back(7);
int value=0;
while(value < N)
{
   for(unsigned int i=0;i<current.size();++i)
   {
       value=current[i]*10+4;
       next.push_back(value);
       lucky.push_back(value);
       value=current[i]*10+7;
       next.push_back(value);
       lucky.push_back(value);
   }

   current=next;
   next.clear();
}
\$\endgroup\$
  • \$\begingroup\$ I would only use a single vector, but otherwise good work. \$\endgroup\$ – Deduplicator Nov 13 '15 at 0:19
2
\$\begingroup\$

Well, there's lots to improve about your program.

  1. Consider adopting any of the common styles for code-formatting.
    As-is, your current formatting seriously impedes readability.

  2. #include <bits/stdc++.h> is a bad idea, sharply limiting portability ad increasing compile-times. See: How does #include <bits/stdc++.h> work in C++?
    Just include those headers you need, which are <vector> and <iostream>.

  3. You are courting conflicting symbols and general bafflement with any minor change of your toolchain. See: Why is using namespace std; considered bad practice?

  4. You are using the popular for-if-antipattern. See Introducing the for-if anti-pattern
    Why don't you just enumerate the ones you are actually interested in?

  5. A for-range-loop is simpler than explicitly using iterators/indices. Unless you actually need them.

  6. In the end you don't actually want that whole list, only whether one of them divides your input-number. So why store them at all, and why also those bigger than the input-number?

  7. return 0; is implicit for main in C++.

Doing it as it should be done, with recursion on coliru:

#include <stdio.h>

int luckydiv_helper(long in, long num, int free) {
    return !free
        ? !(in % num)
        : luckydiv_helper(in, 10 * num + 4, free - 1)
            || luckydiv_helper(in, 10 * num + 7, free - 1);
}

int luckydiv(long in) {
    long abort = in;
    for(int digits = 1; abort; digits++, abort /= 10)
        if(luckydiv_helper(in, 0, digits))
            return 1;
    return !in;
}

int main() {
    long in;
    if(scanf("%ld", &in) != 1 || in < -999999999 || in > 999999999) {
        fprintf(stderr, "You didn't enter a number between -999999999 and "
            "+999999999. Aborting.\n");
        // A long can represent all 9-digit decimal numbers.
        return 1;
    }
    printf("%ld ", in);
    if(in < 0) in = -in;
    puts(luckydiv(in) ? "YES" : "NO");
}

A way to efficiently get all "lucky" numbers without recursion:

#include <limits>
#include <vector>

template<class T> std::vector<T> luckyvector() {
    std::vector<T> v = {4, 7};
    const auto limit4 = (std::numeric_limits<T>::max() - 4) / 10;
    const auto limit7 = (std::numeric_limits<T>::max() - 7) / 10;
    T x;
    for(size_t i = 0; (x = v[i]) <= limit7; i++) {
        v.push_back(x * 10 + 4);
        v.push_back(x * 10 + 7);
    }
    if(x <= limit4)
        v.push_pack(x * 10 + 4);
    return v;
}
\$\endgroup\$
  • \$\begingroup\$ You used recursion in luckydiv_helper(), and the task forbids recursion. \$\endgroup\$ – 200_success Nov 13 '15 at 0:52
  • \$\begingroup\$ @200_success: I gave a way to do the task the program solves efficiently with recursion, yes. And a way to just generate a vector with all those numbers, without recursion. Clarified what is what. \$\endgroup\$ – Deduplicator Nov 13 '15 at 1:06
0
\$\begingroup\$
#include <iostream>
#include <vector>

bool is_lucky(int check_num)
{
while(check_num!=0)
    {
    if((check_num%10!=4)&&(check_num%10!=7))
        {
        return false;
        }
    check_num/=10;
    }
return true;
}

int main()
{
std::vector <long long> lucky;
for(int in_num=1;in_num<1000;in_num++)
    {
    if(is_lucky(in_num))
        {
        lucky.push_back(in_num);
        }
    }
}

Even though I am still using the for-if anti-pattern as Deduplicator pointed out, I was finally able to make the is_lucky function which maybe less efficient and a lesser intelligent way to do it than the other ones posted, seems to be the shortest way to do the task.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.