What is the approach to be followed to get 100 points in this question?
I have tried to get that in O(n) but it failed in some of the test cases?
What is the approach to be followed to get 100 points in this question?
I have tried to get that in O(n) but it failed in some of the test cases?
You can use KMP algorithm for pattern searching.
Create two new arrays from the differences of adjacent elements. One for a[] and one for b[]. Now apply KMP search.
I understand the approach. Could you provide the code for better understanding please? Thank you @sayanmedya
Thanks a lot bro
What are you actually doing in this line
if (abs(b[i - j] - a[0]) <= x)
ans++;
The rest is same as KMP and how finding a match with adjacency difference gives the answer?
Remember the pattern we matched against the array b was difference array.
Here i - j is the index where the difference array matches.
Let’s have a look at the sample testcase,
Here, B\_Diff=\{1,1,1,1,1\} and A\_Diff=\{1,1,1\}
Now, A\_Diff matches in 3 different indices, 0,1,2
The above condition checks if that index can be an answer or not by finding a suitable x as specified in the question.
So by this condition index 2 is not a solution even though it matches.
The question talks about adding some number x to the whole array A[]. Now, whatever value we are going to add with the array, the difference will always remain same. So if A[1,...,n]+x=B[i,...,i+n-1] holds, their difference will also be same. Thus matching difference gives us answer.
K i got it
I have seen that you have solved all the problems. Could you please explain solution for the problems
thanks in advance
Problem’s name is good.