Code for calculating citizens beheaded

Recently I came across this problem ,


A despotic king decided that his kingdom needed to be rid of
corruption and disparity. He called his prime minister and ordered
that all corrupt citizens be put to death. Moreover, he wanted this
done quickly.


The wily prime minister realised that investigating every citizen to
decide who was corrupt and who was not was rather difficult. So he
decided on the following plan: He ordered all the citizens to appear
in the court one by one and declare their wealth.


The king does not sit in the court all the time (he has other
important business to attend to - for instance, meet dignitaries from
neighbouring kingdoms, spend time with his family ...) Whenever the
king walks into the court, the prime minister pulls out the richest
man who has appeared before the court so far and is still alive and
beheads him for being corrupt. Since the rich are more likely to be
corrupt, he hopes to get rid of most of the corrupt and the king is
happy as he sees his policy being implemented enthusiastically.


Suppose the wealth of the citizens trooping into the court is 1 3 7
6 5 18 9 11 2 4


and the king walked in three times: the first time after the first
four persons have seen the minister, the second time after the first
five persons have seen the minister and, finally after the first nine
persons have seen the minister.


At the king's first visit the richest person to have met the minister
has wealth 7 and he would be beheaded. At the second visit, the wealth
of the richest person who has met the minister and is still alive has
wealth 6 and so he would be beheaded. At the third visit the richest
person to have met the minister who is still alive has wealth 18 and
so he would be beheaded.


You may assume that the input is such that whenever the king walks in,
it is always possible to behead someone.


Your aim is to write a program that will

i am completely useless

• That int i in main. You never read it. Remove it.

• The std::vector visits in main. Never used in any way. Remove it.

What are you doing there?

int findGreatest(std::vectorvec) {

That sounds good, but why make a copy of the (entire) vector? Better take it by const reference, you don't plan to modify it in that function:

int findGreatest(std::vector const & vec) {

Now what follows is not so good:

int n = vec.size(); // better use size_t
    int arr[n][n]; // This is NOT C++!
    for(int i=0;i=0;i--){
        for(int j=0;j arr[i+1][j+1]){
                arr[i][j] = arr[i+1][j];
            }else{
                arr[i][j] = arr[i+1][j+1];
            }
        }
    }
    return arr[0][0];
}

Let's take a step back and see what you're trying to achieve: Finding the greatest element in a vector. To do that, iterate over the vector, tracking the currently greatest element:

int currentMax = std::numeric_limits::min(); // or INT_MIN
for (size_t i = 0; i  currentMax) {
    currentMax = vec[i];
  }
}

As this is a rather useful concept, there's of course a function for it: std::max_element. Though this does not return the value, but rather an iterator (index) to the element with the greatest value. But ...

getPos(riches,findGreatest(riches));

... this is exactly what we want.

Save intermediate values

int b = getPos(riches,findGreatest(riches));
std::cout << b << findGreatest(riches) << std::endl;
std::cout << riches[b] << std::endl;
riches[b] = 0;

You call your (expensive) findGreatest function twice. Don't. Also you don't stick to the output format specified in the problem statement.
Thus we can reduce to

std::vector::iterator wealthiest = std::max_element(std::begin(riches), std::end(riches));
std::cout << *wealthiest << std::endl;
*wealthiest = 0;

But isn't there a faster solution?

With the above, you always search to the entire vector of currently known persons to find the wealthiest of them. In the worst case, e.g. when all N persons enter, and then the king comes to see M people beheaded, you're basically searching M times through the whole vector, thus you have O(M * N).

To improve on that: Nothing states that the persons must stay in the order in which they entered the room. Whenever a new person enters the room, let it stand so that all persons in front of it are wealthier, and all persons behind it are less wealthy. When the king comes, behead the first (as it has no one in front, there's no wealthier person). Basically, keep the collection of citizens sorted according to their wealth.

There are multiple ways of doing so:

• Use not a vector but a sorted container, e.g. a std::priority_queue or (since there are no two citizens with the same wealth) a std::set.

• Keep a heap inside your vector: std::make_heap.

• Sort your vector whenever the king comes. (Though this only works good if sorting an already almost sorted sequence is fast)

Random improvements

• You know how many citizens there'll be. Reserve space for them beforehand.

StackExchange Code Review Q#143498, answer score: 11