Given an array arr[] and three integers D, A and B. You start with the number D and at any time you can add or subtract either A or B to the current number. That means you can do the following four operations any number of times:
- Add A to the current number.
- Subtract A from the current number.
- Add B to the current number.
- Subtract B from the current number.
The task is to find the count of integers from the given array which can be reached after performing the above operations.
Examples:
Input: arr[] = {4, 5, 6, 7, 8, 9}, D = 4, A = 4, B = 6
Output: 3
The reachable numbers are:
4 = 4
6 = 4 + 6 – 4
8 = 4 + 4
Input: arr[] = {24, 53, 126, 547, 48, 97}, D = 2, A = 5, B = 8
Output: 6
Approach: This problem can be solved using a property of diophantine equations
Let the integer we want to reach from the array be x. If we start with D and we can add/subtract A or B to it any number of times, that means we need to find if the following equation has integer solution or not.
D + p * A + q * B = x
If it has integer solutions in p and q then it means we can reach the integer x from D otherwise not.
Rearrange this equation to
p * A + q * B = x – D
This equation has an integer solution if and only if (x – D) % GCD(A, B) = 0.
Now iterate over the integers in the array and check if this equation has a solution or not for the current x.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the GCD// of a and bint GCD(int a, int b){ if (b == 0) return a; return GCD(b, a % b);}// Function to return the count of reachable// integers from the given arrayint findReachable(int arr[], int D, int A, int B, int n){ // GCD of A and B int gcd_AB = GCD(A, B); // To store the count of reachable integers int count = 0; for (int i = 0; i < n; i++) { // If current element can be reached if ((arr[i] - D) % gcd_AB == 0) count++; } // Return the count return count;}// Driver codeint main(){ int arr[] = { 4, 5, 6, 7, 8, 9 }; int n = sizeof(arr) / sizeof(int); int D = 4, A = 4, B = 6; cout << findReachable(arr, D, A, B, n); return 0;} |
Java
// Java implementation of the approachclass GFG{ // Function to return the GCD // of a and b static int GCD(int a, int b) { if (b == 0) return a; return GCD(b, a % b); } // Function to return the count of reachable // integers from the given array static int findReachable(int[] arr, int D, int A, int B, int n) { // GCD of A and B int gcd_AB = GCD(A, B); // To store the count of reachable integers int count = 0; for (int i = 0; i < n; i++) { // If current element can be reached if ((arr[i] - D) % gcd_AB == 0) count++; } // Return the count return count; } // Driver code public static void main(String[] args) { int arr[] = { 4, 5, 6, 7, 8, 9 }; int n = arr.length; int D = 4, A = 4, B = 6; System.out.println(findReachable(arr, D, A, B, n)); }}// This code is contributed by Rajput-Ji |
Python3
# Python implementation of the approach# Function to return the GCD# of a and bdef GCD(a, b): if (b == 0): return a; return GCD(b, a % b);# Function to return the count of reachable# integers from the given arraydef findReachable(arr, D, A, B, n): # GCD of A and B gcd_AB = GCD(A, B); # To store the count of reachable integers count = 0; for i in range(n): # If current element can be reached if ((arr[i] - D) % gcd_AB == 0): count+=1; # Return the count return count;# Driver codearr = [ 4, 5, 6, 7, 8, 9 ];n = len(arr);D = 4; A = 4; B = 6;print(findReachable(arr, D, A, B, n));# This code is contributed by 29AjayKumar |
C#
// C# implementation of the approach using System;class GFG { // Function to return the GCD // of a and b static int GCD(int a, int b) { if (b == 0) return a; return GCD(b, a % b); } // Function to return the count of reachable // integers from the given array static int findReachable(int[] arr, int D, int A, int B, int n) { // GCD of A and B int gcd_AB = GCD(A, B); // To store the count of reachable integers int count = 0; for (int i = 0; i < n; i++) { // If current element can be reached if ((arr[i] - D) % gcd_AB == 0) count++; } // Return the count return count; } // Driver code public static void Main() { int []arr = { 4, 5, 6, 7, 8, 9 }; int n = arr.Length; int D = 4, A = 4, B = 6; Console.WriteLine(findReachable(arr, D, A, B, n)); } } // This code is contributed by AnkitRai01 |
Javascript
<script>// javascript implementation of the approach // Function to return the GCD // of a and b function GCD(a , b) { if (b == 0) return a; return GCD(b, a % b); } // Function to return the count of reachable // integers from the given array function findReachable(arr, D, A, B, n) { // GCD of A and B var gcd_AB = GCD(A, B); // To store the count of reachable integers var count = 0; for (i = 0; i < n; i++) { // If current element can be reached if ((arr[i] - D) % gcd_AB == 0) count++; } // Return the count return count; } // Driver code var arr = [ 4, 5, 6, 7, 8, 9 ]; var n = arr.length; var D = 4, A = 4, B = 6; document.write(findReachable(arr, D, A, B, n));// This code is contributed by aashish1995</script> |
3
Time Complexity: O(n * log(min(a, b))), where a and b are two parameters for GCD.
Auxiliary Space: O(log(min(a, b)))
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
