Open
+ 1

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

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.

21st May 2020, 6:37 AM
Akash Singhania
+ 2
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).
22nd May 2020, 10:45 AM
Schindlabua
+ 3
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/
22nd May 2020, 10:50 AM
ChaoticDawg
+ 3
If you use Arrays.sort() it has a time complexity of O(n log n). You want stay away from O(nÂ²).
22nd May 2020, 2:46 PM
ChaoticDawg
+ 2
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?
21st May 2020, 10:29 AM
ChaoticDawg
+ 2
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)
21st May 2020, 11:03 PM
ChaoticDawg
+ 2
Can you post the explanation and constraints of the challenge? Unfortunately the info posted is too vague.
22nd May 2020, 9:45 AM
ChaoticDawg
+ 1
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.
21st May 2020, 7:13 AM
Schindlabua
+ 1
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.
21st May 2020, 6:35 PM
ChaoticDawg
+ 1
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.
21st May 2020, 7:21 PM
Schindlabua
+ 1
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.
21st May 2020, 10:30 PM
ChaoticDawg
+ 1
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
21st May 2020, 11:07 PM
Schindlabua
+ 1
Thank you guys!
22nd May 2020, 11:06 AM
Akash Singhania
0
ChaoticDawg The array [9,2] can form NÂ² pairs, with N=2: (9,9), (9,2), (2,9), (2,2)
21st May 2020, 2:10 PM
Schindlabua
0
Wait what, why are we removing duplicates all of a sudden :D Is this some challenge question or what?
21st May 2020, 10:51 PM
Schindlabua
0
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.
22nd May 2020, 9:34 AM
Akash Singhania
0
Please check the code below. It has the question as well as my code. https://code.sololearn.com/cORI36ldj4ER/?ref=app
22nd May 2020, 9:56 AM
Akash Singhania
0
Just to be clear, the code gives all correct outputs, it just falls short on the execution time aspect.
22nd May 2020, 9:57 AM
Akash Singhania
0
hola
22nd May 2020, 3:13 PM
bbgEver Pico