Number of array elements derivable from D after performing certain operations

Given an array of N integers and 3 integers D, A and B. The task is to find the number of array elements that we can convert D into by performing the following operations on D: 

• Add A (+A)
• Subtract A (-A)
• Add B (+B)
• Subtract B (-B)

Note: It is allowed to perform any number of operations of any type.

Examples: 

Input :  arr = {1, 2, 3}, D = 6, A = 3, B = 2 
Output :  3
Explanation: 
We can derive 1 from D by performing (6 - 3(A) - 2(B))
We can derive 2 from D by performing (6 - 2(A) - 2(A))
We can derive 3 from D by performing (6 - 3(A))
Thus, All array elements can be derived from D.
 
Input :  arr = {1, 2, 3}, D = 7, A = 4, B = 2 
Output :  2
Explanation: 
We can derive 1 from D by performing (7 - 4(A) - 2(B))
We can derive 3 from D by performing (7 - 4(A))
Thus, we can derive {1, 3}

Lets say the we want to check if the element a_i can be derived from D:

Suppose we perform: 

• The operation of type1(i.e Add A) P times.
• The operation of type 2(i.e Subtract A) Q times.
• The operation of type 3(i.e Add B) R times.
• The operation of type 4(i.e Subtract B) S times.

Let the value we get after performing these operations be X, then, 
-> X = P*A – Q*A + R*B – S*B 
-> X = (P – Q) * A + (R – S) * B
Suppose we successfully derive A_i from D, i.e X = |A_i – D|, 
-> |A_i – D| = (P – Q) * A + (R – S) * B
Let (P – Q) = some constant say, U 
and similarly let (R – S) be a constant, V
-> |A_i – D| = U * A + V * B
This is in the form of the Linear Diophantine Equation and the solution exists only when |A_i – D| is divisible by gcd(A, B). 

Thus now we can simply iterate over the array and count all such A_i for which |A_i – D| is divisible by gcd(a, b).

Below is the implementation of the above approach: 

4
3

Complexity Analysis:

• Time Complexity: O(log(max(A, B) + N), where N is the number of array elements and A & B represents the value of given integers.
• Auxiliary Space: O(log(max(A, B)) due to recursive stack space .