You are not logged in. Please login at www.codechef.com to post your questions!

×

QUALPREL : Not understanding the reason for TLE,.

Why am I getting TLE when complexity is still O(nlogn) as mentioned in Editorial Solution and I used binary search in increasingly sorted array which is O(logn) instead of traversing elements in O(n)

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    int tests;
    cin >> tests;
    while(tests--){
        int n, k;
        cin >> n >> k;
        int arr[n];
        for(int i=0; i<n; i++){
            cin >> arr[i];
        }
        sort(arr, arr+n);
        int x = arr[n-(k-1)-1];
        int low = 0, high = n-1, mid = (low+high)/2;
        while(low<=mid){
            if(arr[mid]<x)
                low = mid+1;
            else
                high = mid-1;
            mid = (low+high)/2;
        }
            cout << n-(high+1) << '\n';
    }
    return 0;
}

asked 27 Nov '18, 00:02

kishansairam9's gravatar image

2★kishansairam9
1
accept rate: 0%

converted to question 27 Nov '18, 00:05


Try out the test case

1
6 6
1 2 3 3 3 4

In this test case your code will stuck in infinite loop because here according to your code
x will be 1
low will be 0 and high will be 5 and mid will be 2 in first pass
So arr [2] will be 3 which is greater than x so high becomes 1 and mid becomes 0
Now arr [0] will be 1 which is not less than x so high becomes -1 and mid becomes 0 here again arr [0] is not less than x so high becomes -1 and mmid becomes 0 and this will run forever like this and you won't get your answer that's why it's giving TLE

link

answered 27 Nov '18, 11:18

admin5's gravatar image

5★admin5
2269
accept rate: 18%

edited 27 Nov '18, 11:22

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,688
×801
×721
×102
×29

question asked: 27 Nov '18, 00:02

question was seen: 94 times

last updated: 27 Nov '18, 11:22