CODEWITHSUNDEEP
c++algorithmdot-product
hakuna
hakuna

Reputation: 6701

Compute minimum dot product c++

I am trying to compute the minimum dot product for two arrays/vectors. Below are the details:

Problem: given two sequences a1, a2, . . . , and b1, b2, . . . , bn, find a permutation π of the second sequence such that the dot product of a1, a2, . . . , an and bπ1, bπ2, . . . , bπn is minimum.

My logic is working fine but when i try for input as below , its failing due to integer overflow. What data types i shall use for accommodating my condition 1 ≤ n ≤ 10^3; −10^5 ≤ ai, bi ≤ 10^5 for all 1 ≤ i ≤ n

1

99999

99999

The out put for the above scenario should be 9999800001 , but i am getting 1409865409

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

using std::vector;

int64_t min_dot_product(int n, vector<int> a, vector<int> b) {
    int64_t result = 0;
    if (n != 0)
    {
        std::sort(a.begin(), a.end());
        std::sort(b.begin(), b.end());
        std::reverse(a.begin(), a.end());

        /*for (long long int i = 0; i < n; i++) {
            result += a[i] * b[n - 1 - i];
        }*/

        result = std::inner_product(a.begin(), a.end(), b.begin(), 0);
    }
    return result;
}

int main() {
    int n;
    std::cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        std::cin >> b[i];
    }
    std::cout << min_dot_product(n, a, b) << std::endl;
}

Upvotes: 1

Views: 835

Answers (1)

Rishit Sanmukhani
Rishit Sanmukhani

Reputation: 2269

Make following changes:

  1. Replace vector<int> by vector<int64_t> to store number in 64 bit integer.

  2. Use result = std::inner_product(a.begin(), a.end(), b.begin(), 0LL);
    (0LL suggest that result is int64_t)

The problem is that you are storing it in int32_t and so multiplication overflows.

Upvotes: 3

Related Questions