Produsul tuturor celorlalte elemente, în C++

Pentru vectorul 2 3 4, vrem rezultatul 12 8 6: la fiecare poziție înmulțim toate valorile, cu excepția celei de pe poziția respectivă. Formula „produs total împărțit la element” pare simplă, dar nu funcționează când apar zerouri.

Împărțim vecinii în două părți

Pentru poziția i, valorile excluzând a[i] formează partea din stânga și partea din dreapta. Calculăm produsul fiecăreia și le înmulțim. Prefixul este partea de la începutul vectorului, iar sufixul este partea care ajunge până la final.

Citim 1≤n≤18 și valori întregi între -10 și 10. Limita mică pentru n este intenționată: toate produsele intermediare au modul cel mult 10^18 și încap în long long. Nu promitem funcționarea pentru un vector arbitrar de lung, deoarece numărul de cifre al produsului poate crește rapid.

La prima parcurgere, p este produsul valorilor strict din stânga. Scriem p în b[i], apoi îl înmulțim cu a[i] pentru pasul următor. La parcurgerea inversă, p este produsul strict din dreapta; înmulțim b[i] cu acesta înainte de a include a[i].

Pentru 2,3,4, produsele strict din stânga sunt 1,2,6, iar cele strict din dreapta sunt 12,4,1. Înmulțirea pe coloane dă 12,8,6.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    long long a[18],b[18];
    for(int i=0;i<n;++i) cin >> a[i];
    long long p=1;
    for(int i=0;i<n;++i) { b[i]=p; p*=a[i]; }
    p=1;
    for(int i=n-1;i>=0;--i) { b[i]*=p; p*=a[i]; }
    for(int i=0;i<n;++i) cout << (i?" ":"") << b[i];
    cout << '\n';
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    vector<long long> a(n),b(n);
    for(int i=0;i<n;++i) cin >> a[i];
    long long p=1;
    for(int i=0;i<n;++i) { b[i]=p; p*=a[i]; }
    p=1;
    for(int i=n-1;i>=0;--i) { b[i]*=p; p*=a[i]; }
    for(int i=0;i<n;++i) cout << (i?" ":"") << b[i];
    cout << '\n';
}

De ce inițializăm cu 1

În stânga primei poziții și în dreapta ultimei nu există elemente. Produsul unei mulțimi goale de factori este 1, elementul neutru al înmulțirii. Pentru n=1, rezultatul este deci 1, conform acestei convenții declarate.

Pentru 2 3 4, produsele din stânga sunt 1 2 6, iar cele din dreapta sunt 12 4 1. Înmulțirea pe poziții produce 12 8 6. Pentru 2 0 4, obținem 0 8 0: doar poziția zeroului exclude acel factor. Dacă există două zerouri, fiecare produs rămas conține cel puțin unul și toate rezultatele sunt zero.

Ordinea actualizărilor este esențială. Dacă înmulțești întâi p cu a[i] și abia apoi îl scrii în rezultat, incluzi tocmai elementul pe care trebuia să îl excluzi. Folosim un indice întreg cu semn în bucla inversă, astfel încât scăderea de la zero să permită oprirea.

Timpul este O(n), prin două parcurgeri. Rezultatul are O(n) memorie, pe lângă date; în afara lui folosim numai câteva variabile. Tablourile clasice rezervă 18 celule fiecare, din care utilizăm primele n.

Exersează

Verifică 2 3 4, 2 0 4, 0 0 5, -2 3 -4 și vectorul cu un singur 7. Rezultatele sunt 12 8 6, 0 8 0, 0 0 0, -12 8 -6 și 1. Explică semnul fiecărui produs înainte să rulezi programul.

Continuă cu sume prefix, produse și limitele tipurilor.

Întrebări frecvente

Cum calculez produsul tuturor elementelor în afară de cel curent?

Pentru fiecare poziție, înmulțește produsul elementelor din stânga cu produsul celor din dreapta. Produsele prefix și sufix permit obținerea tuturor rezultatelor în timp O(n).

De ce nu împart produsul total la elementul curent?

Dacă elementul este zero, împărțirea nu este definită. Metoda cu prefixe și sufixe evită împărțirea și tratează natural zerourile, în limitele numerice declarate.

Ce rezultate obțin dacă vectorul conține două zerouri?

Toate produsele care exclud o singură poziție sunt zero, deoarece în fiecare rămâne cel puțin un zero. Cu exact un zero, numai poziția acelui zero poate avea rezultat nenul.