M
M
maxkleiman2021-09-21 20:20:39
C++ / C#
maxkleiman, 2021-09-21 20:20:39

How to make the algorithm faster and more efficient?

There are two sequences of numbers:

A[0], A[1], ... , A[n].
B[0], B[1], ... , B[m]. You need to do the following operations with the sequence A:
Remove elements whose indices are multiples of B[0].
From the remaining elements, remove those whose indices are multiples of B[1].
Repeat this process until B[m].
Remove remaining elements.

Program code
#include <iostream>
#include <vector>
#include<iomanip>
using namespace std;
vector <int> divisible_func(vector <int>& a, vector <int>& b) {
    vector <int> c;
    for (size_t i = 0; i < b.size(); i++) {
        for (size_t j = 0; j < a.size(); j++) {
            if (j % b[i] != 0) {
                c.push_back(a[j]);
            }
        }
        a = c;
        c.resize(0);
    }
    a.push_back(-1);
    return a;
}
int main()
{
    int elem1;
    int elem2;
    vector <int> a;
    vector <int> b;
    vector <int> count;
    while (cin >> elem1) {
        if (elem1 == -1) break;
        a.push_back(elem1);
    }
    while (cin >> elem2) {
        if (elem2 == -1) break;
        b.push_back(elem2);
    }
    count = divisible_func(a, b);
    for (size_t i = 0; i < count.size(); i++) {
        cout << count[i] << setw(count.size());
    }
    
    return 0;
}

Answer the question

In order to leave comments, you need to log in

1 answer(s)
A
Alexander Prilepsky, 2021-10-02
@maxkleiman

Yes, it's a strange task. Indexes change at each step. Probably, educational... The resulted implementation can be improved a little;
void divisible_func(std::vector& a, const std::vector& b) {
vector c;
c.reserve(a.size());
for(size_t i = 0; i < b.size(); ++i) {
for(size_t j = 1; j < a.size(); ++j) {
if (j % b[i] != 0) {
c.push_back(a[j]);
}
}
a.swap(c); // capacity swapped
c.clear(); // capacity not changed
}
a.push_back(-1); // ????????????????
}
int main() {
int elem;
vector a;
vectorb;
while (cin >> elem) {
if (elem == -1) break;
a.push_back(elem);
}
while (cin >> elem) {
if (elem == -1) break;
b.push_back(elem);
}
divisible_func(a, b);
for (size_t i = 0; i < a.size(); i++) {
cout << a[i] << std::setw(a.size());
}
}

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question