Concepts Used

Strings

Difficulty Level

Hard

Problem Statement (Simplified):

Find the maximum answer by evaluating the given string and putting a bracket anywhere in the string.

See original problem statement here

Test Case

    Input:
    2
    3+4*5+6
    3*5+6*7+2

    Output:
    47
    233

    Explanation:
    Case-1:
    We can put brackets at last operator making equation as 3+4*(5+6) => 3+4*11 => 47.

    Case-2:
    We can put bracket at 2nd operator making equation as 3*(5+6)*7+2 => 3*11*7+2 => 33*7+2 => 231+2 => 233.

Solving Approach :

Bruteforce Approach:

1) We can place brackets at all possible positions and check the value of all possible cases and then we can find the maximum value out of them, thus we print the maximum value.
2) Evaluating string of size L takes O(N) time, where checking all possibilities take O(M) times where M is the number of operators i.e. * or + in whole string. So this approach takes total O(M\times N) time complexity. The above approach takes a long time to evaluate strings of larger sizes. So we search for an optimized approach that can solve this problem in a shorter time by referring the best sites to learn programming languages.

Efficient Approach:

1) An easy analysis shows that the brackets must be placed adjacent to * sign since they won’t have any effect next to a + sign.
2) We need to store the indexes of all the * in the string and iterate over all possible pairs. One thing to keep in mind is the maximum case may be one in which the brackets start at the 0th index or the one in which it ends at the last index.

Example

  • Lets assume given equation is 3*5+6*7+2.
  • As discussed in Step-1, the equation will be maximized if we put brackets adjacent to a multiplication operator. So we get two possibilities here, that is, 3*(5+6)*7+2 and 3*5+6*(7+2).
  • On evaluating above equations, equations yield 233 and 69 respectively, where the first equation yields the maximum value. So it is our final answer.

Solutions

#include <stdio.h>
long long a[5002],b[5002],c[5002],c1[5002];
long long fun(long long l,long long r)
{
    if(l==r)
        return a[l];
    long long sum=0,i;
    for(i=l;i<=r;i++)
        b[i]=a[i];
    for(i=l;i<r;i++)
    {
        if(c[i]==1)
        {
            sum+=b[i];
        }
        else
        {
            b[i+1]=b[i]*b[i+1];
        }
    }
    sum+=b[r];
    return sum;
}

long long fun2(long long l,long long r)
{
    if(l==r)
        return b[l];
    long long sum=0,i;
  for(i=l;i<r;i++)
    {
        if(c1[i]==1)
        {
            sum+=b[i];
        }
        else
        {
            b[i+1]=b[i]*b[i+1];
        }
    }
    sum+=b[r];
    return sum;
}


int main()
{

  int test;
  scanf("%d",&test);
  while(test--){
      char str[5003];
      scanf ("%s",&str);
      long long i=0,j,mul[16],ctr=0,len=0,sum=0,max=-1,k,k1;
      mul[0]=-1;
      ctr++;
      while (str[i]!='\0')
      {
          if(str[i]=='+')
              c[i/2]=1;
          else if (str[i]=='*')
          {
              mul[ctr]=i/2;
              ctr++;
              c[i/2]=2;
          }
          else
          {
              a[i/2]=str[i]-48;
              sum+=a[i/2];
          }
          i++;
          len++;
      }
      mul[ctr]=len/2;
      ctr++;
      for(i=0;i<=len/2;i++)
      {
      }
      if(ctr==0)
      {
          printf ("%lld\n",sum);
          return 0;
      }
      for(i=0;i<ctr;i++)
      {
          for(j=i+1;j<ctr;j++)
          {
              long long temp2=fun(mul[i]+1,mul[j]);
              k=0;
              if(mul[i]!=-1)
              {
                  for(k=0;k<mul[i]+1;k++)
                  {
                    b[k]=a[k];
                      c1[k]=c[k];
                  }
              }
              b[k]=temp2;
              c1[k]=2;
              k++;
              for(k1=mul[j]+1;k1<=len/2;k1++)
              {
                  b[k]=a[k1];
                  c1[k]=c[k1];
                  k++;
              }
              long long tt=fun2(0,k-1);
              if(tt>max)  
                  max=tt;
          }
      }
      printf ("%lld\n",max);
  }return 0;
}


