Every value in a program has a type, and the type decides three things: what the value can hold, how much memory it takes, and what the operators do to it. Most beginner bugs in these problems are type bugs that look like logic bugs.
Whole numbers, and how big they get#
int count = 0; // about -2.1 billion to 2.1 billion
long long total = 0; // about -9.2 quintillion to 9.2 quintillion
int count = 0; // about -2.1 billion to 2.1 billion
long long total = 0; // about -9.2 quintillion to 9.2 quintillion
int count = 0; // about -2.1 billion to 2.1 billion
long total = 0; // about -9.2 quintillion to 9.2 quintillion
count = 0 # Python integers grow as large as they need to
total = 0
An int is 32 bits, so it tops out at 2147483647. Go past that and C, C++ and Java do not complain. The value wraps around to a large negative number and your program carries on, confidently wrong. This is called overflow.
The rule for these problems: if the constraints allow values near a billion, or you are adding up many values, or multiplying two of them, use the 64 bit type. 100000 numbers each up to 10^9 sum to 10^14, far past what an int holds.
Python does not have this problem, which is one reason people like it for practice. It is also why a Python solution can pass where the same logic in Java fails.
Dividing whole numbers#
In C, C++ and Java, dividing two integers throws the fraction away:
int a = 7 / 2; // 3
double b = 7 / 2; // still 3.0: the division happened between integers
double c = 7.0 / 2; // 3.5
int a = 7 / 2; // 3
double b = 7 / 2; // still 3.0: the division happened between integers
double c = 7.0 / 2; // 3.5
int a = 7 / 2; // 3
double b = 7 / 2; // still 3.0: the division happened between integers
double c = 7.0 / 2; // 3.5
a = 7 // 2 # 3: two slashes for whole number division
b = 7 / 2 # 3.5: one slash always gives a float
The second line in the C family is the classic trap. The type on the left does not change how the right side is worked out.
Remainder#
% gives what is left after dividing: 7 % 2 is 1, 10 % 5 is 0. It is how you test for even numbers (n % 2 == 0) and how you take the last digit of a number (n % 10).
With negative numbers the languages disagree. -7 % 2 is -1 in C, C++ and Java, and 1 in Python. If a problem allows negatives, test that case deliberately.
Numbers with a fractional part#
double in C, C++ and Java, float in Python. Both hold about 15 significant digits, and both are approximate: 0.1 + 0.2 is 0.30000000000000004 in all four languages.
So never compare two computed doubles with ==. Compare the difference with a small tolerance, such as fabs(a - b) < 1e-9. Better still, for these problems, stay in whole numbers wherever you can.
True and false#
bool in C (from stdbool.h), C++ and Python, boolean in Java. Comparisons produce them: x > 0, a == b, s.isEmpty(). Combine them with &&, ||, ! in the C family, or and, or, not in Python.
Text#
Text is where the four languages differ most.
char* s = "hello";
int n = strlen(s); // 5, found by walking to the '\0' at the end
char first = s[0]; // 'h'
string s = "hello";
int n = s.size(); // 5
char first = s[0]; // 'h'
s += '!'; // strings can be changed in place
String s = "hello";
int n = s.length(); // 5
char first = s.charAt(0); // 'h'
// Strings cannot be changed. Build new text with a StringBuilder.
StringBuilder b = new StringBuilder(s);
b.append('!');
s = "hello"
n = len(s) # 5
first = s[0] # 'h', itself a string of length 1
# Strings cannot be changed. Collect pieces in a list and join them.
parts = [s, "!"]
result = "".join(parts)
A trap in Java and Python: adding to a string in a loop, s = s + c, copies the whole string every time. For a string of n characters that is n copies of growing length, which is slow. Use StringBuilder in Java and "".join(...) in Python.
A trap in C: a char* does not know its length. strlen walks to the terminating '\0' each time you call it, so calling it inside a loop condition makes the loop quadratic. Call it once and keep the number.
Characters are numbers#
In C, C++ and Java a char is a small number. That makes a lot of string problems easy:
c - '0'turns the digit character'7'into the number7c - 'a'turns a lowercase letter into0to25, handy as an index into an array of 26 counters
In Python, ord(c) gives the number and chr(n) goes back, so ord(c) - ord('a') does the same job.
Try it#
Palindrome number and Count digits are both about whole numbers, division and remainder, and both have one case that catches people out. See if you can find it before the hidden tests do.