How to pick all pairs of 2 nos. out of an array of N integers input by user without nesting of loops .??

Question

I am presently using nested for loop to pick all possible pairs of 2, and then i further manipulate it, as required in the question. But the use of nested loop makes my answer only logically correct as the time barrier is crossed, hence tagging my answer as partially correct. Please drop your suggestions.

Answer 1

One thing I'm thinking about is sorting the array first. If you're checking the array [1,2,3,4,5,6,7,8,9,10] for k≥3 and you are currently comparing the pair (4,7) then you get everything to the right ((4,8), (4,9), (4,10)) and to the left ((3,7), (2,7), (1,7)) and every combination like (2,9) for free without calculating anything. Should be an easy formula to figure out how many pairs they are but that's for you to figure out :P

That should give you a pretty efficient O(n²) algorithm or even bring it down O(n log n).

Answer 2

That's pretty much where I was going too. Here is an example with distinct pairs, but may be modified.
https://www.google.com/amp/s/www.geeksforgeeks.org/count-pairs-difference-equal-k/amp/

Answer 3

If you use Arrays.sort() it has a time complexity of O(n log n). You want stay away from O(n²).

Answer 4

Well really there would only be N/2 possible pairs (there is only 1 array of length N, you can't possibly get N²), but that isn't really relevant to answering the challenge. Also, it seems that they're looking for an answer that will result in a time complexity of O(n) not O(n²) which is what you would have with a nested loop.
My question for you The Outrageous Indian is what are the constraints? Sometimes, there is a bit of a hint there.
My guess is that they are;
1 <= A[i] <= N
Where A is the array and N is the length of the array. Is this correct, or are we dealing with something else?

Answer 5

That was my understanding from reading the OP, but honestly now I'm questioning everything. Lol
I read as if it was a challenge question from a site such as hackerrank.com or leetcode or some similar site, but not sure. I thought this because it is stated that "the time barrier is crossed" and their answer was "partially correct". IE. a TLE (time limit exceeded) error
Which if it is the question I'm thinking of, which is asked on multiple sites, they are looking for an answer that is linear and has a time complexity of O(n)

Answer 6

Can you post the explanation and constraints of the challenge? Unfortunately the info posted is too vague.

Answer 7

What you are doing is correct. There are N*N possible pairs, so two nested for loops running from 0 to N do exactly the amount of work needed with no time wasted.

Maybe your problem comes from the "then I further manipulate it" part. You could share the code in the code playground and we can have a look.

Answer 8

Schindlabua those pairs are all imaginary. That's not how this works. You only have a pair if they match. And you'd never attempt to match or make a pair with an element from the same index. IE you can't match an element against itself. It would be completely illogical to code a check to see if A[i] == A[i] in any program, because of course it does. This would be a waist of time completely, even of it is O(1). The only comparison check you'd make in this case would be A[0] == A[1] and then all checks for that array are done as the only other check would be A[1] == A[0] which is redundant and another waist of time complexity, again even if it is O(1), and therefore the total possible pairs is in fact N/2.

Answer 9

ChaoticDawg uhm. How what works.

He says he's picking all possible pairs. There's N² of them. It's the cartesian product, happens all the time.

Answer 10

Cartesian product is the product of 2 sets. There is only 1 linear array in the question. What I'm saying is that it doesn't apply. As we only have X of N length there is no Y (or rather Y is a constant 0 if you prefer) in the example. It's not a multi dimensional array. We aren't looking for the product either. Just looking for a duplicate of any given int in the linear array.
[2, 4, 1, 6, 7, 4, 2, 8, 7]
Were the output would be
[4, 2, 7]
(At least this is what I'm assuming would be the desired output without knowing what the entire explanation and constraints of the given challenge are).
Really the question is a bit vague and ambiguous and further details are needed to come to a proper conclusion.

https://mathinsight.org/definition/cartesian_product

Yes, I understand that you're using X as Y also. I just still don't think that is what we are after. Maybe I'm wrong, but without further input from the OP IDK.

Answer 11

Oh yeah you're already 200IQ ahead of me then. I'm just saying if you enumerate all possible pairs in a size N array that'll always involve an O(N²) algo because there are N² possible pairs.

But let's wait for the OP to tell us what he's actually doing. :D

Answer 12

Thank you guys!

Answer 13

ChaoticDawg The array [9,2] can form N² pairs, with N=2: (9,9), (9,2), (2,9), (2,2)

Answer 14

Wait what, why are we removing duplicates all of a sudden :D Is this some challenge question or what?

Answer 15

Well, my issue was all about the time complexity of the program. My program shows TLE error on execution hence tagging the code as partially correct. To be precise, the execution time of the program is close to 2 secs while the time limit is 1 sec. Therefore I just wished to know if there was a way to do the task I mentioned above within the given time frame.

Answer 16

Please check the code below. It has the question as well as my code.

https://code.sololearn.com/cORI36ldj4ER/?ref=app

Answer 17

Just to be clear, the code gives all correct outputs, it just falls short on the execution time aspect.

Answer 18

hola