Do-while error

[awkedd]

Determine the two numbers a,b with the properties:
- a*b = n
- a < = b
- the difference b-a is minimum

example :
input : 70
output: 7 10


Here is my code :

 
#include <iostream>
#include<math.h>
using namespace std;
int n,a,b;
int main()
{
    cin>>n;
    if( sqrt(n)== int (sqrt(n)))
    {
        cout<<sqrt(n)<<" "<<sqrt(n);
    }
    else
    {
    a=b=sqrt(n);
    do
    {
        a--;
        b++;
    }
    while(a*b==n);
    }
    cout<<a<<" "<<b;
   return 0; }

why doesn't it work ?

[TarikNeaj]

if( sqrt(n)== int (sqrt(n))) no idea what the "int" is doing in there. Remove it.

But what Im really wondering is about the actual ifstatement, isint this if( sqrt(n)== (sqrt(n))) always true? Im pretty sure its always true. if "n" is entered as 2. sqrt2 is obviously equal to sqrt2 no?

Edit: Did not know that woah

[awkedd]

in class the computer science teacher said that one way we can verify if n is a perfect square is to check if sqrt(n) is integer and showed us that line if( sqrt(n)== int (sqrt(n))) , apparently is works.

[Ganado]

@TarikNeaj Pretty sure he's testing to see if it's a perfect square there, which would make b -a be 0 and therefore a minimum.

I think one of your problems is the condition of your do-while loop. You loop while a*b==n, so the only way it will get out of this loop is when a*b != n, which directly goes against the requirement of your problem.

Also, a problem is that if you enter a perfect square (ex: 49), it enters the if statement, but in this branch of the problem, a and b are never set and therefore you have undefined behavior when you print line 23.

[awkedd]

@Ganado , now it doesn't output anything

[Ganado]

What is your code now? Also in case you didn't see my edit I'll post it here again

Also, a problem is that if you enter a perfect square (ex: 49), it enters the if statement, but in this branch of the problem, a and b are never set and therefore you have undefined behavior when you print line 23.

[awkedd]

#include <iostream>
#include<math.h>
using namespace std;
int n,a,b;
int main()
{
    cin>>n;
    a=b=sqrt(n);
    
    if( sqrt(n)== int (sqrt(n)))
    {
        cout<<a<<" "<<b;
    }
    else
    {

    do
    {
        a--;
        b++;
    }
    while(a*b!=n);
    }
    cout<<a<<" "<<b;
   return 0; }

[Ganado]

The logic of how you try to account for non-square numbers just seems to be wrong.
Let's say you enter 7, a prime number. It's only factors are 1 and 7.
The integer sqrt of 7 is 2, so now a == b == 2.

In your while loop now, you decrement a and increment b. This is not guaranteed to produce a number where a * b equals your original n.
For 7, you'll get:
a = 2
b = 2
while loop:
--> a = 1
--> b = 3
--> a = 0
--> b = 4
... which as you discovered, makes infinite loop since a*b will never be able to equal n.

I don't know a solution to your problem off the top of my head, it more about math logic than coding itself.
_____________________
I guess a brute-force way to do it is to keep track of a list of a factors of your given number n, and then compare each while keeping track of which combination gets the the smallest abs(b - a).

[awkedd]

the problem is that : 1 ≤ n ≤ 1.000.000.000

[Ganado]

I won't do the whole thing for you, but here is an example of a program that generates a list of factor pairs:

#include <vector>
#include <iostream>

struct NumberPair {
    NumberPair(int num1, int num2)
    : n1(num1),
      n2(num2)
    {}
    int n1;
    int n2;
};

int main()
{
    std::vector<NumberPair> factor_pairs;
    
    int n;
    std::cin >> n;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i * j == n)
                factor_pairs.push_back(NumberPair(i, j));
        }
    }
    
    for (int i = 0; i < factor_pairs.size(); i++)
    {
        std::cout << factor_pairs[i].n1 << " " << factor_pairs[i].n2 << std::endl;
    }
}

If you haven't learned what vectors or structs are, sorry. Vectors are dynamic arrays and structs are just a way of organizing data together. You don't have to use this them solve this.

Try running this program and enter 24.
The output will be

2 12
3 8
4 6
6 4
8 3
12 2

So these are your factor pairs, as in, all of them make a product of 24.
What you then need to do is find which pair gets you the minimal absolute value of (n2 - n1).
In this case, it would be 4 and 6, and b would need to be 6 since it's the larger number.

This could be done without using an array if you keep track of the minimal difference inside the for loop itself.

One more thing I'll throw in, this doesn't involve structs or arrays:

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            // see if i * j equals n. If it does, see if the absolute value of i - j
            // is the minimum value seen so far.
            // (You'll need a variable to keep track of the minimal value so far)
            // If it is, make the new minimum value be abs( i - j),
            // and make b = std::max(i, j)
            // and make a = std::min(i, j)
        }
    }

(Heh, I guess I did end up doing most of it, but I don't mind since you at least first attempted to do it yourself).

[awkedd]

Thanks !

[keskiverto]

Nested loops?

a*b == n
a <= b

=>

b == n/a
a <= sqrt(n)

b-a is minimal, when a is the largest divisor of n that is <= sqrt(n)

Start from the sqrt(n) and go downwards until you have a divisor. Calculate b from a.

You almost had it in the beginning, but you don't have to check for "perfect square" separately.

[Ganado]

Hey I thought of the most brute-force way :P didn't say it was the best way