Question

Problem 1: ALGORITHM COMPLEXITY:Write an algorithm (pseudocode but not a program) that takes a positive numberias an input, where i=a1a2...an,n>=3(numberwith 3 or more digits, every digit can have the value between 0 and 9–both inclusive). The algorithm should find the largest number jsuch that j=b1..bm, 1<=m<=n(numberwith m digits),andevery bk<=bk+1where1<=k<m and bk,bk+1ε{a1, a2, an}.Also, perform the computational complexity (time complexity)analysis of your algorithm and write the algorithm complexity in Big-Oh notation.

Examples:Input: 23720, Output: 237Input: 9871, Output: 9Input: 1789, Output:1789Input: 2372891, Output: 289

Answer 1

Algorithm:

• take number input, n as string.
• initialize two variables max_num = 0, and curr_num = 0
• start iterating through the string from left.
• if number[i] > number[i-1] then curr_num = curr_num*10 + (number[i]-'0')
• else curr_num = number[i]-'0'
• update max_num at each step using max_num = max(max_num,curr_num)
• return max_num

Code:

#include <iostream>
using namespace std;

int main() {
   string num;
   cin>>num;
   int max_num = 0,curr_num = 0;
   for(int i=0;i<num.size();i++){
   if(i>0&&num[i]-'0'>num[i-1]-'0'){
   curr_num = curr_num*10 + (num[i]-'0');
   }
   else{
   curr_num = (num[i]-'0');
   }
   max_num = max(max_num,curr_num);
   }
   cout<<max_num<<'\n';
   return 0;
}

Code Screenshot: