These are the notes for C++ Coding Questions, episode 2, placement practice for people who finished the SyntaxPilot C++ course. Number questions: the sum of digits, reversing a number (and the overflow nobody warns you about), and the palindrome number, the maths way and the string way.
Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.
Every program was compiled with g++ -Wall -O2 -std=c++17 main.cpp -o main (g++ 13.3, Linux x86-64, 32-bit int, 64-bit long long), the SyntaxPilot compiler's C++ command with warnings on, and every output below is real. The compiler stops a program after 8 seconds.
Real-life picture: a bank token slip
With the slip 4721 |
In C++ |
|---|---|
read only the last digit: 1 |
n % 10, the remainder after dividing by 10 |
cover the last digit with your thumb: 472 |
n / 10, integer division drops the remainder |
copy it backwards on a new slip: 1, 12, 127, 1274 |
rev = rev * 10 + d: shift the old digits left, add the new one at the end |
The digit loop
while (n != 0) {
int d = n % 10; // read the last digit
// ...use d...
n /= 10; // remove it
}
For 4721, d is 1, 2, 7, 4: right to left, one turn per digit. (If n can be 0 and 0 must count as one digit, use a do { } while (n != 0); loop instead, which always runs at least once.)
Q1: Sum of digits
Problem. Read an integer and print the sum of its digits. The minus sign is not a digit.
| Input | Output |
|---|---|
| 1234 | 10 |
| -123 | 6 |
| 0 | 0 |
| -2147483648 | 47 |
The obvious attempt: while (n > 0)
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int sum = 0;
while (n > 0) {
sum += n % 10;
n /= 10;
}
cout << "sum of digits: " << sum << "\n";
return 0;
}
Input 1234:
sum of digits: 10
Input -123:
sum of digits: 0
Why: for -123, n > 0 is false at once, the loop never runs, and sum stays 0.
The fix: drop the sign first. But an int goes from -2,147,483,648 to 2,147,483,647: there is one more negative value, so -(-2147483648) does not fit in an int. That is signed overflow, which is undefined behaviour (UB): the C++ standard promises nothing about what happens. So read n as a long long (at least 64 bits, up to about 9.2 × 10¹⁸).
The fix
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n;
if (n < 0) n = -n;
int sum = 0;
while (n > 0) {
sum += n % 10;
n /= 10;
}
cout << "sum of digits: " << sum << "\n";
return 0;
}
Input -123:
sum of digits: 6
Input 0:
sum of digits: 0
Input -2147483648:
sum of digits: 47
Complexity: the loop runs once per digit, d times, and a number n has about log₁₀ n digits: time O(d) = O(log n), extra space O(1).
Q2: Reverse a number
Problem. Reverse the digits of an int, keeping the sign. Leading zeros of the result vanish. Say so if the result does not fit in an int.
| Input | Output |
|---|---|
| 1234 | 4321 |
| -123 | -321 |
| 1200 | 21 |
| 1534236469 | overflow (9646324351 > INT_MAX) |
The obvious attempt
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int rev = 0;
while (n != 0) {
rev = rev * 10 + n % 10;
n /= 10;
}
cout << "reversed: " << rev << "\n";
return 0;
}
Input 1234:
reversed: 4321
Input -123:
reversed: -321
Negative numbers work by themselves: in C++, % keeps the sign of the left side (-123 % 10 is -3) and / rounds toward zero (-123 / 10 is -12), so every digit comes out negative and rev ends up negative.
Input 1200:
reversed: 21
Input 1534236469:
reversed: 1056389759
Wrong, and silent. The real reverse is 9,646,324,351, more than INT_MAX = 2,147,483,647. On the last step rev * 10 overflowed: undefined behaviour. This build printed a wrapped-around value; another compiler or another flag could print something else, or worse.
The fix: build it in a long long, then check the range
INT_MAX and INT_MIN come from the header <climits>.
#include <iostream>
#include <climits>
using namespace std;
int main() {
int n;
cin >> n;
long long rev = 0;
while (n != 0) {
rev = rev * 10 + n % 10;
n /= 10;
}
if (rev > INT_MAX || rev < INT_MIN)
cout << "overflow: doesn't fit in an int\n";
else
cout << "reversed: " << rev << "\n";
return 0;
}
Input 1534236469:
overflow: doesn't fit in an int
Input 1463847412:
reversed: 2147483641
Input -2147483648:
overflow: doesn't fit in an int
Input -123:
reversed: -321
Complexity: time O(d), space O(1).
Interview version (LeetCode "Reverse Integer"): you may be told you cannot use 64-bit integers. Then check before the multiplication: if
rev > INT_MAX / 10orrev < INT_MIN / 10, the nextrev * 10would overflow.
Q3: Palindrome number
Problem. A palindrome reads the same forwards and backwards (121, 7, 1221, the word "madam"). For each integer, say if it is a palindrome.
| Input | Output |
|---|---|
| 121 | palindrome |
| 123 | not |
| -121 | not ("-121" backwards is "121-") |
| 10 | not ("01") |
| 0, 7 | palindrome |
The obvious attempt: n == reverse(n)
#include <iostream>
using namespace std;
long long reverseNum(long long n) {
long long rev = 0;
while (n != 0) {
rev = rev * 10 + n % 10;
n /= 10;
}
return rev;
}
bool isPal(long long n) {
return n == reverseNum(n);
}
int main() {
long long n;
while (cin >> n) {
if (isPal(n)) cout << n << " is a palindrome\n";
else cout << n << " is not a palindrome\n";
}
return 0;
}
Input 121 123 -121 10 0 7:
121 is a palindrome
123 is not a palindrome
-121 is a palindrome
10 is not a palindrome
0 is a palindrome
7 is a palindrome
Why: the reverse keeps the sign, so reverseNum(-121) is -121 and the numbers are equal. But written down, -121 backwards is 121-: a negative number is never a palindrome. (reverseNum uses long long, so it cannot overflow for any int input.)
The fix
#include <iostream>
using namespace std;
long long reverseNum(long long n) {
long long rev = 0;
while (n != 0) {
rev = rev * 10 + n % 10;
n /= 10;
}
return rev;
}
bool isPal(long long n) {
if (n < 0) return false;
return n == reverseNum(n);
}
int main() {
long long n;
while (cin >> n) {
if (isPal(n)) cout << n << " is a palindrome\n";
else cout << n << " is not a palindrome\n";
}
return 0;
}
Input 121 123 -121 10 0 7:
121 is a palindrome
123 is not a palindrome
-121 is not a palindrome
10 is not a palindrome
0 is a palindrome
7 is a palindrome
Numbers ending in 0 (like 10) are already handled: the reverse is 1, not 10.
The C++ string way
to_string(n) turns a number into text (-121 becomes "-121"); reverse(r.begin(), r.end()) from <algorithm> reverses a string in place (begin() and end() mark the whole string).
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool isPal(long long n) {
string s = to_string(n);
string r = s;
reverse(r.begin(), r.end());
return s == r;
}
int main() {
long long n;
while (cin >> n) {
if (isPal(n)) cout << n << " is a palindrome\n";
else cout << n << " is not a palindrome\n";
}
return 0;
}
Input 121 123 -121 10 0 7:
121 is a palindrome
123 is not a palindrome
-121 is not a palindrome
10 is not a palindrome
0 is a palindrome
7 is a palindrome
Here the minus is just a character, so the sign is handled by itself. Cost: O(d) extra space for the two strings. Some interviews say "no strings": then use the maths way.
Complexity summary
| Program | Time | Extra space |
|---|---|---|
| sum of digits | O(d) = O(log n) | O(1) |
reverse (in a long long) |
O(d) | O(1) |
| palindrome, maths way | O(d) | O(1) |
| palindrome, string way | O(d) | O(d) |
d is the number of digits: at most 10 for an int, 19 for a long long.
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
while (n > 0) with n = -123 |
sum of digits: 0 |
the loop never runs | flip the sign first |
if (n < 0) n = -n; with int n |
UB for -2147483648 | 2147483648 doesn't fit in int |
do it in a long long |
int rev, reversing 1534236469 |
reversed: 1056389759 |
signed overflow (UB) | long long rev + INT_MAX check |
n == reverse(n) for negatives |
-121 is a palindrome |
the reverse keeps the sign | if (n < 0) return false; |
int prod = 0; for a product |
the product is always 0 | 0 × anything = 0 | start a product at 1 |
expecting -17 / 5 to be -4 |
-3 |
C++ rounds toward zero | know the rule |
The int sign flip for real: with this build the result is still negative, because -n overflowed.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
if (n < 0) n = -n; // UB when n is -2147483648
cout << n << "\n";
return 0;
}
Input -2147483648:
-2147483648
Your turn: sum equals product? (solution)
Is the sum of the digits equal to their product? Start the product at 1. Use a do-while so that 0 still has one digit (sum 0, product 0: yes).
#include <iostream>
using namespace std;
int main() {
long long n;
while (cin >> n) {
long long m = n < 0 ? -n : n; // the sign is not a digit
long long sum = 0, prod = 1; // product starts at 1, not 0
do {
int d = m % 10;
sum += d;
prod *= d;
m /= 10;
} while (m != 0); // do-while: 0 still has one digit
cout << n << ": sum " << sum << ", product " << prod
<< (sum == prod ? " -> yes\n" : " -> no\n");
}
return 0;
}
Input 123 / 22 / 1124 / 10 / 0 / -22:
123: sum 6, product 6 -> yes
22: sum 4, product 4 -> yes
1124: sum 8, product 8 -> yes
10: sum 1, product 0 -> no
0: sum 0, product 0 -> yes
-22: sum 4, product 4 -> yes
Time O(d), space O(1).
Practice questions (with solutions)
1. Count the digits of n (0 has one digit).
Solution
#include <iostream>
using namespace std;
int main() {
long long n;
while (cin >> n) {
if (n < 0) n = -n;
int count = 0;
do {
count++;
n /= 10;
} while (n != 0);
cout << count << " digits\n";
}
return 0;
}
Input 12345 / 0 / -907 / 9223372036854775807:
5 digits
1 digits
3 digits
19 digits
2. The largest digit of n.
Solution
#include <iostream>
using namespace std;
int main() {
long long n;
while (cin >> n) {
if (n < 0) n = -n;
int best = 0;
do {
int d = n % 10;
if (d > best) best = d;
n /= 10;
} while (n != 0);
cout << "largest digit " << best << "\n";
}
return 0;
}
Input 4721 / -305 / 0:
largest digit 7
largest digit 5
largest digit 0
3. Palindrome without reversing all of it. Reverse only the second half: stop when the reversed half is at least as big as what is left. No overflow is possible.
Solution
#include <iostream>
using namespace std;
// Reverse only the second half: no overflow possible, half the work.
bool isPal(int n) {
if (n < 0 || (n % 10 == 0 && n != 0)) return false; // 10, 120: can't start with 0
int half = 0;
while (n > half) {
half = half * 10 + n % 10;
n /= 10;
}
return n == half || n == half / 10; // even or odd number of digits
}
int main() {
int n;
while (cin >> n)
cout << n << (isPal(n) ? " is a palindrome\n" : " is not a palindrome\n");
return 0;
}
Input 121 1221 123 -121 10 0 2147447412 2147483647:
121 is a palindrome
1221 is a palindrome
123 is not a palindrome
-121 is not a palindrome
10 is not a palindrome
0 is a palindrome
2147447412 is a palindrome
2147483647 is not a palindrome
Mini project: a number inspector
For each number: digit count, digit sum, the reverse (or "overflow"), and palindrome or not.
#include <iostream>
#include <climits>
using namespace std;
int main() {
int n;
while (cin >> n) {
long long m = n < 0 ? -(long long)n : n;
int digits = 0, sum = 0;
long long rev = 0;
do {
int d = m % 10;
digits++;
sum += d;
rev = rev * 10 + d;
m /= 10;
} while (m != 0);
if (n < 0) rev = -rev;
cout << n << ": " << digits << " digits, sum " << sum << ", reversed ";
if (rev > INT_MAX || rev < INT_MIN) cout << "(overflow)";
else cout << rev;
cout << ", " << (n >= 0 && rev == n ? "palindrome" : "not a palindrome") << "\n";
}
return 0;
}
Input 4721 / -123 / 1534236469 / 12321 / 0:
4721: 4 digits, sum 14, reversed 1274, not a palindrome
-123: 3 digits, sum 6, reversed -321, not a palindrome
1534236469: 10 digits, sum 43, reversed (overflow), not a palindrome
12321: 5 digits, sum 9, reversed 12321, palindrome
0: 1 digits, sum 0, reversed 0, palindrome
Quick quiz
#include <iostream>
using namespace std;
int main() {
cout << -17 % 5 << " " << -17 / 5 << "\n";
return 0;
}
(A) -2 -3 (B) 3 -4 (C) 2 -3 (D) -2 -4
Answer
(A) -2 -3. Division rounds toward zero: -17 / 5 is -3. The remainder keeps the sign of the left side, and a == (a / b) * b + a % b always holds: 5 × (-3) + (-2) = -17.
Output:
-2 -3
Interview questions
- How do you get the last digit of n, and remove it?
n % 10andn / 10. - What do
%and/do with negative numbers in C++?/rounds toward zero;%has the sign of the left operand.-7 / 2 == -3,-7 % 2 == -1. - Reverse an integer and detect overflow without 64-bit types. Before
rev = rev * 10 + d, checkrev > INT_MAX / 10 || rev < INT_MIN / 10. - Why can't you write
abs(INT_MIN)safely? Its positive value, 2147483648, doesn't fit in anint: undefined behaviour. - Is signed overflow an error in C++? No message: it is undefined behaviour. Unsigned overflow, by contrast, is defined: it wraps around modulo 2ⁿ.
- Is a negative number a palindrome? No: the minus sign is only at the front.
- Palindrome check in O(1) space without overflow? Reverse only half the digits.
- Time complexity of a digit loop? O(number of digits) = O(log n).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Digit | One of 0-9 in a number | 4721 has digits 4, 7, 2, 1 |
% (modulo) |
The remainder of a division | 4721 % 10 is 1 |
| Integer division | Division that drops the remainder (rounds toward zero) | 4721 / 10 is 472 |
| Digit loop | Read n % 10, use it, n /= 10, until n is 0 |
sum of digits |
do-while |
A loop that runs its body at least once | counting the digits of 0 |
int range |
-2,147,483,648 to 2,147,483,647 (32 bits) | INT_MIN, INT_MAX |
INT_MAX / INT_MIN |
The largest / smallest int |
from <climits> |
long long |
An integer of at least 64 bits | up to about 9.2 × 10¹⁸ |
| Signed overflow | A signed result too big for its type | 9646324351 in an int |
| Undefined behaviour (UB) | The C++ standard makes no promise | a wrapped value here |
| Reverse a number | rev = rev * 10 + d for each digit |
1234 → 4321 |
| Palindrome | Reads the same forwards and backwards | 121, "madam" |
to_string |
Turns a number into a string |
to_string(-121) is "-121" |
std::reverse |
Reverses a range in place (<algorithm>) |
reverse(s.begin(), s.end()) |
begin() / end() |
The start and one-past-the-end of a container | the whole string |
| Edge case | A small or extreme input that often breaks code | 0, negatives, INT_MIN |
| O(d), O(log n) | Work grows with the number of digits | 10 turns for a 10-digit number |
| O(1) space | A fixed number of variables | sum, rev |
Summary
n % 10reads the last digit andn / 10removes it: every digit question is this loop.- Negative numbers: the sign is not a digit; flip it in a
long long, because-INT_MINoverflows anint. rev = rev * 10 + dbuilds the reverse; build it in along longand compare withINT_MAX/INT_MIN, because signed overflow is silent UB.- C++
/rounds toward zero and%keeps the left side's sign. - Negative numbers are never palindromes; the string way (
to_string+reverse) handles the sign by itself but uses O(d) space.
Next episode: Number questions II: checking primes fast, counting primes with the sieve of Eratosthenes, and GCD and LCM, with more overflow traps.