Wrong Answer. Please check code

#1

#include<bits/stdc++.h>

using namespace std;

int main() {

int n,target; cin>>n;
int a[n];
for(int i=0;i<n;i++) 
cin>>a[i];
cin>>target;
map<int, int> m;

for(int i=0;i<n;i++) {	
	
	int rem = target - a[i] ;
	if(m.find(rem) != m.end()) {
		int count=m[rem];
		for(int j=0;j<count;j++) {
			cout<<rem<<" and "<<a[i]<<"\n";
		}
	}
	m[a[i]++];
}

return 0;

}

this is my code. i am getting wrong answer. what’s the mistake?

#2

hello @priyamthakuria27

here it should be m[a[i]]++;
rest everthing is correct.

also even after doing this change it will not pass all test case because of thr ordering issue.
to get ac please follow this algorithm->
image

#3

but this is of O(nlogn) complexity.
isn’t there a solution of O(n) complexity?

#4

see the algorithm( i mentioned above) works in O(n) (assuming given array is already sorted) .

there is hashing algorithm that works in O(n) but i wont print output in required order.

apart from these two i dont think there exist any other O(n) solution .

#5

the sorting itself is of O(nlogn) right?

#6

yeah…

I am saying if given array is sorted then O(n) otherwise i we need to sort it explicitly then O(n+ nlog(n) ) -> which is O(nlog(n)).

#7

also, why doesn’t my solution pass all the cases? what’s the error?

#8

ordering
test case contain output in sorted formats but ur will print in any order because array is not sorted.

#9

Ok. Understood.
Thank you.