Find pairs with given sum in a sorted array.
Given an array A of size N. Write a code to find all pairs in the array that sum to a number equal to K. If no such pair exists then output will be –1.
NOTE – The array elements are distinct and in a sorted order.
For example –
Input :
arr[] = {1, 2, 3, 4, 5, 6, 7};
sum = 9
Output:
Pairs with given sum 9 is
Pair (2 , 7 )
Pair (3 , 6 )
Pair (4 , 5 )
Find first and last position of element in sorted array.
Given a sorted array which contains duplicate elements. Write a code to find first and last position of a number in a sorted array.
OR
Find first and last occurrences of x in sorted array where x is a target value.
If a number is not found return -1.
For example –
Example 1 –
Input : {1, 4, 7, 8, 8, 11, 11, 11, 11, 12, 13, 13} , target = 11
Output: {5, 8}
The first index of 11 is 5 and last index is 8.
Example 2 –
Input: {1, 6, 7, 7, 8, 8, 9, 9}, target = 5
Output: {-1, -1}
The target value is not found.
NOTE – We have to solve this problem in O(logn) time complexity.
Given two sorted arrays, Write a java code to find intersection of two arrays.
For example, if the input arrays are:
arr1[] = {2, 3, 6, 7, 9, 11}
arr2[] = {4, 6, 8, 9, 12}
The common elements between these two arrays are {6, 9}.