Grade 9 · 10 algorithmsCitește în română

Frequency arrays, prefix sums and the Sieve of EratosthenesFrecvență, sume parțiale și ciurul lui Eratostene

Every frequency arrays, prefix sums and the sieve of eratosthenes algorithm from the Romanian high school curriculum, with the idea explained, its complexity, examples and code you can edit and run right here.

Create a free account Browse the collection

10algorithms
8chapters
1grade

Frequency arrays, prefix sums and the Sieve of Eratosthenes

Frecvență, sume parțiale și ciurul lui Eratostene · 10 algorithms

Common digits of two numbersCifrele comune a două numereIn two arrays of 10 positions we mark which digits appear in each number (aparA[c], aparB[c]). The common digits are the ones marked in both arrays;…O(n)
Sieve of EratosthenesCiurul lui EratosteneFinds all prime numbers up to n. We start with all numbers unmarked; for every unmarked i (hence prime) we mark its multiples as not prime, starting…O(n log n)
Majority elementElementul majoritarThe majority element appears more than n / 2 times. The voting algorithm (Boyer-Moore) keeps a candidate and a counter: an element equal to the…O(n)
The missing number in a permutationNumărul lipsă dintr-o permutaren and n - 1 distinct numbers from the set {1, 2, ..., n} are given; exactly one is missing. The sum of all numbers from 1 to n is n · (n + 1) / 2…O(n)
Subarray of length k with the maximum sumSecvența de lungime k cu suma maximăSliding window: we compute the sum of the first k elements, then slide the window one position to the right: we add the element that enters (v[i])…O(n)
Maximum subarray sum (Kadane's algorithm)Secvența de sumă maximă (algoritmul lui Kadane)We go through the array and keep the sum of the current subarray, which ends at position i. If the sum so far has become negative, it no longer…O(n)
Prefix sumsSume parțiales[i] = v[1] + v[2] + ... + v[i], with s[0] = 0, is computed in a single pass: s[i] = s[i - 1] + v[i]. Then the sum over any range [st, dr] is s[dr]…O(n)
Distinct values and their frequenciesValorile distincte și frecvențele lorOnce the frequency array is built, the distinct values are the indices val with frecv[val] > 0. Going through them in increasing order, we print…O(n)
Marking ranges with a difference arrayMarcarea intervalelor cu vectorul de diferențeWe have n positions, initially 0, and m operations 'add 1 to positions a..b'. Instead of walking every range, we only note its ends: d[a]++ (it…O(n)
Frequency arrayVectorul de frecvențăFor small natural values (here 0..1000), frecv[x] stores how many times the value x has appeared. The value becomes an index, so every number read…O(n)