Find Watson's integer

Question

Problem Statement:

Watson gives Sherlock an array \$A_1\$, \$A_2\$ ... \$A_N\$. He asks him to find an integer \$M\$ between \$P\$ and \$Q\$ (both inclusive), such that, \$\min \{|A_i-M|, 1 \le i \le N\}\$ is maximised. If there are multiple solutions, print the smallest one.

Input Format:

The first line contains \$N\$. The next line contains space separated N integers, and denote the array \$A\$. The third line contains two space separated integers denoting \$P\$ and \$Q\$.

Constraints:

• \$1 \le N \le 10^2\$
• \$1 \le A_i \le 10^9\$
• \$1 \le P \le Q \le 10^9\$

My code:

#include <bits/stdc++.h>
int main()
{   int size,print,dist=INT_MIN,answer,start,end,diff;
    std::vector <int> arr;
    std::cin>>size;
    for(int i=0;i<size;i++)
    {   int templ
        std::cin>>temp;
        arr.push_back(temp);
    }
    std::sort(arr.begin(),arr.end());
    std::cin>>start>>end;
    for(int i=start;i<=end;i++)
    {   
        dist=INT_MAX;
        for(int j=0;j<size;j++)
        {
            diff=fabs(i-arr[j]);
            if(diff>dist)
                break;
            dist=std::min(dist,diff);

        }
        if(dist>answer)
        {
            answer=dist;
            print=i;
        }
    }
    std::cout<<print;
    return 0;
}

My code is producing the output that I'm expecting, however it is failing with the hackerrank judge telling me that the time limit has been exceeded.

According to me its running time is O(n(p-q)). Then it should clear all the test cases in less than 2s (assuming computer can compute 10^9 problems in a second, I remember reading somewhere that that's how most online judges work). At most my program will work on 10^11 problems (n*p-q= 10^2 *10^11).

Do my timing predictions make sense?

How can I improve my code, particularly the performance so that it is able to pass this judge?

Answer 1

General Advise
Online coding challenges may not be timed as far as how long it takes to write them. Take the time to write better code rather than rushing through it. Don't make assumptions about the size of data or the run time that is allowed, on line research may be incorrect about this, because times won't be posted.

Big O Calculation
Does the Big O Calculation include the call to sort() if not, then that can be part of the timing problem.

Use Functions
The program is too complex and needs to be broken into functions. One function gets the array of numbers of input. Another function should do the calculation. The main() function should just control the program.

Declare Variables as Needed
There is a list of variables at the very beginning, this is more C like than C++. If the program is broken into functions this large list of variables at the top is not needed.

Meaningful Variable Names
The variable size is a good name, although the type might be size_t rather than int. The other variable names might be more meaningful if the were declared where they were needed.

Missing Includes
The code is missing some necessary include files:

#include <vector>
#include <iostream>
#include <algorithm>

std::sort()
The call to sort is missing the third argument, which should be the comparison to use in the sort.

Answer 2

You can achieve a tremendous speed-up by getting rid of that god-awful nested for-loop and simply thinking harder about the structure of the problem. This leads to the following observations:

Suppose that NONE of the elements of (sorted) arr[1 .. N] lie within the range [P .. Q]. Then either Q < arr[1] or arr[N] < P. In the first case, the min distance is clearly maximized by choosing M == P; in the second case, by choosing M == Q.

Otherwise find i (minimum) and j (maximum) such that each arr[k], for k in [i .. j], is in [P .. Q]. A little thought shows that the min distance is maximized by one of:

(a) P and arr[i]: Choose M = P

(b) arr[j] and Q: Choose M = Q

(c) M = (arr[k] + arr[k+1]) / 2 for some k in [i .. j]

I trust you can code that.

Answer 3

    for(int i=0;i<size;i++)
    {   int templ
        std::cin>>temp;

Is that really the code you tested? I don't think it ought to compile...

---

As far as performance goes, it seems to me that with online judge questions in general you should assume that it's not required to iterate over 10^9 cases. I'm not going to describe an algorithm in detail, because that would IMO be missing the point, but ask yourself this: if the problem statement said \$1 \le N \le 1\$, would you still want to iterate over \$Q - P\$ cases or would there be a constant-time solution?

Answer 4

Performance

You shouldn't rely only on big O notation to calculate real time. It is theoretical runtime scaling on some condition. There are a lot of conditions that come into play when you run on machine. Always measure.

push_back

You should use reserve() if its possible. In the current situation, you could easily write arr.reserve(size). It is implementation detail of the std::vector that it resizes every time it runs out of capacity. It usually increases exponentially, but multiplier is implementation defined (it's been 2 as long as I've seen).

Implementation defined

#include <bits/stdc++.h>

The contents of the header is totally implementation defined. You should never use it. I know that adding additional includes may take time, but generally you will get more feature complete versions if you include appropriate headers.

You do comparison to uninitialized variable:

if(dist>answer)

Seems like you're very lucky. You should initialize it to avoid undefined behavior. Also, increase level of warnings of the compiler, since it usually notifies about such parts of the code.

C++ way

For INT_MAX and INT_MIN you could as well use

std::numeric_limits<int>::max();
std::numeric_limits<int>::min();

Your inner loop could be replaced with range loop since you don't need the index.

   for(const auto& element: arr)
    {
        diff=fabs(i-element);
        if(diff>dist)
            break;
        dist=std::min(dist,diff);

    }