Two Bags of Potatoes · Interview Problem

Back to problems

Codeforces

Easy

Math

Number Theory

Two Bags of Potatoes

Find the smallest integer number of potatoes to move so that one bag has a total divisible by a given number.

Acceptance 0%

Start Practice

Also Available On

Other platform versions and source mappings for the same problem.

Codeforces 239A

gfg

Primary

Problem Statement

You are given two bags containing $y$ and $x$ potatoes, and a number $n$ .

You want to move some positive number of potatoes from the second bag to the first bag so that after the move, the first bag contains a total number of potatoes divisible by $n$ .

Find the smallest number of potatoes you need to move.

The number moved must be at least $1$ and cannot exceed the number of potatoes initially in the second bag.

Input Format

A single line contains three integers $n$ , $x$ , and $y$ .
Here, $x$ is the number of potatoes in the second bag and $y$ is the number of potatoes in the first bag.

Output Format

Output the minimum number of potatoes to move from the second bag to the first bag so that $(y + k)$ is divisible by $n$ for some integer $k \ge 1$ .
If it is impossible, output $-1$ .

Constraints

$1 \le n, x, y \le 10^9$
The moved amount must satisfy $1 \le k \le x$
Use 64-bit integers if needed.

Examples

Sample cases returned by the problem API.

Example 1

Input

5 10 3

Output

Explanation

The first bag has 3 potatoes. Moving 2 potatoes makes it 5, which is divisible by 5. This is the minimum possible move.

Example 2

Input

4 1 8

Output

-1

Explanation

The first bag already has 8 potatoes, which is divisible by 4, but we must move a positive number of potatoes. The smallest positive amount that makes the sum divisible by 4 is 4, which is impossible because the second bag has only 1 potato.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress