Now suppose our goal is to instead find whether there is a sub-array A[l, r] such that
![(b) Now suppose our goal is to instead find whether there is a sub-array A[l, r] such that
Ali] = n².
i=l
Design a randomized algorithm for this case with worst-case expected runtime of O(n).](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F5ff83b3f-35bb-4190-932b-2e5a6e904b7a%2F62081231-d2b4-4ecb-bb4e-8183578ed202%2Fstrib2_processed.png&w=3840&q=75)
To find a sub-array where one array is the square of the other array, we need a minimum of O(N) space complexity.
Why? Because we need to find to the square root of the first array and store it in another array. In teh worst case we need to traverse the whole array (arr1) and match it with every position of arr2 till (i=0 to i<= length(arr2)). Here in this algorithm, I have taken arr1 as the main array, arr2 as sub-array and arr3 = [] as an empty array. There would be 2 conditions as mentioned below.
This is not a code. This is just an algorithm.
---------------------------------------------------- Algorithm------------------------------------------------------------
Case1: arr1 size is greater than arr2
For i=0 to length(arr1)-length(arr2)
arr3 = Math.sqrt(arr1)
If equal(arr2.begin(),arr2.end(), arr3.begin()+i) is true
Then return true since we found a range
starting from arr3[i] which is equal to arr2
Return false if no such range is found.
Case 2: arr1 size is greater than arr2
For i=0 to length(arr2)-length(arr1)
arr3 = Math.sqrt(arr1)
If equal(arr3.begin(),arr3.end(), arr2.begin()+i) is true
Then return true since we found a range
starting from arr2[i] which is equal to arr3
Return false if no such range is found.
----------------------------------------------------------------------------------------------------------------------------
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