#include <stdio.h>
long long a[5002],b[5002],c[5002],c1[5002];
long long fun(long long l,long long r)
{
    if(l==r)
        return a[l];
    long long sum=0,i;
    for(i=l;i<=r;i++)
        b[i]=a[i];
    for(i=l;i<r;i++)
    {
        if(c[i]==1)
        {
            sum+=b[i];
        }
        else
        {
            b[i+1]=b[i]*b[i+1];
        }
    }
    sum+=b[r];
    return sum;
}

long long fun2(long long l,long long r)
{
    if(l==r)
        return b[l];
    long long sum=0,i;
  for(i=l;i<r;i++)
    {
        if(c1[i]==1)
        {
            sum+=b[i];
        }
        else
        {
            b[i+1]=b[i]*b[i+1];
        }
    }
    sum+=b[r];
    return sum;
}


int main()
{

  int test;
  scanf("%d",&test);
  while(test--){
      char str[5003];
      scanf ("%s",&str);
      long long i=0,j,mul[16],ctr=0,len=0,sum=0,max=-1,k,k1;
      mul[0]=-1;
      ctr++;
      while (str[i]!='\0')
      {
          if(str[i]=='+')
              c[i/2]=1;
          else if (str[i]=='*')
          {
              mul[ctr]=i/2;
              ctr++;
              c[i/2]=2;
          }
          else
          {
              a[i/2]=str[i]-48;
              sum+=a[i/2];
          }
          i++;
          len++;
      }
      mul[ctr]=len/2;
      ctr++;
      for(i=0;i<=len/2;i++)
      {
      }
      if(ctr==0)
      {
          printf ("%lld\n",sum);
          return 0;
      }
      for(i=0;i<ctr;i++)
      {
          for(j=i+1;j<ctr;j++)
          {
              long long temp2=fun(mul[i]+1,mul[j]);
              k=0;
              if(mul[i]!=-1)
              {
                  for(k=0;k<mul[i]+1;k++)
                  {
                    b[k]=a[k];
                      c1[k]=c[k];
                  }
              }
              b[k]=temp2;
              c1[k]=2;
              k++;
              for(k1=mul[j]+1;k1<=len/2;k1++)
              {
                  b[k]=a[k1];
                  c1[k]=c[k1];
                  k++;
              }
              long long tt=fun2(0,k-1);
              if(tt>max)  
                  max=tt;
          }
      }
      printf ("%lld\n",max);
  }return 0;
}



import java.util.*;
import java.io.*;
import java.math.*;

class Main {
    static long a[] = new long[6000];
    static long b[] = new long[6000];
    static long xx,yy,x,y,k,ans;
    static int i,j,m,n;
    static String s,t;
    static void solve(int l, int r)
    {
        x = 0; y = a[l];
        for (int i = l; i < r; i++)
            if (b[i] == 1)
            {
               x += y; y = a[i+1];
            }
            else
                y *= a[i+1];
    }

    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);

       int test = sc.nextInt();
       while(test!=0){

          s = sc.next();
          t = "1*";
          t = t.concat(s);
          t = t.concat("*1");
          s = t;
            n = s.length();
            m = n/2;
            for (i = 0; i < n; i+=2)
                a[i/2] = (int)s.charAt(i) - (int)'0';
            for (i = 1; i < n; i+=2)
                if (s.charAt(i) == '+')
                   b[i/2] = 1;
                else
                    b[i/2] = 2;
            long max1 = 0;
            for (i = 0; i < m; i++)
                for (j = i+1; j < m; j++)
                if (b[i] == 2 && b[j] == 2)
                {
                 solve(0,i);
                 xx = x; yy = y;
                 solve(i+1,j);
                 yy *= x + y;
                 long xxx = a[j];
                 a[j] = yy;
                 solve(j,m);
                 max1 = Math.max(max1, xx+x+y);
                 a[j] = xxx;
                }
            System.out.println(max1);
          test--;
      }
    }
}

Space complexity of this approach would be O(N).

Previous post Aman String
Next post Anagram or Not (IMAGE NOT ADDED)

Leave a Reply

Your email address will not be published. Required fields are marked *