Given two integers A and B, the task is to count the possible values of K such that A%K = B%K. If the count is infinite, print -1.
Examples:
Input: A = 2, B = 4
Output: 2
Explanation: The set of all possible values of K is {1, 2}.
As 2%1 = 4%1 = 0 and 2%2 = 4%2 = 0.Input: A = 5, B = 5
Output: -1
Explanation: There are infinite values of K as all possible integer value of K satisfies the given condition.
Approach: The given problem can be solved using the following observation that all values of A and B can be divided into the following two cases:
- The case where A = B. In such cases, all possible integer value of K is valid answer. Hence, the value of the required count is infinite.
- The case where A > B. In such cases, it can be observed that a value of K is valid if K divides (A – B). For cases with B > A, simply swap the values of A and B.
Therefore, calculate all the possible values of K such that it divides (A – B) completely which is the required value.
Below is the implementation of the above approach:
C++14
// C++ Program of the above approach#include <bits/stdc++.h>using namespace std;// Function to find the count of the// values of K such that A%K = B%Kint countInt(int A, int B){ // If the count is Infinite if (A == B) return -1; int diff = abs(A - B); // Stores the required count int count = 0; // Loop to calculate all the // divisors of diff for (int i = 1; i * i <= diff; i++) { if (diff % i == 0) { // Increment count for i if (diff == i * i) count++; // Increment count for i // and diff / i both else count += 2; } } // Return Answer return count;}// Driver codeint main(){ int A = 2, B = 4; cout << countInt(A, B); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Function to find the count of the // values of K such that A%K = B%K static int countInt(int A, int B) { // If the count is Infinite if (A == B) return -1; int diff = Math.abs(A - B); // Stores the required count int count = 0; // Loop to calculate all the // divisors of diff for (int i = 1; i * i <= diff; i++) { if (diff % i == 0) { // Increment count for i if (diff == i * i) count++; // Increment count for i // and diff / i both else count += 2; } } // Return Answer return count; } // Driver code public static void main (String[] args) { int A = 2, B = 4; System.out.print(countInt(A, B)); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python code for the above approach # Function to find the count of the# values of K such that A%K = B%Kdef countInt(A, B): # If the count is Infinite if (A == B): return -1; diff = abs(A - B); # Stores the required count count = 0; # Loop to calculate all the # divisors of diff i = 1; while((i * i) <= diff): if (diff % i == 0): # Increment count for i if (diff == i * i): count += 1 # Increment count for i # and diff / i both else: count += 2; i += 1 # Return Answer return count;# Driver codeA = 2B = 4print(countInt(A, B));# This code is contributed by Saurabh Jaiswal |
C#
// C# Program of the above approachusing System;class GFG { // Function to find the count of the // values of K such that A%K = B%K static int countInt(int A, int B) { // If the count is Infinite if (A == B) return -1; int diff = Math.Abs(A - B); // Stores the required count int count = 0; // Loop to calculate all the // divisors of diff for (int i = 1; i * i <= diff; i++) { if (diff % i == 0) { // Increment count for i if (diff == i * i) count++; // Increment count for i // and diff / i both else count += 2; } } // Return Answer return count; } // Driver code public static int Main() { int A = 2, B = 4; Console.Write(countInt(A, B)); return 0; }}// This code is contributed by Taranpreet |
Javascript
<script> // JavaScript code for the above approach // Function to find the count of the // values of K such that A%K = B%K function countInt(A, B) { // If the count is Infinite if (A == B) return -1; let diff = Math.abs(A - B); // Stores the required count let count = 0; // Loop to calculate all the // divisors of diff for (let i = 1; i * i <= diff; i++) { if (diff % i == 0) { // Increment count for i if (diff == i * i) count++; // Increment count for i // and diff / i both else count += 2; } } // Return Answer return count; } // Driver code let A = 2, B = 4; document.write(countInt(A, B)); // This code is contributed by Potta Lokesh </script> |
Output
2
Time Complexity: O(√(A – B))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
