Doubt in my code

#1

Hello, why my program is printing the results more than one time ?

#2

Hey @yashsharma4304 you forgot to sort the array, and I have changed your for statement initialisation part for j variable.
Have look at here

#3

yeah… I forget to initialize j from i and that was my mistake. But the array need not to be sorted for this approach. Thanks for clearing my doubt :slightly_smiling_face:

#4

Now also it is not clearing one of the test case why?

#5

This won’t be solved using for loop @yashsharma4304 or else one of your test case won’t get passed if you still use for loop, try to solve it using while loop . Here is the pseudo code->

 void targetSum(int *arr, int n, int target)
{
    sort(arr, arr + n);
    int left = 0;
    int right = n - 1;
    while (left < right)
    {
        int sum = arr[left] + arr[right];
        if (sum > target)
        {
            right--;
        }
        else if (sum < target)
        {
            left++;
        }
        else
        {
            cout << arr[left] << " and " << arr[right] << endl;
            left++;
            right--;
        }
    }
}
#6

It’s written in that the output should be in a sorted manner, so we have to sort it first and then apply our logic.

#7

if(a[i]>=a[j]){

                cout<<a[j]<<" and "<<a[i]<<endl;

            }

            else{

                cout<<a[i]<<" and "<<a[j]<<endl;

But I have write these conditions for getting the output in the sorted manner.

#8

See, by the logic you are applying. It’s time complexity will be O(n^2) but when we sort it, in worst case the while loop logic will go to O(n^2) and average will be O(nlogn)
Try to dry run using this test case
arr[] = {10, 12, 10, 15, -1, 7, 6, 5, 4, 2, 1, 1, 1},
sum = 11
Output : 9
Try to dry run you will feel yourself that while sorting the array we will be saved doing extra iterations.

1 Like
#9

If you will sort it, then there won’t be a need to check it.

#10

So do they also check the optimization of my code with their test cases. I mean if any of my test case is failing then the time complexity or the space complexity may be one of the reason ?

#11

hey @yashsharma4304 i found that where were you test cases were failing
in input of
5
5 2 3 4 1
6
expected output is:
1 and 5
2 and 4

But your code is giving
1 and 5
2 and 4
3 and 3

So you know that no duplicate number is expected.
So in this case why your code is failing because in output we don’t want any duplicate number
for that i have edited your code here


Try submitting this, as we haven’t sorted in this code

#12

It will show you TLE when your time complexity will be more then the required Time complexity moreover there’s no criteria for space complexity. So you can take as much space you want.

1 Like
#13

yeah now it worked well. :slightly_smiling_face:

#14

I am glad it worked. Good work :smile:

1 Like
#15

:relaxed: :smile: :smile: