Increasing all elements by an integer x in O (n) in program capability?
So I came across a problem:
I need to create a data structure that will have a set of integers. It must have methods: The class is called:
Class structure
methods:
void structure :: new (); // creates an empty set
void structure :: insert (int x); // inserts integer x into the set
Structure bool :: isElement (int x); // checks if x is in the set
void structure :: increaseBy (int x); // increases all elements in set x
I'm assuming this question is homework.
But I just want an opinion on what data structure is best to use in this implementation.
And how can I create a final method that would increase all elements by x by O (1) times, at first it seems impossible. Even if there are some C ++ operators that have this kind of functionality, wouldn't they have the same complexity?
I mean, I could use a vector, an array, even some linked list, set, or similar structures.
So the problems are not with the first three ways, they are quite easy to do, and it is also good to use O (n) for the latter, but these are not "full points" if it is O (1) time complexity. So is there a way to do this? Any hints would be helpful and also I apologize if I made a mistake in posting this question my first time posting on stackoverflow.com, I have only / not posting math.stackexchange.com so far, so any advice would be appreciated. how good.
Thanks in advance.
source to share
Here's a possible implementation
class structure
{
public:
void insert(int x) {ls.push_front(x - offset);}
bool isElement(int x) {return std::find(ls.begin(), ls.end(), x - offset) != ls.end();}
void increaseBy(int x) {offset += x;}
private:
int offset = 0;
std::list<int> ls;
};
it
- O (1) for
insert
- O (n) for
isElement
- O (1) for
increaseBy
source to share
Add a class to the class addedSum
:
template<typename Set> struct setWithInc {
Set container;
int addedSum;
setWithInc() : addedSum(0) {}
bool isElement(int x) {
return container.find(x - addedSum) != container.end();
}
void insert(int x) {
container.insert(x - addedSum);
}
void increaseBy(int x) {
addedSum += x;
}
};
source to share