Problem
Can Tile
Small tile is 1 unit, Big tile is 5 units, given number of small tiles and big tiles, check whether we can tile the target.
follow up question:
If the multiply and divide are not allowed, can you code this recursively?
Solution
This is an open question, the big tiles' shape and area's shape haven't been given. We have to make assumption they are both square in order to have a solvable problem. Once that assumption is made, the model will decide how hard this problem is. If the function deal with small, big, width and height, we got a harder problem. Have to shrink down the width and height in the loop. If we only deal with area, the problem can be solved in one line:
small >= (target / 5 > big ? target - big * 5 : target % 5);
With the constraint in the follow up question, we have to think out of box. The recursive code has exit condition at area == 0, and area < 0. When area >0, we need to do the recursion.
public class CanTile {
public static boolean canTile(int bTile, int sTile, int area) {
if(area == 0) return true;
if(area < 0) return false;
if(bTile == 0 && sTile == 0) return false;
return ((sTile > 0 && canTile(bTile, sTile - 1, area - 1)) || (bTile > 0 && canTile(bTile - 1, sTile, area - 5)));
}
public static boolean canTile2(int small, int big, int area) {
return small >= (target / 5 > big ? target - big * 5 : target % 5);
}
public static void main(String...args) {
System.out.println(canTile(100, 20, 20*20)); //true
System.out.println(canTile(100, 3, 24*21)); //false
System.out.println(canTile(100, 0, 20*21)); //true
System.out.println(canTile(100, 4, 4*6)); //true
System.out.println(canTile(100, 3, 4*6)); //false
}
}
public static boolean canTile(int bTile, int sTile, int area) {
if(area == 0) return true;
if(area < 0) return false;
if(bTile == 0 && sTile == 0) return false;
return ((sTile > 0 && canTile(bTile, sTile - 1, area - 1)) || (bTile > 0 && canTile(bTile - 1, sTile, area - 5)));
}
public static boolean canTile2(int small, int big, int area) {
return small >= (target / 5 > big ? target - big * 5 : target % 5);
}
public static void main(String...args) {
System.out.println(canTile(100, 20, 20*20)); //true
System.out.println(canTile(100, 3, 24*21)); //false
System.out.println(canTile(100, 0, 20*21)); //true
System.out.println(canTile(100, 4, 4*6)); //true
System.out.println(canTile(100, 3, 4*6)); //false
}
}
The time cost for non-recursive version is O(1).
The recursive version has to try the small tile before apply the big tile, the time cost is O(area). The space cost decided by the size of the calling stack, which is no bigger than area/5 + small, in the worst case, there is no big title, the stack depth is O(area)
The recursive version has to try the small tile before apply the big tile, the time cost is O(area). The space cost decided by the size of the calling stack, which is no bigger than area/5 + small, in the worst case, there is no big title, the stack depth is O(area)
