How to approaches this problems?

#1

how to appraoch this problem…

#2

Hey @Vikaspal

This Question is similar to the Array - Target Sum pair. The only difference is to capture that prices of roses which have a minimum difference between them.

Note :- As in this Logic we are traversing our left from 0th to lastIndex and the right from lastIndex to 0 so each time we got pair we will upadate the final ans variables so that each time the difference between them decreases.

1.First sort the given array.
2.Now take two variables one as left and other as right starting from 0th and end index of the sorted array respectively.
3.Now iterate till left<right.
3.1 Calculate the sum of the elements at left and right position
3.1.1 If the sum is equal to the target then print both the elements. //printing target sum pairs
3.1.2 If the sum is less than the target then increase the left by 1
3.1.3 Else decrease the right by 1
4.End loop.Thus, all the pairs has been printed .

#3

@Kartikkhariwal1 i got the two pointer approaches hence sorting will takes nlogn + we are traverse the arrays in O(N) time so run time is nlogn only right… but my question is if we do it in the brute force ways like we have sort the arrays .
for (int i = 0; i < n; i++ ) {
for(int j = i + 1; j < n; j++) {
if (arr[i] + arr[k] == targetSum) {
int rose1 = arr[i];
int rose = arr[k];
}
}
}
Does this will gives us the optimal minimum answer because we are going to include only the sum elments which leads to target sum
like if target sum = 10 , 2, 4, 6 , 8, 10 so here we get the 2 and 8 but here which approches fails ans is 4 6 right ?? and brute force according to u

#4

Hey @Vikaspal

Yes correct

It can give optimal minima u just have to change it a lil bit

long long curDif=INT_MAX;
    long long p1,p2;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if( (ar[i]+ar[j]) == tar and abs(ar[j]-ar[i])<curDif ){
				p1=ar[i];
				p2=ar[j];
				curDif=ar[j]-ar[i];
			}
		}
	}

If this resolves your query then please mark it as resolved :slight_smile:

#5

@Kartikkhariwal1 can u checkout this two pointer approaches it leads to TLE

#6

Hey @Vikaspal

if (arr[left] + arr[right] == target) {

               

               int cur_diff = arr[left] < arr[right] ? arr[right] - arr[left] : arr[left] - arr[right]; 

               if (cur_diff < diff) {

                   diff = cur_diff; 

                   rose1 = arr[left]; 

                   rose2 = arr[right];

                   // right--; movcve them out of condition

                   // left++;

               }

                   right--; 

                   left++;

           }

If this resolves your query then please mark it as resolved :slight_smile: