Question

The game starts when I give you some Teddy bears. You can then give back some bears, but you must follow these rules (where n is the number of bears that you have):

1. If n is even, then you *may* give back exactly n/2 bears.
2. If n is divisible by 3 or 4, then you *may* multiply the last two digits of n and give back this many bears. (By the way, the last digit of n is n%10, and the next-to-last digit is ((n%100)/10).
3. If n is divisible by 5, then you *may* give back exactly 42 bears.

The goal of the game is to end up with EXACTLY 42 bears.

For example, suppose that you start with 250 bears. Then you could make these moves:

• --Start with 250 bears.
• --Since 250 is divisible by 5, you may return 42 of the bears, leaving you with 208 bears.
• --Since 208 is even, you may return half of the bears, leaving you with 104 bears.
• --Since 104 is even, you may return half of the bears, leaving you with 52 bears.
• --Since 52 is divisible by 4, you may multiply the last two digits (resulting in 10) and return these 10 bears. This leaves you with 42 bears.
• --You have reached the goal!

For each integer 50, 51, 52, ..., 500, tell me if 42 can be reached and if so, what are the steps. Notice I use a stack to reverse the print out, so it is more readable. For example, the output of the last few cases are shown here:

Starting number: 496 n=496, return 248. Now n=248. n=248, return 32. Now n=216. n=216, return 6. Now n=210. n=210, return 42. Now n=168. n=168, return 84. Now n=84. n=84, return 42. Now n=42. Starting number: 497 No solution Starting number:498 n=498, return 249. Now n=249. n=249, return 36. Now n=213. n=213, return 3. Now n=210. n=210, return 42. Now n=168. n=168, return 84. Now n=84. n=84, return 42. Now n=42. Starting number:499 No solution Starting number: 500 n=500, return 250. Now n=250. n=250, return 42. Now n=208. n=208, return 104. Now n=104. n=104, return 52. Now n=52. n=52, return 10. Now n=42.

import java.util.*;

public class Hw18_1 {

public static void main(String[] args) {

Stack<String> stack = new Stack<>();

for (int i = 50; i <= 500; i++) {

System.out.println("\nStarting number:" + i);

if (bears(stack, i))

while (!stack.isEmpty())

System.out.println(stack.pop());

else

System.out.println("No solution");

}

}

static boolean bears(Stack<String> stack, int n) {

int product;

if (n == 42) {

return true;

} else if (n < 42) {

// your work

} else if ((n % 2 == 0) && bears(stack, n / 2)) {

// your work

} else if ((n % 5 == 0) && bears(stack, n - 42)) {

// your work

} else {

product = ((n % 100) / 10) * (n % 10);

// your work

}

return false;

}

}

Answer 1

Code:

import java.util.*;

public class Hw18_1 {
public static void main(String[] args) {
// stack to store the values that are returned each time
Stack<String> stack = new Stack<>();
// for each value of i call the bears function and print output
for (int i = 50; i <= 500; i++) {
System.out.println("\nStarting number:" + i);
int curr=i;
// if bears function returned true then print solution
if (bears(stack, i))
while (!stack.isEmpty()){
String val=stack.pop();
int value=Integer.parseInt(val);
System.out.println("n="+curr+", return "+value+". Now n="+(curr-value)+".");
curr-=value;
}
// else there is no solution
else
System.out.println("No solution");
}
}
static boolean bears(Stack<String> stack, int n) {
int product;
// base case if n==42 then return true
if (n == 42) {
return true;
}
// if n<42 then it is never possible
if (n < 42) {
return false;
}
// if divisible by 2 , then return n/2
if ((n % 2 == 0) && bears(stack, n / 2)) {
stack.push(Integer.toString(n/2));
return true;
}
// divisible by 5 ,then return 42
if ((n % 5 == 0) && bears(stack, n - 42)) {
stack.push(Integer.toString(42));
return true;
}
// if divisible by 3 or 4 , return product of last 2 digit
if((n % 3 == 0) || (n % 4 == 0)){
product = ((n % 100) / 10) * (n % 10);
// if product is 0 then we need to return othewise
// the function would get stuck in infinite loop
if(product==0) return false;
if(bears(stack,n-product)){
stack.push(Integer.toString(product));
return true;
}
}
// no soultion possible so return false
return false;
}
}

============

Note:

I have modified the given template as the function bears template wasn't correct. Further to match the given sample output I have modified the main too.

============

Sample output along with code screenshot :

1 import java.util.*; n=168, return 84. Now n=84. n=84, return 42. Now n=42. Starting number:491 No solution 3- public class Hw 18_1 { public static void main(String[] args) { // stack to store the values that are returned each time Stack<String> stack = new Stacko O; // for each value of i call the bears function and print output for (int i = 50; i <= 500; i++) { System.out.println("\nStarting number:" + i); int curr=i; // if bears function returned true then print solution if (bears (stack, i)) while (!stack.isEmpty(){ String val=stack.pop(); int value=Integer.parseInt(val); System.out.println("n="+curr+", return "+value+". Now, n="+(curr-value)+"."); curr-=value; Starting number:492 n=492, return 18. Now n=474. n=474, return 237. Now n=237. n=237, return 21. Now n=216. n=216, return 6. Now n=210. n=210, return 42. Now n=168. n=168, return 84. Now n=84. n=84, return 42. Now n=42. Starting number:493 No solution // else there is no solution else System.out.println("No solution"); Starting number: 494 No solution static boolean bears (Stack<String> stack, int n) { int product; // base case if n==42 then return true if (n == 42) { return true; Starting number:495 n=495, return 42. Now n=453. n=453, return 15. Now n=438. n=438, return 219. Now n=219. n=219, return 9. Now n=210. n=210, return 42. Now n=168. n=168, return 84. Now n=84. n=84, return 42. Now n=42. if 42 then it is never possible

return true; // if n<42 then it is never possible if (n < 42) { return false; Starting number: 496 n=496, return 248. Now n=248. n=248, return 32. Now n=216. n=216, return 6. Now n=210. n=210, return 42. Now n=168. n=168, return 84. Now n=84. n=84, return 42. Now n=42. // if divisible by 2 , then return n/2 if ((n % 2 == ) && bears (stack, n / 2)) { stack.push(Integer.toString(n/2)); return true; Starting number:497 No solution // divisible by 5 , then return 42 if ((n % 5 == ©) && bears (stack, n - 42)) { stack.push(Integer.toString(42)); return true; Starting number:498 n=498, return 249. Now n=249. n=249, return 36. Now n=213. n=213, return 3. Now n=210. n=210, return 42. Now n=168. n=168, return 84. Now n=84. n=84, return 42. Now n=42. // if divisible by 3 or 4 , return product of Last 2 digit if((n % 3 == 0) || (n % 4 == 0)){ product = ((n % 100) / 10) * (n % 10); // if product is @ then we need to return othewise // the function would get stuck in infinite Loop if (product==0) return false; if(bears (stack,n-product)) { stack.push(Integer.toString(product)) return true; Starting number:499 No solution // no soultion possible so return false return false; Starting number:500 n=500, return 250. Now n=250. n=250, return 42. Now n=208. n=208, return 104. Now n=104. n=104, return 52. Now n=52. n=52, return 10. Now n=42. 58 ]

============

Explanation:

In bears function since there was no hard bound rule that if number is divisible by 2 then we return n/2. Note that it was one of the possiblities to get the solution.

So instead of stating conditions in if -elseif -else pattern only if conditions are used. And once the solution is found we return from the function immediately.

Here see line 49 => Let's say n = 108 then product would be 0, so again call for 108 and so on.. That's why this condition is required.

Comments have been added for your understanding.

===========

Please upvote

For any doubts comment.