java/07-recursion/BinarySum Source

Viewing java/07-recursion/BinarySum by daveagp@gmail.com. You have unsaved changes. Log in above to create, edit, preview and publish Websheets.

Property Value

Description
html markup
shown to student

Write a recursive static method <code>binaryDigitSum(n)</code> that
takes a nonnegative integer <code>n</code> and
<ul>
<li>if <code>n</code> is zero, returns zero</li>
<li>if <code>n</code> is odd, returns one plus <code>binaryDigitSum(n/2)</code>
</li>
<li>if <code>n</code> is even and not zero, returns <code>binaryDigitSum(n/2)
</code></li>

Epilogue
html markup
shown when solved

remove
Public permissions remove
Remarks
Comments, history, license, etc.

remove
Engine
Choices
json list of string, bool pairs
e.g. [["good", true], ["bad", false]]

Correct answer
Template / Reference solution

// sum of the binary digits of n
\[
public static int binaryDigitSum(int n) {
if (n==0) return 0;

if (n%2 == 1) // is n odd?
return 1 + binaryDigitSum(n/2);

// n is even and positive
return binaryDigitSum(n/2);
}
]\

public static void main(String[] args) {
StdOut.println(binaryDigitSum(5)); // should be 2, 5 is 101
StdOut.println(binaryDigitSum(25)); // should be 3, 25 is 11001
}

Template / Reference solution

Java test suite
See manual

testMain();
test("binaryDigitSum", 0);
test("binaryDigitSum", 1);
test("binaryDigitSum", 2);
test("binaryDigitSum", 3);
test("binaryDigitSum", 4);
test("binaryDigitSum", 126);
test("binaryDigitSum", 255);
test("binaryDigitSum", 256);

C++ test suite
json list of stdin/args tests
e.g. [{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}]
to just run once with no input use [{}]

C++ test suite
See manual

Forbidden substrings
json list of strings
e.g. ["for","while"]

remove
Solution visibility remove
Java imports
json list of importables
e.g. ["java.util.*"]

remove
Override Java classname
else defaults to
websheet name
remove
Dependent on other websheets?
json list of websheet names in this folder
e.g. ["DataStructure"]

remove
Is example?
i.e., just a demo
remove
Add compiler flag(s)
json list of flags
e.g. ["-Wno-unused-variable"]

remove
Remove default compiler flag(s)
json list of flags
see default_cppflags
e.g. ["-Wno-write-strings"]

remove

Property	Value
Description html markup shown to student	Write a recursive static method <code>binaryDigitSum(n)</code> that takes a nonnegative integer <code>n</code> and <ul> <li>if <code>n</code> is zero, returns zero</li> <li>if <code>n</code> is odd, returns one plus <code>binaryDigitSum(n/2)</code> </li> <li>if <code>n</code> is even and not zero, returns <code>binaryDigitSum(n/2) </code></li>
Epilogue html markup shown when solved	remove
Public permissions	remove
Remarks Comments, history, license, etc.	remove
Engine
Choices json list of string, bool pairs e.g. `[["good", true], ["bad", false]]`
Correct answer
Template / Reference solution	// sum of the binary digits of n \[ public static int binaryDigitSum(int n) { if (n==0) return 0; if (n%2 == 1) // is n odd? return 1 + binaryDigitSum(n/2); // n is even and positive return binaryDigitSum(n/2); } ]\ public static void main(String[] args) { StdOut.println(binaryDigitSum(5)); // should be 2, 5 is 101 StdOut.println(binaryDigitSum(25)); // should be 3, 25 is 11001 }
Template / Reference solution
Java test suite See manual	testMain(); test("binaryDigitSum", 0); test("binaryDigitSum", 1); test("binaryDigitSum", 2); test("binaryDigitSum", 3); test("binaryDigitSum", 4); test("binaryDigitSum", 126); test("binaryDigitSum", 255); test("binaryDigitSum", 256);
C++ test suite json list of stdin/args tests e.g. `[{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}]` to just run once with no input use `[{}]`
C++ test suite See manual
Forbidden substrings json list of strings e.g. `["for","while"]`	remove
Solution visibility	remove
Java imports json list of importables e.g. `["java.util.*"]`	remove
Override Java classname else defaults to websheet name	remove
Dependent on other websheets? json list of websheet names in this folder e.g. `["DataStructure"]`	remove
Is example? i.e., just a demo	remove
Add compiler flag(s) json list of flags e.g. `["-Wno-unused-variable"]`	remove
Remove default compiler flag(s) json list of flags see default_cppflags e.g. `["-Wno-write-strings"]`	remove

Optional properties:

Note: problems are open-source by default (see 'Public permissions'). Assumed license for open problems is Creative Commons 4.0 Attribution-ShareAlike unless specified in 'Remarks'.