2
\$\begingroup\$

This is a well-known problem from a HackerRank challenge: Given an array and a number M, output the maximum of all subarray sums modulo M, M between 1 and 1E14. A number of solutions are discussed on stackoverflow.com and geeksforgeeks.org. All of SO solutions seem to use some built-in mechanics, and I don't see how they account for the following cases

A. The solution comes from a subarray that starts from the beginning, as in arr = [2, 2, 2, 3], M = 7 case;
B. Several subarrays that start from the beginning can have the same modulo, and there is no need to study all of them, only the shortest and the longest.

My solution, with A. and B. accounted for, and the only built-in algo I am using is a basic sort, is below. Not sure if it has some added value or an over-engineering.

using namespace std;
#include <vector>
#include <list>
#include <utility>

struct ModInfo {
  long mdl;
  int first_ind;
  int last_ind;
  ModInfo(long mdl, int first_ind, int last_ind) : mdl(mdl), first_ind(first_ind), last_ind(last_ind) {}
};

bool cmp(const pair<long, int> &a, const pair<long, int> &b) {
  if (a.first != b.first)
    return a.first < b.first;
  return a.second < b.second;
}

long maximumSum(vector<long> a, long m) {
  if (m == 1)
    return 0;
  
  // finding modulos of arrays that start from the beginning  
  list<pair<long, int> > cumsum_from_beginning;
  cumsum_from_beginning.push_back(pair<long, int>(0, 0));
  int i = 1;
  for(vector<long>::const_iterator it = a.begin(); it != a.end(); it++, i++) {
    pair<long, int> new_pair(((*it) + cumsum_from_beginning.back().first) % m, i);
    cumsum_from_beginning.push_back(new_pair);
  }
  // ordering by modulo, then index
  cumsum_from_beginning.sort(&cmp);
  
  // for each modulo, find the last indices of the shortest and the longest subarray that have this modulo
  list<pair<long, int> >::const_iterator it = cumsum_from_beginning.begin(), next_it = it;
  list<ModInfo> mod_info;
  while (it != cumsum_from_beginning.end()) {
    next_it++;
    for(; next_it != cumsum_from_beginning.end(); next_it++) {
      if (it->first != next_it->first)
        break;
    }
    next_it--; // like this, it->first == next_it->first
    ModInfo new_elem(it->first, it->second, next_it->second);
    mod_info.push_back(new_elem);
    next_it++; // increment back
    
    it = next_it;
  }  
  // accounting for A.
  long best_so_far = mod_info.back().mdl;
  if (best_so_far == (m - 1))
    return (m - 1);
  
  for(list<ModInfo>::const_iterator it1 = mod_info.begin(); it1 != mod_info.end(); it1++) {
    list<ModInfo>::const_iterator it2 = it1;
    for(it2++; it2 != mod_info.end(); it2++) {
      // formula as in https://www.geeksforgeeks.org/maximum-subarray-sum-modulo-m/
      long best_candidate = m + it1->mdl - it2->mdl;
      if (best_candidate < best_so_far) 
        break;
      if (it1->last_ind > it2->first_ind) {
        best_so_far = best_candidate;
        if (best_so_far == (m - 1))
          return (m - 1);
        break;
      }
    }
  }

  return best_so_far;
}

This solution has passed all HackerRank test cases, so I presume it's correct. Sample test cases:

  • [3 3 9 9 5] mod 7 → 6
  • [1 5 9] mod 5 → 4
  • [1 2 3] mod 2 → 1
  • [2 2 2 3] mod 7 → 6
\$\endgroup\$
0

1 Answer 1

2
\$\begingroup\$

using namespace std; at the global level harms comprehension. If you really need to bring some name into scope, keep it minimised - usually the only need is in templates when we need argument-dependent lookup to fall back to the std function:

template<typname T>
auto measure(T a, T b)
    using std::size;
    return size(a) + size(b);
}

Accept std::vector arguments by const-reference, rather than by value. Copying a large vector could be expensive, and we don't need a copy.

long might not have sufficient range for m - it needs to represent values up to 10¹⁴, but long is only guaranteed up to about 2✕10⁹. We need a wider type, perhaps std::uint_fast64_t.

The cmp() function seems to be a duplicate of std::less for the pair type.

We can reduce some unwieldy type names using auto. For example:

