Program to Find Minimum Scalar Product of Two Vectors

To minimise the scalar product of two integer arrays, sort one array ascending and the other descending, then compute the element-wise sum of products.

What Is the Minimum Scalar Product Problem?

The dot product (also called the scalar product) of two n-element vectors A and B is the sum A[0]*B[0] + A[1]*B[1] + … + A[n-1]*B[n-1]. The elements are fixed; you control how to pair them.

The problem: given two integer arrays of equal length n, find a permutation of each that produces the smallest possible sum of pairwise products. This is not asking for the minimum over all reorderings of a single array; it asks for the best pairing across two independent arrays.

This appears in campus placement aptitude rounds as a coding question, in online tests with a greedy algorithm section, and as a sub-problem in certain analytical-coding assessments. See the DE Shaw campus recruitment process for the kind of algorithmic reasoning problems that appear in rigorous aptitude-plus-coding rounds.

Two standard examples, with verified answers:

• n = 3, A = [1, 3, 5], B = [2, 4, 1]: minimum scalar product = 15
• n = 5, A = [1, 2, 3, 4, 5], B = [1, 0, 1, 0, 1]: minimum scalar product = 6

How those answers are derived is what the next section covers.

The Greedy Algorithm

Three steps:

• Sort A in ascending order.
• Sort B in descending order.
• Compute sum = A[0]*B[0] + A[1]*B[1] + ... + A[n-1]*B[n-1].

That sum is the minimum scalar product. No need to enumerate permutations or use dynamic programming.

Walkthrough: Sample 1

Input: n = 3, A = [1, 3, 5], B = [2, 4, 1]

• Sort A ascending: [1, 3, 5]
• Sort B descending: [4, 2, 1]
• Dot product: 1×4 + 3×2 + 5×1 = 4 + 6 + 5 = 15

Walkthrough: Sample 2

Input: n = 5, A = [1, 2, 3, 4, 5], B = [1, 0, 1, 0, 1]

• Sort A ascending: [1, 2, 3, 4, 5]
• Sort B descending: [1, 1, 1, 0, 0]
• Dot product: 1×1 + 2×1 + 3×1 + 4×0 + 5×0 = 1 + 2 + 3 + 0 + 0 = 6

Both match the expected answers.

Why It Works: Rearrangement Inequality

The rearrangement inequality is the formal justification. It states: if a1 ≤ a2 ≤ … ≤ an and b1 ≤ b2 ≤ … ≤ bn are two sorted sequences of real numbers, then pairing them in opposite order (a1 with bn, a2 with b(n-1), and so on) gives the minimum possible sum of products, and pairing them in the same order gives the maximum.

The intuition is numerical. A large positive B value multiplied by a large positive A value adds a big positive number to the sum. To drag the total down, pair the large B values with the smallest (most negative) A values, and pair the small B values with the largest A values. Sorting A ascending and B descending forces exactly that pairing.

The formal argument is an exchange proof. Suppose the current pairing is not optimal. Then there exist indices i and j where A[i] is smaller than A[j] but B[i] is also smaller than B[j] (the sequences are in the same relative order at those positions). Swapping B[i] and B[j] changes the total by:

• New contribution: A[i]*B[j] + A[j]*B[i]
• Old contribution: A[i]*B[i] + A[j]*B[j]
• Difference: (A[i]*B[j] + A[j]*B[i]) - (A[i]*B[i] + A[j]*B[j]) = (A[i] - A[j]) * (B[j] - B[i])

Since A[i] is smaller than A[j], the factor (A[i] - A[j]) is negative. Since B[i] is smaller than B[j], the factor (B[j] - B[i]) is positive. Their product is negative, so the swap reduces the sum. Any pairing where A and B are not in strictly opposite sort orders can be improved. The global minimum is therefore the (A ascending, B descending) pairing.

Verifying with a Worked Example

Take A = [1, 3, -5] and B = [-2, 4, 1].

Applying the Greedy

• Sort A ascending: [-5, 1, 3]
• Sort B descending: [4, 1, -2]
• Dot product: (-5)×4 + 1×1 + 3×(-2) = -20 + 1 + (-6) = -25

Brute-Force Confirmation

Fix A in its original order [1, 3, -5] and check every permutation of B:

• B = [-2, 4, 1]: 1×(-2) + 3×4 + (-5)×1 = -2 + 12 - 5 = 5
• B = [-2, 1, 4]: 1×(-2) + 3×1 + (-5)×4 = -2 + 3 - 20 = -19
• B = [4, -2, 1]: 1×4 + 3×(-2) + (-5)×1 = 4 - 6 - 5 = -7
• B = [4, 1, -2]: 1×4 + 3×1 + (-5)×(-2) = 4 + 3 + 10 = 17
• B = [1, -2, 4]: 1×1 + 3×(-2) + (-5)×4 = 1 - 6 - 20 = -25
• B = [1, 4, -2]: 1×1 + 3×4 + (-5)×(-2) = 1 + 12 + 10 = 23

