Pair of Roses Wrong Answer

#1

Wrong Answer.

#2

hi @Kinjal print values in ascending order

#3

I did that by comparing val1 & val2, right! Is that what you mean?

#4

I have one doubt like if difference of pair of prices are same, is that mean, in output can have more than one solution for a particular case?

#5

@Kinjal print 4 first and then 6, in your output 6 is before 4.

i am not sure what to do in that case as nothing has been specified, so most probably such a case will not be there. Although CB does not have the feature to allow multiple correct answers yet.

#6

yeah, I made an silly mistake. You’re right as always. It worked.

#7

How would you approach this problem if I ask?

#8

good job :slight_smile: :+1:
I sorted the array and , iterarated over the whole array and used binary search to find target-a[i] in the range [i+1, n) o(nlogn) complexity. you can use a hashmap to reduce the searching complexity, although i am not sure how to specify the “range” thing in that

#9

@Kinjal you could use a multimap i guess to overcome that, that would also work.

#10

I think, mine one will take O(n^2) time.
I would like to implement your approach because it’s O(nlogn).

#11

hi @Kinjal you can use some other data structure to reduce the complexity further so that you can perform search in O(1), then the total complexity can be reduced to O(n)

#12

Let me implement your approach first.

1 Like
#13

Can you check it out please? I don’t know what’s wrong with this code.

#14

It worked by your approach. Can you see this code please!
I think, this code will take O(nlogn) time, right!

#15

@Kinjal yes it’s correct!
One thing I’d like to mention is that you can make a vector of size n like this
vector<int> v(n, 0); the second argument is optional, it will initialise the whole array with that value.
then you can directly input the values of vector like an array
cin >> v[i]

1 Like
#16

okay. I will remember your words. Now, I’m trying to optimized the code like you have said before.

#17

If I will use multimap like you’ve said before, still it will take O(nlogn) time. Because multimap operations are O(logn) time.

#18

And, I can’t use hashmap because it will allow only unique key. That’s what I’m thinking.

#19

@Kinjal what about unordered_multiset? you will have to use a pair<value, index> tho to ensure that it doesn’t end up searching its own value (like if array is 10 40 70 and target is 80, so you have to make sure that 40 cannot make a pair with 40)
There is the option of unordered_multimap as well.

#20

@Kinjal unordered data structures are implemented using hashing, so they will take only O(1) time for searching