# Find numbers that divide X and Y to produce the same remainder

Given two integers **X** and **Y**, the task is to find and print the numbers that divide X and Y to produce the same remainder.**Examples:**

Input:X = 1, Y = 5Output:1, 2, 4Explanation:

Let the number be M. It can be any value in the range [1, 5]:

If M = 1, 1 % 1 = 0 and 5 % 1 = 0

If M = 2, 1 % 2 = 1 and 5 % 2 = 1

If M = 3, 1 % 3 = 1 and 5 % 3 = 2

If M = 4, 1 % 4 = 1 and 5 % 4 = 1

If M = 5, 1 % 5 = 1 and 5 % 5 = 0

Therefore, the possible M values are 1, 2, 4Input:X = 8, Y = 10Output:1, 2

**Naive Approach:** The naive approach for this problem is to check the modulo value for all the possible values of M in the range [1, max(X, Y)] and print the value of M if the condition satisfies.

Below is the implementation of the above approach:

## C++

`// C++ program to find numbers` `// that divide X and Y` `// to produce the same remainder` `#include <iostream>` `using` `namespace` `std;` `// Function to find` `// the required number as M` `void` `printModulus(` `int` `X, ` `int` `Y)` `{` ` ` `// Finding the maximum` ` ` `// value among X and Y` ` ` `int` `n = max(X, Y);` ` ` `// Loop to iterate through` ` ` `// maximum value among X and Y.` ` ` `for` `(` `int` `i = 1; i <= n; i++) {` ` ` `// If the condition satisfies, then` ` ` `// print the value of M` ` ` `if` `(X % i == Y % i)` ` ` `cout << i << ` `" "` `;` ` ` `}` `}` `// Driver code` `int` `main()` `{` ` ` `int` `X, Y;` ` ` `X = 10;` ` ` `Y = 20;` ` ` `printModulus(X, Y);` ` ` `return` `0;` `}` |

## Java

`// Java program to find numbers` `// that divide X and Y` `// to produce the same remainder` `class` `GFG{` ` ` `// Function to find` `// the required number as M` `static` `void` `printModulus(` `int` `X, ` `int` `Y)` `{` ` ` `// Finding the maximum` ` ` `// value among X and Y` ` ` `int` `n = Math.max(X, Y);` ` ` ` ` `// Loop to iterate through` ` ` `// maximum value among X and Y.` ` ` `for` `(` `int` `i = ` `1` `; i <= n; i++) {` ` ` ` ` `// If the condition satisfies, then` ` ` `// print the value of M` ` ` `if` `(X % i == Y % i)` ` ` `System.out.print(i + ` `" "` `);` ` ` `}` `}` ` ` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` ` ` `int` `X, Y;` ` ` `X = ` `10` `;` ` ` `Y = ` `20` `;` ` ` `printModulus(X, Y);` `}` `}` `// This code is contributed by Princi Singh` |

## Python3

`# Python program to find numbers` `# that divide X and Y` `# to produce the same remainder` `# Function to find` `# the required number as M` `def` `printModulus( X, Y):` ` ` ` ` `# Finding the maximum` ` ` `# value among X and Y` ` ` `n ` `=` `max` `(X, Y)` ` ` `# Loop to iterate through` ` ` `# maximum value among X and Y.` ` ` `for` `i ` `in` `range` `(` `1` `, n ` `+` `1` `):` ` ` `# If the condition satisfies, then` ` ` `# print the value of M` ` ` `if` `(X ` `%` `i ` `=` `=` `Y ` `%` `i):` ` ` `print` `(i,end` `=` `" "` `)` `# Driver code` `X ` `=` `10` `Y ` `=` `20` `printModulus(X, Y)` `# This code is contributed by Atul_kumar_Shrivastava` |

## C#

`// C# program to find numbers` `// that divide X and Y` `// to produce the same remainder` `using` `System;` `class` `GFG{` `// Function to find` `// the required number as M` `static` `void` `printModulus(` `int` `X, ` `int` `Y)` `{` ` ` `// Finding the maximum` ` ` `// value among X and Y` ` ` `int` `n = Math.Max(X, Y);` ` ` `// Loop to iterate through` ` ` `// maximum value among X and Y.` ` ` `for` `(` `int` `i = 1; i <= n; i++) {` ` ` `// If the condition satisfies, then` ` ` `// print the value of M` ` ` `if` `(X % i == Y % i)` ` ` `Console.Write(i + ` `" "` `);` ` ` `}` `}` `// Driver code` `public` `static` `void` `Main()` `{` ` ` `int` `X, Y;` ` ` `X = 10;` ` ` `Y = 20;` ` ` `printModulus(X, Y);` `}` `}` `// This code is contributed by AbhiThakur` |

## Javascript

`<script>` `// Javascript program to find numbers` `// that divide X and Y` `// to produce the same remainder` `// Function to find` `// the required number as M` `function` `printModulus(X, Y)` `{` ` ` `// Finding the maximum` ` ` `// value among X and Y` ` ` `var` `n = Math.max(X, Y);` ` ` `// Loop to iterate through` ` ` `// maximum value among X and Y.` ` ` `for` `(` `var` `i = 1; i <= n; i++) {` ` ` `// If the condition satisfies, then` ` ` `// print the value of M` ` ` `if` `(X % i == Y % i)` ` ` `document.write(i+` `" "` `);` ` ` `}` `}` `// Driver code` `X = 10;` `Y = 20;` `printModulus(X, Y);` `// This code is contributed by noob2000.` `</script>` |

**Output:**

1 2 5 10

**Time Complexity:** O(max(X, Y))**Efficient Approach:** Let’s assume that **Y** is greater than **X** by a difference of **D**.

- Then
**Y**can be expressed as

Y = X + D and Y % M = (X + D) % M = (X % M) + (D % M)

- Now, the condition becomes
**whether X % M and X % M + D % M are equal or not**. - Here, since X % M is common on both the sides, the value of M is true if for some M,
**D % M = 0**. - Therefore, the required values of M will be the
**factors of D**.

Below is the implementation of the above approach:

## CPP

`// C++ program to find numbers` `// that divide X and Y to` `// produce the same remainder` `#include <iostream>` `using` `namespace` `std;` `// Function to print all the possible values` `// of M such that X % M = Y % M` `void` `printModulus(` `int` `X, ` `int` `Y)` `{` ` ` `// Finding the absolute difference` ` ` `// of X and Y` ` ` `int` `d = ` `abs` `(X - Y);` ` ` `// Iterating from 1` ` ` `int` `i = 1;` ` ` `// Loop to print all the factors of D` ` ` `while` `(i * i <= d) {` ` ` `// If i is a factor of d, then print i` ` ` `if` `(d % i == 0) {` ` ` `cout << i << ` `" "` `;` ` ` `// If d / i is a factor of d,` ` ` `// then print d / i` ` ` `if` `(d / i != i)` ` ` `cout << d / i << ` `" "` `;` ` ` `}` ` ` `i++;` ` ` `}` `}` `// Driver code` `int` `main()` `{` ` ` `int` `X = 10;` ` ` `int` `Y = 26;` ` ` `printModulus(X, Y);` ` ` `return` `0;` `}` |

## Java

`// Java program to find numbers` `// that divide X and Y to` `// produce the same remainder` `import` `java.util.*;` `class` `GFG{` ` ` `// Function to print all the possible values` `// of M such that X % M = Y % M` `static` `void` `printModulus(` `int` `X, ` `int` `Y)` `{` ` ` `// Finding the absolute difference` ` ` `// of X and Y` ` ` `int` `d = Math.abs(X - Y);` ` ` ` ` `// Iterating from 1` ` ` `int` `i = ` `1` `;` ` ` ` ` `// Loop to print all the factors of D` ` ` `while` `(i * i <= d) {` ` ` ` ` `// If i is a factor of d, then print i` ` ` `if` `(d % i == ` `0` `) {` ` ` `System.out.print(i+ ` `" "` `);` ` ` ` ` `// If d / i is a factor of d,` ` ` `// then print d / i` ` ` `if` `(d / i != i)` ` ` `System.out.print(d / i+ ` `" "` `);` ` ` `}` ` ` `i++;` ` ` `}` `}` ` ` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` ` ` `int` `X = ` `10` `;` ` ` `int` `Y = ` `26` `;` ` ` ` ` `printModulus(X, Y);` `}` `}` `// This code is contributed by Princi Singh` |

## Python3

`# Python program to find numbers` `# that divide X and Y to` `# produce the same remainder` `# Function to prall the possible values` `# of M such that X % M = Y % M` `def` `printModulus(X, Y):` ` ` `# Finding the absolute difference` ` ` `# of X and Y` ` ` `d ` `=` `abs` `(X ` `-` `Y);` ` ` `# Iterating from 1` ` ` `i ` `=` `1` `;` ` ` `# Loop to prall the factors of D` ` ` `while` `(i ` `*` `i <` `=` `d):` ` ` `# If i is a factor of d, then pri` ` ` `if` `(d ` `%` `i ` `=` `=` `0` `):` ` ` `print` `(i, end` `=` `"");` ` ` `# If d / i is a factor of d,` ` ` `# then prd / i` ` ` `if` `(d ` `/` `/` `i !` `=` `i):` ` ` `print` `(d ` `/` `/` `i, end` `=` `" "` `);` ` ` ` ` `i` `+` `=` `1` `;` ` ` `# Driver code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `X ` `=` `10` `;` ` ` `Y ` `=` `26` `;` ` ` `printModulus(X, Y);` `# This code contributed by Princi Singh` |

## C#

`// C# program to find numbers` `// that divide X and Y to` `// produce the same remainder` `using` `System;` `public` `class` `GFG{` ` ` `// Function to print all the possible values` `// of M such that X % M = Y % M` `static` `void` `printModulus(` `int` `X, ` `int` `Y)` `{` ` ` `// Finding the absolute difference` ` ` `// of X and Y` ` ` `int` `d = Math.Abs(X - Y);` ` ` ` ` `// Iterating from 1` ` ` `int` `i = 1;` ` ` ` ` `// Loop to print all the factors of D` ` ` `while` `(i * i <= d) {` ` ` ` ` `// If i is a factor of d, then print i` ` ` `if` `(d % i == 0) {` ` ` `Console.Write(i+ ` `" "` `);` ` ` ` ` `// If d / i is a factor of d,` ` ` `// then print d / i` ` ` `if` `(d / i != i)` ` ` `Console.Write(d / i+ ` `" "` `);` ` ` `}` ` ` `i++;` ` ` `}` `}` ` ` `// Driver code` `public` `static` `void` `Main(String[] args)` `{` ` ` ` ` `int` `X = 10;` ` ` `int` `Y = 26;` ` ` ` ` `printModulus(X, Y);` `}` `}` ` ` `// This code contributed by Princi Singh` |

## Javascript

` ` `<script>` ` ` `// Javascript program to find numbers` ` ` `// that divide X and Y to` ` ` `// produce the same remainder` ` ` `// Function to print all the possible values` ` ` `// of M such that X % M = Y % M` ` ` `function` `printModulus(X, Y)` ` ` `{` ` ` ` ` `// Finding the absolute difference` ` ` `// of X and Y` ` ` `var` `d = Math.abs(X - Y);` ` ` `// Iterating from 1` ` ` `var` `i = 1;` ` ` `// Loop to print all the factors of D` ` ` `while` `(i * i <= d) {` ` ` `// If i is a factor of d, then print i` ` ` `if` `(d % i == 0) {` ` ` `document.write(i + ` `" "` `);` ` ` `// If d / i is a factor of d,` ` ` `// then print d / i` ` ` `if` `(d / i != i)` ` ` `document.write(parseInt(d / i) + ` `" "` `);` ` ` `}` ` ` `i++;` ` ` `}` ` ` `}` ` ` `// Driver code` ` ` `var` `X = 10;` ` ` `var` `Y = 26;` ` ` `printModulus(X, Y);` `// This code is contributed by rrrtnx.` ` ` `</script>` |

**Output:**

1 16 2 8 4

* Time Complexity Analysis O(sqrt(D))*, where D is the difference between the values X and Y.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.