Write a C++ method removeShorterOfPairs that has an ArrayList of strings as a pa

Question

Write a C++ method removeShorterOfPairs that has an ArrayList of strings as a parameter. For every consecutive pair of strings the methods removes the shorter of the two from the arraylist. If there is a tie (strings with the same length), it removes the second of the pair. If there are an odd number of strings in the list, the final value remains in the list. You may not create new ArrayLists or arrays. Determine the complexity.

For example:
revoveShorterOfPairs: {"Let's", "try", "it", "over"} prints {"Let's", "over"}
revoveShorterOfPairs: {"Keep", "left", "side", "of", "ties"} prints {"Keep", "side", "ties"}

Explanation / Answer

Code:

#include <bits/stdc++.h>
using namespace std;

void removeShorterOfPairs(vector<string> * vec){
   int i=0;
   while(i<vec->size()){
       if(i+1==vec->size()){
           i++;
       }
       else{
           int x=(*vec)[i].length();
           int y=(*vec)[i+1].length();
           if(x<y){
               vec->erase(vec->begin()+i);
           }
           else{
               vec->erase(vec->begin()+i+1);
           }
           i++;
       }
   }

}

int main(){
   vector<string> vec;
   vec.push_back("Keep");
   vec.push_back("left");
   vec.push_back( "side");
   vec.push_back("of");
   vec.push_back("ties");
   removeShorterOfPairs(&vec);

   for(int i=0;i<vec.size();i++){
       cout<<vec[i]<<endl;
   }
   return 0;
}

Time complexity:In worst case each removal from the arraylist take O(n) time So the overall worst case time complexity becomes O(n^2).

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.