12
\$\begingroup\$

I came across this problem and I was wondering if you could help me to improve my solution.

Problem:

Count the number of ways you can reduce a deletable prime to a one digit number.

A "deletable prime" is a prime number where you can delete digits one at a time and still have a prime number.

Input: a number < 8.000.000.000.000.000.000

Example: 4567

enter image description here

Output: number of ways to reduce a deletable prime

Output of example above: 3


#include <algorithm>
#include <iostream>
#include <iterator>
#include <cmath>
#include <vector>

long long RemoveDigit( long long n, unsigned int pos )
{
    const unsigned int base = 10;

    long long factor1 = std::pow( base, pos );
    long long factor2 = std::pow( base, pos + 1 );

    // n / 10^pos * 10^pos => removes all the digits from pos until the least significant digits
    long long truncatedVal1 = ( n / factor1 ) * factor1;

    // n / 10^(pos+1) * 10^(pos+1) => removes all the digits from pos, included until the least significant digits
    long long truncatedVal2 = ( truncatedVal1 / factor2 ) * factor2;

    //delete 1 position by dividing with the 10 then add the remaining digits
    return truncatedVal2 / base + ( n - truncatedVal1 );
}

int CountDigits( long long n )
{
    int noDigits = 0;

    while ( n > 0 )
    {
        noDigits++;
        n /= 10;
    }

    return noDigits;
}

bool isPrime( long long x)
{
    if ( x == 1 )
    {
        return false;
    }

    if ( x == 2 )
    {
        return true;
    }

    long long sqroot = sqrt( x );

    for ( long long d = 2; d <= sqroot; d++ )
    {
        if ( !( x % d ) )
        {
            return false;
        }
    }

    return true;
}

void CountDeletablePrimes( int noDigits, long long delPrime, int & noWays )
{
    for ( int i = 0; i < noDigits; i++ )
    {
        noDigits = CountDigits( delPrime );
        long long newDelPrime = RemoveDigit(delPrime, i);

        if ( isPrime(newDelPrime) )
        {
            if ( newDelPrime / 10 == 0 )
            {
                noWays++;
            }
            else
            {
                CountDeletablePrimes( noDigits, newDelPrime, noWays );
            }
       } 
    }
}

