Learn-dsa..in 30 days!



























CC-17 : Find pairs with particular difference.

Description:

Given an input array, and an integer difference diff, find all pairs within input array that have a difference (subtraction result) of diff.

Test cases and expected outputs:

Input Parameters Expected outputs
Array:
37, 3, 4, 97, 		Pair with diff: 33 are 4 , 37

Pseudocode:

findPairsWithDifference(nums[], diff):

Set nums=quicksort(nums).
Initialize integer array variable named numsLesser and sets its length to nums.length.
Iterate through nums using for loop with idx as iteration variable and values of idx ranging from 0 to nums.length-1:
Initialize and int array names pairWithReqDiff of length 2.
Initialize int variable complement to nums[idx]+diff. Now, if we can find complement in the nums array, we will be able to find a pair of numbers with difference diff.
Find the index of complement in nums and set it in variable complementIdx.
If complementIdx != -1 then:
Set pairWithReqDiff[0]=nums[idx].
Set pairWithReqDiff[1]=nums[complementIdx].
Return null.

QuickSort(nums[], startIdx, endIdx):

Integer array named nums, start index startIdx and end index endIdx of nums are received as input parameters.
If (startIdx < endIdx) then execute following steps:
Initialize and integer variable pivot with value nums[endIdx]. We will use this variable to partition the elements into two partitions.
Initialize and integer variable iidx with value startIdx-1. We will use this variable to track and swap elements less than pivot to partition containing elemnts lesser than the pivot.
Iterate through using for loop with jidx as iteration variable and values of iidx ranging from startIdx to endIdx-1:
If nums[jidx]<=pivot then:
Increment iidx by 1.
Swap elements at position iidx and jidx.
Swap elements at index iidx+1 and endIdx.
Set integer variable partitionIdx to iidx+1.
Call method quicksort(nums, startIdx, partitionIdx-1) to sort the partition with lesser elements than pivot element.
Call method quicksort(nums, partitionIdx+1, endIdx,) to sort the partition with greater elements than pivot element.
The element of nums array have been sorted now using Quick Sort, so return nums array from the method.

binarySearch(nums[], toSearch):

Integer array named nums and integer named toSearch to be searched are received as input parameters.
Set integer variable firstIdx to zero, we will use this variable to check the first index of partition in which are searching for required integer.
Set integer variable lastIdx to nums.length-1, we will use this variable to check the last index of partition in which are searching for required integer.
While (firstIdx <= lastIdx) do the following steps:
Set integer variable midCount to (lastIdx-firstIdx)/2.
Set integer variable midIdx to (firstIdx+midCount)to get mid index of current partition. We will use midIdx to partition the array into 2 parts.
If (nums[midIdx]==toSearch) return midIdx; this means have found the required element.
Else if nums[midIdx > toSearch then:
Set lastIdx=(midIdx-1) as we need to search in lower partition now.
Else:
Set firstIdx=midIdx+1, as we need to search in the higher partition now.
If toSearch is not found in code above return -1, as the required element does not exist within the input array.

Code:

public int[] findPairWithDifference(int[] nums, int diff) {
	nums=quickSort(nums, 0, nums.length-1);
	for (int idx=0;idx<nums.length; idx++) {
		int[] pairWithReqDiff=new int[2];
		int complement=nums[idx]+diff;
		int complementIdx=binarySearch(nums,complement);
		if (complementIdx !=-1) {
			pairWithReqDiff[0]=nums[idx];
			pairWithReqDiff[1]=nums[complementIdx];
			return pairWithReqDiff;
		}		
	}
	return null;
}

public int[] quickSort(int[] nums,int startIdx, int endIdx) {
	if(startIdx < endIdx) {
		int pivot=nums[endIdx];
		int iidx=startIdx-1;
		for (int jidx=startIdx; jidx < endIdx;jidx++) {
			if (nums[jidx] <= pivot) {
				iidx++;		
				int swap=nums[iidx];
				nums[iidx]=nums[jidx];
				nums[jidx]=swap;
			}
		}
		int swap=nums[iidx+1];
		nums[iidx+1]=nums[endIdx];
		nums[endIdx]=swap;
			
		int partitionIdx=iidx+1;
		quickSort(nums, startIdx, partitionIdx-1);
		quickSort(nums, partitionIdx+1,endIdx);
		}
	return nums;
}

public int binarySearch(int[] nums, int toSearch){
	int firstIdx=0;
	int lastIdx=nums.length-1;
	while (firstIdx <= lastIdx) {
		int midCount=(lastIdx-firstIdx)/2;
		int midIdx=firstIdx+midCount;
		if (nums[midIdx]==toSearch) {
			return midIdx;
		} else { if (nums[midIdx]> toSearch) {
			lastIdx=midIdx-1;
		}else {
			firstIdx=midIdx+1;
		}
		}		
	}	
	return -1;
}

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us