KnowledgeHub
Questions
Tags
Users
Search
Alex Rivera
|
Logout
Edit Question
Title
Body
This is a interview Question. "Given a sorted array. Find the number of couples with the same difference." for example: if array is {1, 2, 3, 5, 7, 7 , 8, 9}; then we have 5 pairs with difference of 1 6 pairs with difference of 2 4 pairs with difference of 4 2 pairs with difference of 3 4 pairs with difference of 6 3 pairs with difference of 5 2 pairs with difference of 7 1 pair with difference of 8 1 pair with difference of 0 I tried the following: maxdiff=arr[n-1]-arr[0]; //calculating the maximum difference int b[maxdiff]; for(i=0;i<maxdiff;i++) { for(j=0;j<n;j++) { p=arr[j]+i; x=binarysearch(p,arr); //search p in array,where x return 0/1 if(x==1) b[i]++; } } this is O(k*n*logn) solution where k is the maximum difference between the first and last element of a sorted array,n is the array size. Does anyone have any better idea than this?
Tags (comma-separated)
Save Edits
Cancel