Grandi attese per un piccolo incremento

Abbiamo ricevuto l'incarico di scrivere una funzione in C++ che deve rispettare le seguenti specifiche:

input: un vettore di interi positivi
output: un long

Il long in output deve essere generato in modo tale che sia pari al valore più elevato ottenibile come produttoria dei valori passati in input, considerando che possiamo incrementare di una unità uno e un solo elemento dell'array.

Ad esempio, se in input ci viene passato {4,3,2} dobbiamo scegliere se tornare (4+1)*3*2 = 30, 4*(3+1)*2 = 32, o 4*3*(2+1) = 36.

Intermezzo fornito da Belle & Sebastian.


In pratica il requisito può essere tradotto come una richiesta di identificare il minore tra i valori passati, incrementarlo, e ritornare la produttoria. Per autoconvincerci di questo fatto pensiamo ad un caso limite, in cui l'input è composto da {1, 100}. Aggiungendo 1 al primo elemento otteniamo il raddoppio del suo valore, e quindi dell'intera produttoria. Se aggiungessimo 1 al secondo, quel valore crescerebbe solo di un centesimo.

Una prima idea potrebbe essere quella di ordinare in modo crescente il vettore, incrementare il primo elemento, eseguire la produttoria sul vettore modificato:

#include <vector>
#include <algorithm>

long prodPlus1(vector<int> input) // 1.
{
    sort(input.begin(), input.end());
    ++input[0];

    long res = 1;
    for_each(input.begin(), input.end(), [&res] (int i) {res *= i;}); // 2.
    return res;
}

1. Dato che dobbiamo comunque creare una copia del vettore, tanto vale farla implicitamente nell'intestazione della funzione
2. Con for_each scandiamo l'intero vettore, e la funzione lambda si occupa di mettere il risultato della produttoria nella variabile locale res, che poi torneremo al chiamante.

Non è malaccio, come codice. Soprattutto dà una certa soddisfazione scrivere la riga col for_each e la funzione lambda. Ma lascia un po' l'amaro in bocca la copia e il sorting del vettore, entrambe operazioni non necessarie. Infatti, in realtà, a noi interessa trovare e modificare solo un elemento, tutto il resto potremmo risparmiarcelo.

Invece di sort, usiamo allora min_element(), e poi spezziamo il for_each() in due parti, tenendo l'iteratore all'elemento minore del vettore come separatore tra i due tronconi.

Il codice risultante potrebbe dunque essere questo:

#include <vector>
#include <algorithm>

long prodPlus2(const vector<int>& input)
{
    vector<int>::const_iterator it = min_element(input.begin(), input.end());

    long res = (*it) + 1;
    for_each(input.begin(), it, [&res] (int i) {res *= i;});
    for_each(it+1, input.end(), [&res] (int i) {res *= i;});
    return res;
}