Check if is it possible to get to a point that is presented by a number [closed]

Question

Problem description from an Iranian online course, translated with the help of Google Translate:

Tired of coding, Mehdi has gone on to his childhood games. But because he doesn't know who to play with, he has to change the rules of the game and play solitaire. To begin with, he wants to play solitaire "Walnut, Break Out".

Mehdi is standing n cm from the wall and wants to reach the wall. To do this, he can extend his leg forward, or transverse his leg forward. The goal is for him to stretch his legs and move forward so that he can tangle with the wall at the end. But Mehdi doesn't code anymore, so you need to help him figure out how to win this game. That is, tell him to stretch his leg a few times and cross a few times to get the exact distance. The problem is about checking whether we can get to a wall that is represented with a number, by horizontal and vertical moves or not. If we can, print one of the correct answers and we cant, print -1.

We have three input values: The distance to the wall \$ n \$ , the foot length \$ x\$ , and the foot width \$ y\$ . The values are restricted by $$ 1 \le n,x,y \le 100\,000 \, . $$

We have to check if \$ n \$ is a multiple of \$ x \$ plus a multiple of \$ y \$. For example if \$n = 10 \$and \$x = 2 , y=3\$ , we can reach to \$10\$ with multiplying \$2 \cdot 2 + 3 \cdot 2 \$, or \$2 \cdot 5 + 3 \cdot 0 \$.

I wrote this code for it. I get correct answers for most of the test cases except one, and 2 errors for a time limit exceeded. I am looking for an optimized and faster solution.

#include<iostream>
using namespace std;
int main()
{
    int n,x,y;
    int x1,y1;
    cin>>n>>x>>y;
    bool flag = false;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n+1;j++)
        {
            if (x * i + j * y == n)
                {
                    flag = true;
                    x1=i;
                    y1=j;
                }
        }
         if(flag)
            break;
    }
    if(flag == false)
        cout<<"-1";
    else
    cout<<x1<<" "<<y1;

    return 0;
}

Answer 1

General remarks

This

using namespace std;

is considered bad practice, see for example Why is “using namespace std” considered bad practice? on Stack Overflow.

Consistent indenting and spacing increases the legibility of the code.

Use curly braces for if/else blocks even if they consist only of a single statement.

Enable all compiler warnings and fix them, such as

std::cout<<x1<<" "<<y1;
// Variable 'x1' may be uninitialized when used here
// Variable 'y1' may be uninitialized when used here

Choose better variable names:

bool flag = false;

does not indicate what the flag is used for.

Testing boolean values: This may be opinion-based, but I prefer

if (!flag) { ... }

over

if (flag == false) { ... }

The return statement in main() is optional, and can be omitted.

Program structure

Separating the actual computation from the I/O makes the main method short, increases the clarity of the program, and allows you to add unit tests easily. In addition, you can “early return” from the function if a solution is found, so that the flag, x1, y1 variables becomes obsolete.

As of C++17 you can return an optional which contains a value (the solution as a pair) or not.

With these suggestions, the program could look like this:

#include <iostream>
#include <optional>

std::optional<std::pair<int, int>> solveSteps(int x, int y, int n) {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            if (x * i + j * y == n) {
                // Return solution:
                return std::make_optional(std::make_pair(i, j));
            }
        }
    }
    // No solution found:
    return std::nullopt;
}

int main()
{
    int n, x, y;
    std::cin >> n >> x >> y;

    auto solution = solveSteps(x, y, n);
    if (solution) {
        std::cout << solution->first << " " << solution->second << "\n";
    } else {
        std::cout << "-1\n";
    }
}

Increasing the performance

First you can increase i and j in steps of x and y, respectively. That reduces the number of iterations and save the multiplications:

std::optional<std::pair<int, int>> solveSteps(int x, int y, int n) {
    for (int i = 0; i <= n; i += x) {
        for (int j = 0; j <= n; j += y) {
            if (i + j == n) {
                // Return solution:
                return std::make_optional(std::make_pair(i/x, j/y));
            }
        }
    }
    // No solution found:
    return std::nullopt;
}

The next improvement is to get rid of the inner loop: After moving i steps of width x you only have to check if the remaining distance is a multiple of y:

std::optional<std::pair<int, int>> solveSteps(int x, int y, int n) {
    for (int i = 0; i <= n; i += x) {
        if ((n - i) % y == 0) {
            // Return solution:
            return std::make_optional(std::make_pair(i/x, (n-i)/y));
        }
    }
    // No solution found:
    return std::nullopt;
}

Another improvement would be to check if y > x. In that case it is more efficient to iterate in steps of width y and check if the remaining distance is a multiple of x.

Mathematics

Some final remarks on how this can be solved mathematically, with links for further reading.

What you are looking for is solution \$ (i, j) \$ to the equation $$ n = i x + j y $$ with non-negative integers \$ i, j \$. This is related to Bézout's identity. In particular, a solution can only exist if \$ n \$ is a multiple of the greatest common divisor \$ \gcd(x, y) \$, which is efficiently determined with the euclidean algorithm. In that case it is easy to check if a solution with non-negative numbers exists, compare e.g. Finding positive Bézout coefficients on Mathematics Stack Exchange.