Implement a function to find element at any rank.

[Shubhayu-Das]

Do the checklist before filing the issue:

• [x] Do you have Node.js and all the relevant dev-dependencies installed?
• [ ] Is this a bug fix?
• [x] Is this an enhancement?
• [x] Is this a feature request?

NOTE: Provide a clear and concise description of the feature that needs to be added! Or if its a bug, then provide the necessary steps to reproduce it along with screenshots.

• Give your answer below:

Write a function to find a element with the given rank. If no such element exists, then return an error. Time complexity must be O(n). rank = 1 +(number of >= elements)

 Example: arr = [1,2,3,4,2,6]
 EleAtRank(2) = 4;
 EleAtRank(5) = 2;
 EleAtRank(4) = //error;

[Shubhayu-Das]

I will work on this if you approve of it.

[fave77]

@sateslayer just to be clear we'd implement it like so:

const EleAtRank = M.rankify([ 1, 2, 3, 4, 2, 6 ]);     /* returns a function */

EleAtRank(1);     /* 6 */
EleAtRank(2);     /* 4 */
EleAtRank(3);     /* 3 */
EleAtRank(4.5);   /* 2 */
EleAtRank(6);     /* 1 */

And your time complexity would be O(n)?

[Shubhayu-Das]

Yes, almost.

 EleAtRank(2) = 5 not 4;

There is an additional space complexity of O(n).

And I guess you meant 4 instead of 4.5 . The code will be using a partitioning scheme similar to Merge Sort.

This is useful for the median() function too.

[fave77]

Why the element at rank 2 is 5, cause 5 isn't present in the array!

[Shubhayu-Das]

Oh my bad, the ranks are all integers. So we round up the fractional ranks. That's how I defined my rank function above.

Alternatively I think we can round down as well, but that may lead to errors, I will have to check that out.

[fave77]

For this array, [1, 5, 3, 8, 1, 3, 3]. Let me know, what's the rank of all the elements!

[Shubhayu-Das]

OK! 8 is at rank 1. 5 at rank 2. 3 at rank 5. 1 at rank 7.

[fave77]

Alright, got it!

[fave77]

So, shall I get 1 at rank 6, or 3 at rank 4 & 3?

[Shubhayu-Das]

Rank 6 will be an invalid input. Because all equal numbers are assigned the same rank due to same priority.

[Shubhayu-Das]

OK! 8 is at rank 1. 5 at rank 2. 3 at rank 5. 1 at rank 7.

Any rank values apart from these will be considered invalid.

[fave77]

Alright! Implement it like this:

const EleAtRank = M.rankify([1, 5, 3, 8, 1, 3, 3]);

EleAtRank(1);   /* 8 */
EleAtRank(2);   /* 5 */
EleAtRank(5);   /* 3 */
EleAtRank(7);   /* 1 */

[Shubhayu-Das]

All right. Thanks!

[Shubhayu-Das]

Wait where is the input for the array? What exactly does rankify do?

Alright! Implement it like this:

const EleAtRank = M.rankify([1, 5, 3, 8, 1, 3, 3]);

EleAtRank(1);   /* 8 */
EleAtRank(2);   /* 5 */
EleAtRank(5);   /* 3 */
EleAtRank(7);   /* 1 */

[Shubhayu-Das]

Hey, @pbiswas101 I don't think I will be able to complete it within the stipulated time. I have too many projects to complete. I am extremely sorry :-/ .

[fave77]

@sateslayer No problem! I can extend the time until 11:59 pm if you want!

[Shubhayu-Das]

Um no use, I was busy till now for some project. I'll see if I can do it now.

[Shubhayu-Das]

I have implemented the code, it's working but with slight variations to the definitions I have described above. However I don't think my code is worth adding to Mathball, because it's unstable. I suggest you close this issue or assign it to someone else.

If I can somehow wrap my C code into JavaScript, then it will work perfectly fine.

Sorry for the trouble caused.

[fave77]

@sateslayer No problem.

[Shubhayu-Das]

Can I implement the normal way to do this? It will be O(n*log n) because it involves sorting. If I can get the O(n) algorithm working some other time, I'll update it(outside of GsSOC issues).

[fave77]

@sateslayer sure! You're assigned

[fave77]

@sateslayer your time's up!

[AishwaryaDASH]

Can i work on this issue?

[fave77]

@AishwaryaDASH can you confirm your gssoc19 slack username?

[AishwaryaDASH]

My username is Aishwarya(P). I joined the Mathball channel just today.

[fave77]

@AishwaryaDASH okay, you're assigned!

[fave77]

@AishwaryaDASH your time's up!

[Shubhayu-Das]

I believe this issue is pretty useless if it can't be implemented with efficient time complexity.