-2
\$\begingroup\$

Given an array A with N number of elements, for each element \$i\$ (\$1 \le i \le N\$), find \$x + y\$, where \$x\$ is the largest number less than \$i\$ such that \$A[x] > A[i]\$ and \$y\$ is the smallest number greater than \$i\$ such that \$A[y] > A[i]\$.

If there is no \$x < i\$ where \$A[x] > A[i]\$, \$x=-1\$, similarly

If there is no \$y > i\$ where \$A[y] > A[i]\$, \$y=-1\$

The tricky part is:

\$1 \le N \le 10^6\$

\$1 \le A[i] \le 10^{18}\$

Sample

Input:

5

5 4 1 3 2

Output:

-2 0 6 1 3

This is failing a few test cases:

#include <iostream>
using namespace std;
int main()
{
    int n,i; 
    cin >> n;
    long int a[n];
    for(i=1;i<=n;i++)
        cin >> a[i];
    int x,y,c,d,s1,s2;
    for(i=1;i<=n;i++){
        c=0;
        d=0;
        s1=-1;
        s2=-1;
        x=i-1;
        while(x>0){
            if(a[x]>a[i]){
                s1=x;
                break;
            }
            else{ 
                x--;
            }
        }
        y=i+1;
            while(y<=n){
                if(a[y]>a[i]){
                    s2=y;
                    break;
                }
                else 
                    y++;
            }
        int s=s1+s2;
        cout << s << " ";
    }
    return 0;
}
\$\endgroup\$

closed as off-topic by alecxe, t3chb0t, Graipher, forsvarir, Heslacher Jun 29 '17 at 6:19

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – alecxe, t3chb0t, Graipher, Heslacher
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ It looks to me that your code has a bug. 0 is a valid index but your while loop exits when x == 0. It should probably be set for x>=0. \$\endgroup\$ – tinstaafl Jun 28 '17 at 15:51
  • 3
    \$\begingroup\$ You say it's "failing a few test cases". Is it functionally incorrect, or is it merely insufficiently performant? That's the difference between unready and ready for review. \$\endgroup\$ – Toby Speight Jun 28 '17 at 16:05
  • 1
    \$\begingroup\$ Two comments either way: VLAs are not a C++ thing, and using namespace std is bad mojo. \$\endgroup\$ – Deduplicator Jun 28 '17 at 16:14
4
\$\begingroup\$

The code is almost unreadable. The single-letter variable names don't convey very much, the indentation is inconsistent, and the logic is opaque.

I'd start by dropping using namespace std; and separating the I/O from the program logic so that you can at least code a few test cases to ease debugging and improvement.

That variable-sized array looks risky, even with compilers that support that (non-standard) extension. Even with moderate limit of n < 1 million, that's still quite a lot to put on your stack. Consider allocating with new[] or (better) using a std::vector.

And what are c and d for? They are both set to zero, but never used.

Further points:

long int may have a size of just 32 bits at a minimum, meaning a maximum range of up to 2,147,483,647. To guarantee you can hold positive integers up to 1e18, you'll want an unsigned long long, or (better) std::uint_least64_t. Similarly, the range of int may be only -32,767 to 32,767, so I'd suggest std::uint_least32_t for the index values.

Here's how I would restructure the program:

#include <cstdint>
#include <istream>
#include <vector>

using Integer = std::uint_least64_t;
using IndexSum = std::int_least32_t;

std::vector<Integer> read_input(std::istream& in);
std::vector<IndexSum> add_closest_indices_of_greater_values(const std::vector<Integer>&);

#include <iostream>
#if TEST
int main()
{
    std::vector<IndexSum> actual = add_closest_indices_of_greater_values({
        5, 4, 1, 3, 2
    });
    std::vector<IndexSum>expected = {-2, 0, 6, 1, 3 };
    if (actual == expected)
        return 0;

    for (const auto& a: {actual, expected}) {
        for (auto n: a)
            std::cerr << n << " ";
        std::cerr << std::endl;
    }

    return 1;
}
#else
int main()
{
    std::vector<Integer> a = read_input(std::cin);
    std::vector<Integer> b = add_closest_indices_of_greater_values(a);
    for (auto n: b)
        std::cout << n << " ";
}
#endif

You can then compile with TEST defined, and refine add_closest_indices_of_greater_values() until you get the correct output:

std::vector<IndexSum> add_closest_indices_of_greater_values(const std::vector<Integer>& a)
{
    std::vector<IndexSum> out;
    auto n = a.size();
    out.reserve(n);
    for(auto i=0u;  i<n;  i++){
        IndexSum s1 = -1;
        IndexSum s2 = -1;
        // search for nearest prior element greater than this one
        for (auto x = i;  0 < x;  --x) {
            if (a[x-1] > a[i]) {
                s1 = x;
                break;
            }
        }
        // search for nearest following element greater than this one
        for (auto x = i+1;  x < n;  ++x) {
            if (a[x] > a[i]) {
                s2 = x+1;
                break;
            }
        }
        out.push_back(s1+s2);
    }
    return out;
}

And it's a simple matter to read the input:

std::vector<Integer> read_input(std::istream& in)
{
    std::vector<Integer> a;
    in.exceptions(std::istream::failbit);

    std::size_t n;
    in >> n;
    a.reserve(n);
    for (size_t i = 0u;  i < n;  ++i)
        in >> a[i];

    return a;
}

All you need to do now is to improve the algorithm so it no longer performs a linear search for each element. You may want to instrument how many times you dereference the array, in order to reduce the complexity of the algorithm.

\$\endgroup\$
0
\$\begingroup\$

To begin with, valid indices to a[n] are 0 .. n-1. The loop for(i=1;i<=n;i++) accesses memory beyond the array, which invokes undefined behaviour.


The algorithm has a quadratic time complexity. There is a linearithmic solution (since it seems to be a competitive programming question, I will not spell the algorithm out).

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.