for (auto it = a.begin();  it != a.end();  ++it, ++i) {

And:

for (auto it1 = mod_info.begin();  it1 != mod_info.end();  ++it1) {
    auto it2 = it1;

I don't see why we use a std::list of pairs - why are we not simply using std::vector there?


I found the algorithm hard to follow. Instead of creating a list and sorting it, I prefer to populate a sorted container - std::map is the obvious choice here, mapping cumulative sums to the positions where they appear:

using source_range = std::pair<const void*, const void*>;

std::map<long, source_range> sums;
{
    long total = 0;
    for (auto const& x: a) {
        (total += x) %= m;
        auto [ix, inserted] = sums.try_emplace(total, &x, &x);
        if (!inserted) {
            // update
            ix->second.second = &x;
        }
    }
}

After that, we can duplicate the content of sums, so that we can wrap around from a very large sum to a small one:

auto sum2 = std::vector(sums.begin(), sums.end());
sum2.reserve(2 * sums.size());
std::copy(sums.begin(), sums.end(), std::back_inserter(sum2));

I had wanted to concatenate the ranges as a view, but C++20 is missing the concat() function that's present in Ranges-v3:

// auto sum2 = std::ranges::views::concat(sums, sums);

The search becomes simpler now we have the right data representation:

long biggest = 0;
auto const last = sum2.begin() + sums.size();
for (auto ix = sum2.begin();  ix != last;  ++ix) {
    // Find the next higher sum that could have occurred before
    // this one.
    // This loop is like std::find_if, but exits early if we pass
    // biggest.
    for (auto iy = ix + 1;  ;  ++iy) {
        auto candidate = (ix->first + m - iy->first) % m;
        if (candidate <= biggest) {
            break;
        }
        if (iy->second.second < ix->second.first) {
            biggest = candidate;
            break;
        }
    }
}

(I perhaps might have been clearer to use a custom type rather than std::pair, as expressions such as iy->second.second are still a bit cryptic.)


The test cases all result in a value that's one less than the modulus, which means they are not very diverse. I tested against a set of edge-case values:

EXPECT_EQ(max_mod_sum({1}, -1), 0);
EXPECT_EQ(max_mod_sum({1}, 1), 0);
EXPECT_EQ(max_mod_sum({}, 2), 0);
EXPECT_EQ(max_mod_sum({0}, 2), 0);

and against sets of values that challenge different parts of the implementation (with comments to show which sublist has maximum sum):

EXPECT_EQ(max_mod_sum({0, 0, 0, 1, 0}, 4), 1);
EXPECT_EQ(max_mod_sum({0, 1, 0, 1, 0}, 4), 2);

EXPECT_EQ(max_mod_sum({
            10, 20,
            20, 30, 40,     // this sublist = 90
            60,
        }, 100), 90);

EXPECT_EQ(max_mod_sum({
            10, 20, 30,
            40, 55,         // this sublist = 95
            60, 70
        }, 100), 95);

EXPECT_EQ(max_mod_sum({
            70,
            10, 80,      // this sublist = 90 (cum sum passes 100)
            60,
        }, 100), 90);

EXPECT_EQ(max_mod_sum({
            70,
            70, 80, 40,     // this sublist = 190 ≡ 90
            20,
        }, 100), 90);

Modified code

#include <cstdint>
#include <map>
#include <utility>
#include <vector>

long max_mod_sum(const std::vector<long>& a, const std::uint_fast64_t m)
{
    using source_range = std::pair<const void*, const void*>;

    if (a.empty() || m < 2) {
        return 0;
    }

    std::map<long, source_range> sums;
    {
        long total = 0;
        for (auto const& x: a) {
            (total += x) %= m;
            auto [ix, inserted] = sums.try_emplace(total, &x, &x);
            if (!inserted) {
                // update
                ix->second.second = &x;
            }
        }
    }

    // construct a vector that spans all sums twice, so we get wraparound
    auto sum2 = std::vector(sums.begin(), sums.end());
    sum2.reserve(2 * sums.size());
    std::copy(sums.begin(), sums.end(), std::back_inserter(sum2));

    // I wanted to concatenate the ranges as a view, but C++20 is
    // missing the concat() function from Ranges-v3:
    // auto sum2 = std::ranges::views::concat(sums, sums);

    std::uint_fast64_t biggest = 0;
    auto const last = sum2.begin() + sums.size();
    for (auto ix = sum2.begin();  ix != last;  ++ix) {
        // Find the next higher sum that could have occurred before
        // this one.
        // This loop is like std::find_if, but exits early if we pass
        // biggest.
        for (auto iy = ix + 1;  ;  ++iy) {
            auto candidate = (ix->first + m - iy->first) % m;
            if (candidate <= biggest) {
                break;
            }
            if (iy->second.second < ix->second.first) {
                biggest = candidate;
                break;
            }
        }
        if (biggest == m - 1) {
            break;
        }
    }
    return biggest;
}


#include <gtest/gtest.h>

TEST(MaxModSum, simple)
{
    EXPECT_EQ(max_mod_sum({1}, -1), 0);
    EXPECT_EQ(max_mod_sum({1}, 1), 0);
    EXPECT_EQ(max_mod_sum({}, 2), 0);
    EXPECT_EQ(max_mod_sum({0}, 2), 0);
}

TEST(MaxModSum, values)
{
    EXPECT_EQ(max_mod_sum({0, 0, 0, 1, 0}, 4), 1);
    EXPECT_EQ(max_mod_sum({0, 1, 0, 1, 0}, 4), 2);

    EXPECT_EQ(max_mod_sum({
                10, 20,
                20, 30, 40,     // this sublist = 90
                60,
            }, 100), 90);

    EXPECT_EQ(max_mod_sum({
                10, 20, 30,
                40, 55,         // this sublist = 95
                60, 70
            }, 100), 95);

    EXPECT_EQ(max_mod_sum({
                70,
                10, 80,      // this sublist = 90 (cum sum passes 100)
                60,
            }, 100), 90);

    EXPECT_EQ(max_mod_sum({
                70,
                70, 80, 40,     // this sublist = 190 ≡ 90
                20,
            }, 100), 90);
}
\$\endgroup\$
2
  • \$\begingroup\$ std namespace and long are used was how the HackerRank problem is defined. Your suggestions make sense for real-life problems, thanks! \$\endgroup\$
    – Yulia V
    Feb 9, 2022 at 17:57
  • \$\begingroup\$ I've now properly reviewed the algorithm, and tested an alternative version, in place of that throwaway comment. \$\endgroup\$ Feb 10, 2022 at 4:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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