The minimum across all six permutations is -25, which matches the greedy result.

The permutation [1, -2, 4] gives the same three element pairings as the greedy: (-5, 4), (1, 1), and (3, -2), just listed in a different order. Addition is commutative, so the same pairings produce the same sum regardless of order.

Complete Code Implementations

Each implementation below reads n, then the elements of A, then the elements of B from standard input and prints the minimum scalar product.

C

#include <stdio.h>
#include <stdlib.h>

int cmp_asc(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int cmp_desc(const void *a, const void *b) {
    return (*(int *)b - *(int *)a);
}

int main(void) {
    int n;
    scanf("%d", &n);
    int a[100], b[100];
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i++) scanf("%d", &b[i]);
    qsort(a, n, sizeof(int), cmp_asc);
    qsort(b, n, sizeof(int), cmp_desc);
    long long sum = 0;
    for (int i = 0; i < n; i++) sum += (long long)a[i] * b[i];
    printf("%lld\n", sum);
    return 0;
}

qsort from <stdlib.h> accepts a comparator function. cmp_asc returns negative when a is smaller (ascending order); cmp_desc returns negative when b is smaller (descending order). The long long accumulator guards against integer overflow when elements are large.

For n = 3, A = [1, 3, -5], B = [-2, 4, 1], the output is -25.

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    sort(a.begin(), a.end());
    sort(b.begin(), b.end(), greater<int>());
    long long sum = 0;
    for (int i = 0; i < n; i++) sum += (long long)a[i] * b[i];
    cout << sum << "\n";
    return 0;
}

greater<int>() as the comparator for std::sort inverts the default ascending order to produce descending order. The long long cast in the accumulator prevents overflow.

For n = 5, A = [1, 2, 3, 4, 5], B = [1, 0, 1, 0, 1], the output is 6.

Java

import java.util.Arrays;
import java.util.Scanner;

public class MinScalarProduct {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Integer[] a = new Integer[n];
        Integer[] b = new Integer[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        for (int i = 0; i < n; i++) b[i] = sc.nextInt();
        Arrays.sort(a);
        Arrays.sort(b, (x, y) -> Integer.compare(y, x));
        long sum = 0;
        for (int i = 0; i < n; i++) sum += (long) a[i] * b[i];
        System.out.println(sum);
    }
}

Integer[] is required instead of int[] because Arrays.sort needs a reference type to accept a custom comparator. The lambda (x, y) -> Integer.compare(y, x) reverses the natural order to give descending sort.

Python

def min_scalar_product(a, b):
    a_sorted = sorted(a)                # ascending
    b_sorted = sorted(b, reverse=True)  # descending
    return sum(x * y for x, y in zip(a_sorted, b_sorted))

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
print(min_scalar_product(a, b))

sorted() returns a new list and leaves the originals unchanged. For n = 3, A = [1, 3, -5], B = [-2, 4, 1], min_scalar_product returns -25. For in-place sorting, use a.sort() and b.sort(reverse=True) to save the O(n) allocation cost.

Time and Space Complexity

Step	Time	Space
Sort A ascending	O(n log n)	O(1) in-place
Sort B descending	O(n log n)	O(1) in-place
Dot product loop	O(n)	O(1)
Overall	O(n log n)	O(1)

The two sorts dominate. The dot product loop adds O(n) but that is absorbed by the sort cost. For the array sizes that appear in campus placement coding questions, O(n log n) is more than fast enough.

There is no O(n) solution for this problem in the comparison model. Any correct algorithm must at minimum confirm the relative order of elements, which takes at least O(n log n) comparisons. The greedy approach therefore has optimal asymptotic complexity.

The only caveat is Python’s sorted(), which creates a new list and so uses O(n) extra space. Use a.sort() and b.sort(reverse=True) for in-place variants if memory is constrained.

For placement tests, recognising the rearrangement inequality class of problems reduces any “find the optimal pairing” question to a two-line sort. The greedy chapter in the best books for placement preparation covers this pattern in detail. Campus aptitude rounds typically pair an array-manipulation coding question like this with time and work quantitative aptitude questions in the same session.

The sort-then-pair pattern from this problem reappears inside LLM systems: ranking a set of document vectors by dot product against a query vector follows the same O(n log n) logic. TinkerLLM at ₹299 connects the -25 computation here to how cosine similarity drives document retrieval in production search pipelines, starting from problems at exactly this level of arithmetic.