wHack23
BAN USERFor any value that can be represented using more than 4 3R coins, you can alternatively represent it with every 5 3R coins being replaced with 3 5R coins. Therefore any value that can be represented with any number of both 3R and 5R coins can be represented using only 4 or less 3R coins. If we consider this the canonocal representation of the value, the portion of the value in this canonical representation that can be represented by 3R coins can only be 0, 3, 6, 9, or 12. Also the remaining portion of the value must be a multiple of 5 as it will be made up entirely of 5R coins. So for any value which can be represented using 3R and 5R coins the value minus 0, 3, 6, 9, or 12 must be a multiple of 5.
boolean check(int val) {
if (val < 0)
return false;
for (int i = 0, i < 15, i+=3)
if (i <= val && ((val - i)%5)==0)
return true;
return false;
}
Or for the simplest solution.
boolean check(int val) {
if (val < 0 || val == 1 || val == 2 || val == 4 || val == 7)
return false;
return true;
}
So clearly this is a reference to pancake sorting, so it can be solved trivialy with only 2n-3 reversals and even fewer with non-trivial algorithms, the problem with this approach is the work involved in searching for the max value of the array in order to figure out what index to flip at is still O(n^2). However that is not good for a sort algorithm. The task can be accomplished in O(n log n) by implementing block sort using only reverse operations.
See Wikipedia for a description of the block sort algorithm. The important information is it can be implemented as an inplace sort with O(n log n). The algorithm is complicated enough so writing code for it here would be a little ridiculous. Anyway all of the required operations to implement it can be expressed as functions using only the reverse function, so you should be able to maintain the O(n log n) time complexity. As an example here is a swap function.
- wHack23 February 08, 2015