Challenge to carry a number to 0

Question

Challenge to carry a number to 0

Navigation

#1 by (1 votes)

0

The number of minimum steps must be determined for an integer N to reach 0, following these rules: 1) If N is the product of two numbers a and b, other than 1, then replace N with the max (a, b) 2) Otherwise, replace N with N-1

Example: The number 36 has 5 steps to get to 0 because:

      36-->6-->3-->2-->1-->0

This because 36 = 6 * 6, N changes to the maximum (6). Then 6 = 3 * 2, N changes to the maximum (3). Note that if in 36 they had taken a and b as 18 and 2, then the number of steps would have been 6, so it would not be the minimum.

   36-->18-->9-->3-->2-->1-->0

Entry: An integer Q that will be the number of cases to evaluate, next to Q times the integer N that we want to evaluate. Exit: Minimum number of steps to bring each number to 0

Solution attempt: #include #include

 using namespace std;
 int Q, N, i, a, b;
 int main(){ 
 cin>> Q;
 for (i=0;i<Q;i++){
    cin>>N;
    int contador = 0;
    int l = N;
    for (int k=0;k<N;k++){
        if (l>0 && l == a*b){
            l=max(a,b);
            contador ++;
        }
        else if (l>0){
            l=l-1;
            contador ++;
        }
        }
        cout<<contador<<endl; 
    }
return 0;
}

However, I did not know how to determine the two numbers a and b that multiplied den N.

c++

asked by J O Panda 24.10.2018 в 01:11

source

1 answer

Why do you execute the function when selecting the radio button, but do not select it, jquery? Error 5123 restore BD SQL Server 2012

score 1 · Answer 1

I think you should focus on determining divisors of the number to evaluate, for example with N = 36 :

Dividers are

2 * 18
3 * 12
4 * 9
6 * 6
....

Now, the solution I propose is to iterate and verify for each pair of numbers, to obtain a and b we do a cycle starting with 1 and for each iteration:

If N % i == 0 then a = i and b = N / i (eg 36% 2 = 0 then a = 2, b = 18).

Then verify if the difference between bya is less than or equal to zero, with this condition we will find the most useful pair of numbers, if so, then we go to step 3 and step 1 with i+1 .

We do the maximum equal to a and verify that b is not equal to 1 (here we apply the rules), if b = 0 then max -= 1 , otherwise we do nothing and break the iteration.

At the end of the new value of N it would be max and also the first number found. I leave you the sample code that I made:

#include <iostream>
using namespace std;

int Q = 0;
int N;

int max();

int main()
{
    cout << "Numero a evaluar:  ";
    cin >> N;
    cout << N;
    do{
        N = max();      
        cout << "--->" << N;
        Q++;    
    }while(N != 0);     
    cout << "\nMinimo numero de pasos: " << Q;
    return 0;   
}

int max()
{
    int a, b;
    int max = 0;
    for(int i = 2; i <= N; i++)
    {
        if(N % i == 0)
        {
            a = i;
            b = N / i;
            if(b - a <= 0)
            {
                max = a;
                if(b == 1){
                    max -= 1;
                }
                break;
            }
        }
    }
    return max;
}

With N = 36 the result is:

Numero a evaluar:  36
36--->6--->3--->2--->1--->0
Minimo numero de pasos: 5

Surely there must be a simpler way, but I hope and help you in something, greetings.