Alex
BAN USERIf it is about unsigned integers then a possible approach is to use counting sort, which would use comparing of bits. Thus, if you create a 32x2 (64x2) table count[bit_position][0/1] and fill it with number of numbers in the file with 0/1 on the bit_position and then you can use this array to perform a sort.
- Alex November 29, 2013int find_max_number_recursive(int current, int rest_numbers, const int max_value, int last)
{
if (rest_numbers == 0)
return current;
int result = current;
for (int i = last; i < 10; ++i)
if (current * i <= max_value)
{
result = max(result, find_max_number_recursive(current * i, rest_numbers - 1, max_value, i));
}
return result;
}
int find_max_number(int max_number_of_multiplications, int max_result_length)
{
if (max_result_length < 2 || max_number_of_multiplications < 2)
return -1;
if (max_result_length > 8 || max_number_of_multiplications > 30)
return -1;
int max_value = (int)(pow(10, max_result_length) - 1);
return find_max_number_recursive(1, max_number_of_multiplications + 1, max_value, 2);
}
int main()
{
double t = clock();
cout << find_max_number(30, 8) << endl;
cout << (clock() - t) / CLOCKS_PER_SEC;
return 0;
}
bool check_balance(CharStream *in, stack < char > *brackets)
{
if (in->hasNext)
{
char current = in->next();
if (current == ‘(‘ || current == ‘[‘)
{
brackets->push(c);
return check_balance(in, brackets);
}
else
{
if (brackets->empty())
return false;
char last = brackets->top();
if (last == ‘[‘ && current == ‘)’)
return false;
if (last == ‘(‘ && current == ‘]’)
return false;
return check_balance(in, brackets);
}
}
else
return brackets->empty();
}
bool isValid(const CharStream &in)
{
std::stack brackets;
return check_balance(CharStream &in, stack < char > &brakets);
}
time complexity: O(x * log x)
memory complexity: O(x)
- Alex December 03, 2013