prakash951's blog

Hackerrank OA
By prakash951, history, 3 hours ago, In English 
Write a program to find the number of pairs of elements in an array, that satisfy the below condition.

min(∣a−b∣,∣a+b∣)≤min(∣a∣,∣b∣) 
max(∣a−b∣,∣a+b∣)≥max⁡(∣a∣,∣b∣)

min(∣a−b∣,∣a+b∣)≤min(∣a∣,∣b∣)≤max⁡(∣a∣,∣b∣)≤max(∣a−b∣,∣a+b∣)

Example:

[-9, 6, -5, 3]

-9 -5
-9 6
-5 3
-5 6
3 6

constraints:

1<=N<=200000

-1000000000<=a[i]<=1000000000

Solved it with O(NxN)

Required Complexity: O(NlogN)

If anybody has better solution please share.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by prakash951 (previous revision, new revision, compare).

→ Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by prakash951 (previous revision, new revision, compare).

→ Reply
»
86 minutes ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it 
2 * min( |a|, |b| ) >= max( |a|, |b| )

NlogN

//vector v
int ans=0;
   for ( auto &&i : v ) { i = abs(i); }
   sort(v.begin( ), v.end( ));
   for ( int i = 0, j = 1; j < n; ++j ) {
      for ( ; i < j and (2 * v[i] < v[j]); i++ ) {}
      ans += j &mdash; i;
   }
→ Reply