CODEWITHSUNDEEP
c++algorithmmath
user7302801
user7302801

Reputation: 121

Find sequence of consecutive numbers which's multiple is N

I have an exercise with an input N and it wants me to find a sequence of consecutive numbers which's multiple is equal to N. Example 

Input | Output
  60   | 3 5

3*4*5=60

What i have tried 

cin>>b;
for (int i = 2; i <=b; ++i)
{
    c=1;
    for (int j = i; j <=b; ++j)
    {
        c*=j;
        if(c==b){
            cout<<i<<" "<<j<<endl;
            return 0;
        }else if(c>b){
            j=b;
        }
    }
}

Upvotes: 0

Views: 386

Answers (2)

jrusev
jrusev

Reputation: 46

Here is a working solution in Python (see end of the post for C++ version):

def seq_with_product(n):
    """Return a sequence of consecutive numbers whose product is n."""
    i, curr_prod = 1, 1
    max_j = int(n**0.5) + 1 # n**0.5 is square root of n
    for j in range(2, max_j + 1):
        curr_prod *= j
        while curr_prod > n and i < j-1:
            curr_prod /= i
            i += 1
        if curr_prod == n:
            return range(i, j+1)
    return []

Let i and j be the start and end number in the current sequence. You start from the sequence with the smallest product [1, 2], and check if it is smaller than the given target n. If it is, you want to increase the product, so you include the next number by increasing j. As soon as you get to a product which is larger, you start removing numbers from the product, starting from the smallest (the while loop). If you get the exact product, your answer are the numbers between i and j. So for example, this is how you reach the answer to 60:

[1, 2]          # too small, include the next number
[1, 2, 3]       # too small, include the next number
[1, 2, 3, 4]    # too small, include the next number
[1, 2, 3, 4, 5] # too big, remove the first number
[2, 3, 4, 5]    # too big, remove the first number
[3, 4, 5]       # found

Note that you don't need to consider numbers greater than the square root of the target number plus one, so you can stop at max_j.

In C++, it would be something like:

int i = 1, curr_prod = 1;
int max_j = sqrt(n) + 1;
for (int j = 2; j <= max_j; j++) {
  curr_prod *= j;
  while (curr_prod > n && i < j - 1) {
    curr_prod /= i;
    i += 1;
  }
  if (curr_prod == n) cout << i << " " << j << endl;
}

Upvotes: 1

Frank Puffer
Frank Puffer

Reputation: 8215

Because of this assignment, the inner loop will never terminate if no sequence with the given starting value i is found: 

else if (c > b) {
    j = b;
}

Instead you should do this:

else if (c > b) {
    break;
}

This will terminate the inner loop and check for a sequence with the next start value i+1.

You should also consider the (very common) case that the only sequence contains only one element which is the number N itself.

Upvotes: 1

Related Questions