Target sum of a array

#1

code–https://ide.codingblocks.com/s/38276
ques–https://hack.codingblocks.com/app/contests/1975/195/problem

#2

Hey @aaliyah_beg
The link u shared for code is empty :slight_smile:
please share it again

#3
#4

Hey @aaliyah_beg
You only have to print unique triplets ,for that u have to delete duplicate nos in array.
Also to get the desired results as that of question u also have to sort the array first.
So sort the array and delete duplicates and then apply ur algo.

#5

code–https://ide.codingblocks.com/s/382800 this is working but in test case 0 tle is coming

#6

Yes because ur approach is O(n^3)
Since the array is sorted now
u can do it in O(n^2) using 2 pointer approach
If u dont know what its then let me know :slight_smile:

#7

sir please elaborate. I dont know what that method is.

#8

Approach : The two pointer technique can be brought into action using the sorting technique. In two pointer technique one can search for the pair having a target sum in linear time. The idea here is to fix one pointer (say a) and and use the remaining pointers to find the pair having required sum Target-value at(a) efficiently.
Now let’s discuss how we can find the required pair effectively using two pointer technique. The pointers used for two pointer technique are say (l and r).

So if the sum = value(a) + value(l) + value( r) exceeds the required sum, for same (a, l) the required value® should be less than the previous. Thus, decrementing the r pointer.
If the sum = value(a) + value(l) + value® is less than the required sum, for same (a, r) the required value(l) should be greater than the previous. Thus, incrementing the l pointer.

Algorithm:

  • Sort the array and for every element arr[i] search for the other two elements arr[l], arr[r] such that arr[i]+arr[l]+arr[r]=Target sum.
  • Searching for the other two elements can be done efficiently using Two-pointer technique as the array is sorted.
  • Run an outer loop taking contol variable as i and for every iteration initialize a value l which is the first pointer with i+1 and r with last index.
  • Now enter into a while loop which will run till the value of l<r.
  • If arr[i]+arr[l]+arr[r]>Target sum then decrement r by 1 as the required sum is less than the current sum and decreasing the value of will do the needful.
  • If arr[i]+arr[l]+arr[r]<Target sum then increment l by 1 as the required sum is less than the current sum and increasing the value of will do the needful.
  • If arr[i]+arr[l]+arr[r]==Target sum print the values.
  • Increment i Goto Step 3.