Returning index in a subarray based on divisibility by another number

Question

I am trying to return index in a subarray before which all elements in the subarray are divisible by some large number K (type long long). I have managed to write the correct code but the complexity is not great. Can anyone suggest a better way to do this to optimize the runtime?

long long solve (vector<long long> A, long long K, int R, int L) {

       int index=L-1;
       int count=0;
       while(A[index]%K==0 && index<=R-1){
           if(A[index]%K==0){
               count++;
           }
           index++;
       }
        if(count!=0){
            return (L+count-1);
        }
        else{
            return -1;
        }
}

Here, the parameters are: L is leftmost bound of the subarray R is rightmost bound of the subarray A is a vector holding the entire array. A={1,2,4,5,7,9}

For example, if I pass L=2, R=4, K=2 then it will return the index=3 (indexes start from 1). In other words, from index 1 to 3 in the vector we are checking from L up to R whichever element is divisible by K. We go forward until an element in this sequence fails to fulfill the divisibility criteria. We then print its ending index. Otherwise, if no such element fulfills the criteria, we return -1

That's probably the best algorithm, you can't really check every element in less than `O(n)` time. Probably your main bottleneck is unnecessary copy of `std::vector` in argument, you should pass it by const reference. One thing to improve in algorithm would be getting rid of `if(A[index]%K==0){ count++; }` altogether and returning `index` if `index != L-1` (i.e. different than starting index). — Yksisarvinen, Jun 06 '19 at 14:10
Since `K` is constant, this might be a relevant question: [Repeated integer division by a runtime constant value](https://stackoverflow.com/q/45353629/580083). — Daniel Langr, Jun 06 '19 at 14:11
That would belong better in stack exchange code review. But using `std::span` or `gsl::span` would yield better performance for sure — Guillaume Racicot, Jun 06 '19 at 14:12
@VladfromMoscow probably because the vector size can be too large and indices may be allocated using long long. — harshrd, Jun 06 '19 at 14:13
@harshrd Do you need to return the index of the first element in the range that does not satisfy the condition? — Vlad from Moscow, Jun 06 '19 at 14:17
I'd prefer the function to take an iterator range as an input and return an iterator so it's consistent with the C++ standard library. — Bathsheba, Jun 06 '19 at 14:17
@Yksisarvinen That didn't work out. The test cases are running out of time. — harshrd, Jun 06 '19 at 14:20
@VladfromMoscow No actually I have to return the index where the divisibility criteria was last met. — harshrd, Jun 06 '19 at 14:22
@harshrd As I said already the function design is very bad. Don;t spent your time to write the function. At first redesign it. — Vlad from Moscow, Jun 06 '19 at 14:22
Did you change `vector A` to `const vector& A` in function parameters? This is the only thing that can visibly improve performance here (and the trick mentioned by Danel Langr possibly, though I only expect it to matter in a competition like task) — Yksisarvinen, Jun 06 '19 at 14:24
@Yksisarvinen I tried to change vector to const vector but then the input stream operator doesn't work. — harshrd, Jun 06 '19 at 14:28
@harshrd You should change the type of `A` parameter from vector to a constant vector reference, not the type of the vector argument itself. Better, you should first learn some C++ basics by reading some good book for beginners, (not only) to understand the difference. — Daniel Langr, Jun 06 '19 at 14:33
The example you posted shows a sorted vector. Is that always the case? — Bob__, Jun 06 '19 at 14:38

Vlad from Moscow · Answer 1 · 2019-06-06T15:07:39.697

It is a very bad design of the function that does not follow the C++ concepts.

For starters indices in C++ starts from 0. Secondly a range is specified as [start, end) that is end is not included in the range.

The function should return an object of the type std::vector<long long>::size_type. If an element that satisfies the condition is not found in the range then the function should return the value of end.

I would write the function the following way as it is shown in the demonstrative program

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

auto solve( const std::vector<long long> &v, 
            std::vector<long long>::size_type first,
            std::vector<long long>::size_type last,
            long long value )
{
    last  = std::min( last, v.size() );
    first = std::min( first, last );

    auto current = first;

    while ( ( current != last ) && ( v[current] % value == 0 ) ) ++current;

    return current == first ? last : current - 1;
}

int main()
{
    using size_type = std::vector<long long>::size_type;

    std::vector<long long> v = { 1, 2, 4, 5, 7, 9 };

    size_type first   = 1;
    size_type last    = 3;
    long long divisor = 2;

    auto i = solve( v, first, last, divisor );

    if ( i != last )
    {
        std::cout << "The last element divisible by " << divisor
                  << " in the range [" << first
                  << ", " << last
                  << ") is at position " << i << '\n';
    }
    else
    {
        std::cout << "There is no element divisible by " << divisor 
                  << " in the range [" << first 
                  << ", " << last << ")\n";
    }
}

Its output is

The last element divisible by 2 in the range [1, 3) is at position 2

You could write the same function using iterators. In this case the function declaration would look simpler.

For example

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

auto solve( std::vector<long long>::const_iterator first, 
            std::vector<long long>::const_iterator last,
            long long value )
{
    auto it = std::find_if_not( first, last, 
                                [&value]( const long long &item ) { return item % value != 0; } );

    return it == first ? last : std::prev( first );
}

int main()
{
    std::vector<long long> v = { 1, 2, 4, 5, 7, 9 };

    auto first = std::next( std::cbegin( v ), 1 );
    auto last  = std::next( std::cbegin( v ), 3 );
    long long divisor = 2;

    auto it = solve( first, last, divisor );

    if ( it != last )
    {
        std::cout << "The last element divisible by " << divisor
                  << " in the range [" << std::distance( std::cbegin( v ), first )
                  << ", " << std::distance( std::cbegin( v ), last )
                  << ") is at position " << std::distance( std::cbegin( v ), it ) << '\n';
    }
    else
    {
        std::cout << "There is no element divisible by " << divisor 
                  << " in the range [" << std::distance( std::cbegin( v ), first ) 
                  << ", " << std::distance( std::cbegin( v ), last ) << ")\n";
    }
}

I am taking the vector elements as input from the user and is not hard-coded. How can I implement a const vector as a parameter? Can you suggest some guide from where I can learn more about it? — harshrd, Jun 06 '19 at 16:09
@harshrd It is the function parameter has constant reference type. You may pass as an argument any vector constant or non-constant. — Vlad from Moscow, Jun 06 '19 at 16:13

score 0 · Answer 2 · answered Jun 06 '19 at 15:46

Your logic is flawed as it doesn't break out of the loop on the else case. Rather than work on fixing that I'd suggest moving to using standard algorithms rather than writing your own, for example:

const auto start = next(cbegin(A), L - 1);
const long long finish = distance(start, find_if(start, next(cbegin(A), R - 1), bind(modulus<int>(), placeholders::_1, K)));
const auto result = finish == 0 ? -1 : finish;

As is mentioned by Vlad from Moscow your 1-based indexing increases the complexity. If you were willing to use 0-based indexing, go to a 0 return instead of -1, and use a lambda you could just do:

const auto result = count_if(next(cbegin(A), L), next(cbegin(A), R), [=](const auto i) { return i % K == 0; })

Returning index in a subarray based on divisibility by another number

2 Answers2