int main()
{
    long long n = 0;

    std::cout << "n = ";
    std::cin >> n;

    int noDigits = CountDigits( n );
    int noWays = 0;

    CountDeletablePrimes( noDigits, n, noWays );

    std::cout << noWays << std::endl;

    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ This is a really interesting problem to work on. I may give it a shot myself. With regards to limiting it by 8e18, without having read your code yet, I am not sure why you went with that limit, given that unsigned long long is at least >= 64 bits. You may be able to implement Boost's multiprecision library for "unlimited" (or at least, more) precision, or the GNU Multiple Precision Arithmetic Library (GMP). \$\endgroup\$ – esote Sep 7 '17 at 21:17
6
\$\begingroup\$

My suggestions:

Don't use std::pow to compute the power of an integral number

Floating point math can lead to errors since they are not guaranteed to be precise. It will be better to create a version of pow that works only with integers.

The following should work:

long long intpow(int base, int n)
{
   if ( n == 0 )
   {
      return 1;
   }

   if ( n == 1 )
   {
      return base;
   }

   int m = n/2;
   long long res = intpow(base, m);
   return (res*res*intpow(base, n%2));
}

Save a bit of computation when computing factor2

You have

long long factor1 = std::pow( base, pos );
long long factor2 = std::pow( base, pos + 1 );

That could have been

long long factor1 = std::pow( base, pos );
long long factor2 = base*factor1;

With the new function, that will be

long long factor1 = intpow(base, pos);
long long factor2 = base*factor1;

Use std::sqrt instead of just sqrt

The standard include file cmath is guaranteed to declare std::sqrt. Some also declare sqrt but in order to make the code portable, use std::sqrt.

Improve isPrime implementation

You have the for loop

for ( long long d = 2; d <= sqroot; d++ )
{
    if ( !( x % d ) )
    {
        return false;
    }
}

It is inefficient since you can avoid half the work by realizing that if the number is not even, it will never be divisible by 2, 4, 6, etc.

Here's my suggestion for an improved version:

bool isPrime( long long x)
{
   if ( x == 1 )
   {
      return false;
   }

   if ( x == 2 )
   {
      return true;
   }

   if ( x % 2 == 0 )
   {
      return false;
   }

   long long sqroot = std::sqrt( x );

   for ( long long d = 3; d <= sqroot; d += 2 )
   {
      if ( !( x % d ) )
      {
         return false;
      }
   }

   return true;
}

Return noWays as the return value

Your signature for CountDeletablePrimes is

void CountDeletablePrimes( int noDigits, long long delPrime, int & noWays);

I think it will be better as

// Return the number of ways.
int CountDeletablePrimes( int noDigits, long long delPrime);

With that, the implementation can be changed to:

int CountDeletablePrimes( int noDigits, long long delPrime)
{
   int noWays = 0;
   for ( int i = 0; i < noDigits; i++ )
   {
      noDigits = CountDigits( delPrime );
      long long newDelPrime = RemoveDigit(delPrime, i);

      if ( isPrime(newDelPrime) )
      {
         if ( newDelPrime / 10 == 0 )
         {
            noWays++;
         }
         else
         {
            noWays += CountDeletablePrimes( noDigits, newDelPrime);
         }
      } 
   }

   return noWays;
}

Here's an updated version of your program with the above changes.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <cmath>
#include <vector>

long long intpow(int base, int n)
{
   if ( n == 0 )
   {
      return 1;
   }

   if ( n == 1 )
   {
      return base;
   }

   int m = n/2;
   long long res = intpow(base, m);
   return (res*res*intpow(base, n%2));
}

long long RemoveDigit( long long n, unsigned int pos )
{
   const unsigned int base = 10;

   long long factor1 = intpow(base, pos); // std::pow( base, pos );
   long long factor2 = base*factor1;      // std::pow( base, pos + 1 );

   // n / 10^pos * 10^pos => removes all the digits from pos until the least significant digits
   long long truncatedVal1 = ( n / factor1 ) * factor1;

   // n / 10^(pos+1) * 10^(pos+1) => removes all the digits from pos, included until the least significant digits
   long long truncatedVal2 = ( truncatedVal1 / factor2 ) * factor2;

   //delete 1 position by dividing with the 10 then add the remaining digits
   return truncatedVal2 / base + ( n - truncatedVal1 );
}

int CountDigits( long long n )
{
   int noDigits = 0;

   while ( n > 0 )
   {
      noDigits++;
      n /= 10;
   }

   return noDigits;
}

bool isPrime( long long x)
{
   if ( x == 1 )
   {
      return false;
   }

   if ( x == 2 )
   {
      return true;
   }

   if ( x % 2 == 0 )
   {
      return false;
   }

   long long sqroot = std::sqrt( x );

   for ( long long d = 3; d <= sqroot; d += 2 )
   {
      if ( !( x % d ) )
      {
         return false;
      }
   }

   return true;
}

int CountDeletablePrimes( int noDigits, long long delPrime)
{
   int noWays = 0;
   for ( int i = 0; i < noDigits; i++ )
   {
      noDigits = CountDigits( delPrime );
      long long newDelPrime = RemoveDigit(delPrime, i);

      if ( isPrime(newDelPrime) )
      {
         if ( newDelPrime / 10 == 0 )
         {
            noWays++;
         }
         else
         {
            noWays += CountDeletablePrimes( noDigits, newDelPrime);
         }
      } 
   }

   return noWays;
}

int main()
{
   long long n = 0;

   std::cout << "n = ";
   std::cin >> n;

   int noDigits = CountDigits( n );
   int noWays = CountDeletablePrimes( noDigits, n);

   std::cout << noWays << std::endl;

   return 0;
}
\$\endgroup\$
  • \$\begingroup\$ In isPrime() you can combine the second and third if statements as: if (x % 2 == 0) { return x == 2; } \$\endgroup\$ – rossum Sep 24 '17 at 9:08
5
\$\begingroup\$
void CountDeletablePrimes( int noDigits, long long delPrime, int & noWays )
{
    for ( int i = 0; i < noDigits; i++ )
    {
        noDigits = CountDigits( delPrime );

This confused me. Normally if a loop has a guard condition which compares the loop variable to another value, changing the other value is a "clever" way of doing break; sometimes it's genuinely clever as a way of maintaining a complex invariant (and should typically have a comment explaining what the invariant is). But when I looked to see why noDigits changes inside the loop, I couldn't find a reason.

In fact, I don't see a reason for calling CountDigits more than once in the entire program. If you delete one digit from a prime with noDigits digits, you get a number with noDigits - 1 digits.


I think there is a bug in the program in a corner case: if n is a one-digit prime, I think the output should be 1, but I think the code will output 0.


I agree with the other existing answer (by R Sahu) that std:pow is not a great option here, but I disagree on the best option. In my opinion, since the only use of pow is to compute powers of ten, it would be best to simply compute an array of powers of ten from 10^0 = 1 to the largest one you'll actually need, which is the length of the input plus or minus one.

I would also consider whether % would make RemoveDigit more readable.


What are the #includes for? The code seems to compile with only <iostream> and <cmath>.


Finally, I note that the specification says

a number < 8.000.000.000.000.000.000

That means that isPrime could be called with numbers on the order of 800.000.000.000.000.000. Trial division would need to run up to numbers on the order of 900.000.000. That's not entirely unreasonable on a modern desktop, but if you find that the program fails some test cases due to timeouts you may need to implement a more sophisticated primality test. That is quite a large subject.

\$\endgroup\$
1
\$\begingroup\$

Be consistent in naming the functions. isPrime starts with a lowercase letter, the others don't.

There have been so many questions here for implementing isPrime that you should use the code from one of the answers instead of implementing it yourself and doing so inefficiently.

The result of the % operator is a number, not a boolean, so don't use the ! operator on it.

Use a simple "\n" instead of std::endl.

\$\endgroup\$
1
\$\begingroup\$

After reading all the comments, I've changed the code accordingly and resulted in what you see below.

I am aware that my implementation on checking the primality of a number is not the best way, but I think in this case it does its job. At first I implemented a sieve of Eratosthenes, but it took a long time to construct for large numbers. Maybe I was doing something wrong...

Anyway, thank you all for your suggestions!

#include <iostream>
#include <vector>

std::vector<long long> powersOfTen = { 1 };

void MakePowersOfTenVector( int noDigits )
{
    powersOfTen.reserve( noDigits );

    for ( int i = 1; i < noDigits; i++ )
    {
        powersOfTen.push_back( 10 * powersOfTen[i - 1] );
    }
}

long long RemoveDigit( long long n, unsigned int pos )
{
    const unsigned int base = 10;

    long long factor1 = powersOfTen[pos];
    long long factor2 = base * factor1;

    // n / 10^pos * 10^pos => removes all the digits from pos until the least significant digits
    long long truncatedVal1 = ( n / factor1 ) * factor1;

    // n / 10^(pos+1) * 10^(pos+1) => removes all the digits from pos, included until the least significant digits
    long long truncatedVal2 = ( truncatedVal1 / factor2 ) * factor2;

    //delete 1 position by dividing with the 10 then add the remaining digits
    return truncatedVal2 / base + n % factor1;
}

int CountDigits( long long n )
{
    int noDigits = 0;

    while ( n > 0 )
    {
        noDigits++;
        n /= 10;
    }

    return noDigits;
}

bool IsPrime( long long x)
{
    if ( x == 1 )
    {
        return false;
    }

    if ( x == 2 )
    {
        return true;
    }

    if ( x % 2 == 0 )
    {
        return false;
    }

    long long sqroot = sqrt( x );

    for ( long long d = 3; d <= sqroot; d += 2 )
    {
        if (  x % d  == 0 )
        {
            return false;
        }
    }

    return true;
}

int CountDeletablePrimes( int noDigits, long long delPrime )
{
    int noWays = 0;

    for ( int i = 0; i < noDigits; i++ )
    {
        long long newDelPrime = RemoveDigit(delPrime, i);

        if ( IsPrime(newDelPrime) )
        {
            if ( newDelPrime / 10 == 0 )
            {
                noWays++;
            }
            else
            {
                noWays += CountDeletablePrimes( noDigits - 1, newDelPrime);
            }
       } 
    }

    return noWays;
}

int main()
{
    long long n = 0;

    std::cout << "n = ";
    std::cin >> n;

    int noDigits = CountDigits( n );
    int noWays = 0;

    if ( noDigits == 1 )
    {
        if ( IsPrime( n ) )
        {
            noWays = 1;
        }
    }
    else
    {
        MakePowersOfTenVector( noDigits );
        noWays = CountDeletablePrimes( noDigits, n );
    }

    std::cout << noWays << "\n";

    return 0;
}
\$\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.