Количество элементов в массиве, которые достижимы после выполнения заданных операций над D
Дан массив arr [] и три целых числа D , A и B. Вы начинаете с числа D и в любой момент можете прибавить или вычесть A или B к текущему числу. Это означает, что вы можете выполнять следующие четыре операции любое количество раз:
- Добавьте A к текущему числу.
- Вычтите A из текущего числа.
- Добавьте B к текущему числу.
- Вычтите B из текущего числа.
Задача состоит в том, чтобы найти количество целых чисел из заданного массива, которое может быть достигнуто после выполнения вышеуказанных операций.
Примеры:
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
Подход: эту проблему можно решить, используя свойство диофантовых уравнений.
Пусть целое число, которое мы хотим получить из массива, будет x . Если мы начнем с D и можем добавлять / вычитать A или B любое количество раз, это означает, что нам нужно найти, имеет ли следующее уравнение целочисленное решение или нет.
D + p * A + q * B = x
Если у него есть целочисленные решения в p и q, это означает, что мы можем достичь целого числа x из D, иначе нет.
Измените это уравнение на
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 approachusing 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
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.