C++ ||| prefix and suffix sum
We have just done preprocessing to cal. foctors of 2 and 5 AND then \nmaintain a vector of vector of prefix sum and suffix sum to get all factos in O(1) time\n\
We have just done preprocessing to cal. foctors of 2 and 5 AND then \nmaintain a vector of vector of prefix sum and suffix sum to get all factos in O(1) time\n\n\n\tclass Solution {\n\tpublic:\n\t\tint maxTrailingZeros(vector<vector<int>>& grid) {\n\t\t\tint n = grid.size() , m = grid[0].size();\n\t\t\t// vector of pair of 2 and 5 then  down prefix, up prefix, left to right and vice versa\n\t\t\tvector<vector<pair<int,int>>>t_f(n, vector<pair<int,int>>(m,{0,0}));\n\t\t\tfor( int i=0 ; i<n ; i++){\n\t\t\t\tfor( int j=0 ; j<m ; j++){\n\t\t\t\t\tint t= grid[i][j];\n\t\t\t\t\tint two=0, five=0;\n\t\t\t\t\twhile(t%2==0){\n\t\t\t\t\t\tt /= 2;\n\t\t\t\t\t\ttwo++;\n\t\t\t\t\t}\n\t\t\t\t\twhile(t%5==0){\n\t\t\t\t\t\tt /= 5;\n\t\t\t\t\t\tfive++;\n\t\t\t\t\t}\n\t\t\t\t\tt_f[i][j]={two,five};\n\t\t\t\t}\n\t\t\t}\n\t\t\tvector<vector<pair<int,int>>>ttb, btt, ltr,rtl;\n\t\t\tttb=btt=ltr=rtl = t_f;\n\t\t\t// ttb  --> top to bottom prfix sum of two and fives;\n\t\t\tfor( int i=1 ; i<n ; i++){\n\t\t\t\tfor( int j=0 ; j<m; j++){\n\t\t\t\t\tttb[i][j].first += ttb[i-1][j].first;\n\t\t\t\t\tttb[i][j].second += ttb[i-1][j].second;\n\t\t\t\t}\n\t\t\t}\n\n\t\t\t// btt  -->  bottom to top  suffix sum of two and fives;\n\t\t\tfor( int i=n-2 ; i>=0 ; i--){\n\t\t\t\tfor( int j=0 ; j<m; j++){\n\t\t\t\t\tbtt[i][j].first += btt[i+1][j].first;\n\t\t\t\t\tbtt[i][j].second += btt[i+1][j].second;\n\t\t\t\t}\n\t\t\t} \n\n\t\t\t// ltr  --> left to right prfix sum of two and fives;\n\t\t\tfor( int i=0 ; i<n ; i++){\n\t\t\t\tfor( int j=1 ; j<m; j++){\n\t\t\t\t\tltr[i][j].first += ltr[i][j-1].first;\n\t\t\t\t\tltr[i][j].second += ltr[i][j-1].second;\n\t\t\t\t}\n\t\t\t} \n\n\t\t\t// rtl  --> right to left suffix sum of two and fives;\n\t\t\tfor( int i=0 ; i<n ; i++){\n\t\t\t\tfor( int j=m-2 ; j>=0; j--){\n\t\t\t\t\trtl[i][j].first += rtl[i][j+1].first;\n\t\t\t\t\trtl[i][j].second += rtl[i][j+1].second;\n\t\t\t\t}\n\t\t\t}\n\n\t\t\tint res =0;\n\n\t\t\t//    |   |\n\t\t\t//  __|   |__\n\t\t\t// for above shape\n\t\t\tfor( int i=0 ; i<n ; i++){\n\t\t\t\tfor( int j=0 ; j<m ; j++){\n\t\t\t\t\tint for_2 = ttb[i][j]. first;\n\t\t\t\t\tint for_5 = ttb[i][j].second;\n\n\t\t\t\t\tint left_2= (j>0)? ltr[i][j-1].first : 0;      // left to right;\n\t\t\t\t\tint left_5= (j>0)? ltr[i][j-1].second : 0;\n\n\t\t\t\t\tint right_2= (j<m-1)? rtl[i][j+1].first : 0;      // right to left;\n\t\t\t\t\tint right_5= (j<m-1)? rtl[i][j+1].second : 0;\n\n\t\t\t\t\tint mn1 = min(for_2+left_2  , for_5+ left_5);\n\t\t\t\t\tint mn2 = min(for_2+right_2 , for_5 + right_5);\n\n\t\t\t\t\tres = max( res, max(mn1,mn2));\n\t\t\t\t}\n\t\t\t}\n\n\t\t\t//  ___   ___\n\t\t\t//    |   |\n\t\t\t//    |   |\n\t\t\t// for above shape\n\t\t\tfor( int i=n-1 ; i>=0 ; i--){\n\t\t\t\tfor( int j=0 ; j<m ; j++){\n\t\t\t\t\tint for_2 = btt[i][j]. first;\n\t\t\t\t\tint for_5 = btt[i][j].second;\n\n\t\t\t\t\tint left_2= (j>0)? ltr[i][j-1].first : 0;      // left to right;\n\t\t\t\t\tint left_5= (j>0)? ltr[i][j-1].second : 0;\n\n\t\t\t\t\tint right_2= (j<m-1)? rtl[i][j+1].first : 0;      // right to left;\n\t\t\t\t\tint right_5= (j<m-1)? rtl[i][j+1].second : 0;\n\n\t\t\t\t\tint mn1 = min(for_2+left_2  , for_5+ left_5);\n\t\t\t\t\tint mn2 = min(for_2+right_2 , for_5 + right_5);\n\n\t\t\t\t\tres = max( res, max(mn1,mn2));\n\t\t\t\t}\n\t\t\t}\n\n\t\t\treturn res;\n\n\t\t}\n\t};
['Suffix Array', 'Prefix Sum']