UVA 11621 Small Factors Solution

Explain:

This problem is  very easy  to solve. I first preprocessed the number of samples C for i and j up to 32. To save some cycles I broke off the inner for loop if the value of 2^i*3^j was greater than 2^31. This preprocessing is an inexpensive operation as it is O(31^2) only. I then sorted the list, which is also inexpensive, and used the lower_bound function to determine the first value C >= m. 

Solution in C++:

///**********ALLAH IS ALMIGHTY************///
///AH Tonmoy
///Department of CSE,23rd batch

///Islamic University,Bangladesh  

#include<bits/stdc++.h>

using namespace std;

int i,j;

long n;

vector<long>v;

void remember()

{

    for(i=0; i<32; i++)

    {

        for(j=0; j<32; j++)

        {

            n=pow(2,i)*pow(3,j);

            if(n>pow(2,31))

                break;

            v.push_back(n);

        }

    }

}

int main()

{

    int m,pos;

    remember();

    sort(v.begin(),v.end());

    while(cin>>m)

    {

        if(m==0)

            break;

        else

            pos=lower_bound(v.begin(),v.end(),m)-v.begin();

        cout<<v[pos]<<endl;

    }

}