These are the notes for C Coding Questions, episode 5, placement practice for people who finished the SyntaxPilot C course. Three classics with silent traps: GCD and LCM (Euclid's algorithm), factorial (integer overflow: int vs unsigned vs long long) and the n-th Fibonacci number (loop vs naive recursion).
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 gcc -Wall -O2 -Wno-unused-result main.c -o main -lm (gcc 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 (Time Limit Exceeded), like an online judge.
GCD and LCM: tiles and buses
| In real life | In C | 12 and 18 |
|---|---|---|
| The biggest square tile that covers a 12 × 18 floor exactly | GCD, the greatest common divisor: the biggest number dividing both | 6 |
| Buses every 12 and every 18 minutes leave together again after… | LCM, the least common multiple: the smallest number both divide | 36 |
| 6 × 36 = 216 = 12 × 18 | gcd(a, b) × lcm(a, b) = a × b | so lcm = a / gcd × b |
Two numbers whose GCD is 1 are coprime (7 and 13).
Q1: GCD and LCM
Problem. Read t, then t pairs of ints a b with 1 ≤ a, b ≤ INT_MAX. For each pair print gcd = …, lcm = …. Time limit: 8 seconds.
| Input | Output |
|---|---|
12 18 |
gcd = 6, lcm = 36 |
7 13 |
gcd = 1, lcm = 91 |
100000 99999 |
gcd = 1, lcm = 9999900000 |
Think out loud
The GCD can't be bigger than the smaller number: start there and count down; the first i dividing both is the GCD. Then lcm = a × b / gcd. Edge cases: a == b, one divides the other, coprime numbers, huge numbers.
The obvious attempt
(a < b ? a : b) is the conditional (ternary) operator: if a < b it gives a, otherwise b.
#include <stdio.h>
int main() {
int t;
scanf("%d", &t);
while (t--) {
int a, b, g = 1;
scanf("%d %d", &a, &b);
for (int i = (a < b ? a : b); i >= 1; i--) {
if (a % i == 0 && b % i == 0) {
g = i;
break;
}
}
int lcm = a * b / g;
printf("gcd = %d, lcm = %d\n", g, lcm);
}
return 0;
}
Input 3, 12 18, 7 13, 100000 99999:
gcd = 6, lcm = 36
gcd = 1, lcm = 91
gcd = 1, lcm = 1409965408
- The third LCM is wrong:
a * bis 9,999,900,000, far more thanINT_MAX(2,147,483,647). Signed overflow is undefined behaviour (the C standard promises nothing); the number printed is just what this build produced. No warning. - Big coprime pairs:
Input 3, 2147483646 2147483645, 2147483647 2147483646, 2147483645 2147483644:
Time Limit Exceeded (stopped after 8 seconds, no output)
For a coprime pair near INT_MAX the loop counts down about two billion times before reaching 1.
Euclid's algorithm
Cut the biggest squares off a 48 × 18 floor: two 18 × 18 squares, and an 18 × 12 strip is left (48 % 18 = 12). Any tile that fits the whole floor also fits the strip, so gcd(48, 18) = gcd(18, 12). Repeat:
| a | b | a % b |
|---|---|---|
| 48 | 18 | 12 |
| 18 | 12 | 6 |
| 12 | 6 | 0 |
| 6 | 0 | stop: gcd = 6 |
gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a. Euclid described it around 300 BC.
LCM without overflow
(long long)a / g * b: the cast (long long) converts a to a 64-bit type before the arithmetic, and dividing by g first keeps the intermediate value small. The result is at most a × b < 2⁶² for ints, so it fits in a long long (up to about 9.22 × 10¹⁸). Print it with %lld.
The fix
#include <stdio.h>
int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int a, b;
scanf("%d %d", &a, &b);
int g = gcd(a, b);
long long lcm = (long long)a / g * b;
printf("gcd = %d, lcm = %lld\n", g, lcm);
}
return 0;
}
Input 3, 12 18, 7 13, 100000 99999:
gcd = 6, lcm = 36
gcd = 1, lcm = 91
gcd = 1, lcm = 9999900000
Input 3, 2147483646 2147483645, 2147483647 2147483646, 2147483645 2147483644:
gcd = 1, lcm = 4611686007689969670
gcd = 1, lcm = 4611686011984936962
gcd = 1, lcm = 4611686003395002380
Input 3, 5 5, 6 36, 1 2147483647:
gcd = 5, lcm = 5
gcd = 6, lcm = 36
gcd = 1, lcm = 2147483647
Complexity: counting down is O(min(a, b)). Euclid's numbers at least halve every two steps, so it is O(log min(a, b)) time (under 50 steps for any int), O(1) space.
Q2: Factorial
Problem. n! ("n factorial") = 1 × 2 × 3 × … × n, and 0! = 1 (the empty product). Read n; print n! = …, or a clear message when it can't be computed.
| Input | Output |
|---|---|
5 |
120 |
13 |
6227020800 |
20 |
2432902008176640000 |
21 |
too big for a long long (21! ≈ 5.1 × 10¹⁹) |
-3 |
no factorial for a negative number |
Attempt 1: int
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int f = 1;
for (int i = 2; i <= n; i++) f = f * i;
printf("%d! = %d\n", n, f);
return 0;
}
Input 5:
5! = 120
Input 12:
12! = 479001600
Input 13:
13! = 1932053504
13! = 6,227,020,800 > INT_MAX: signed overflow, undefined behaviour, no warning.
Attempt 2: unsigned int
An unsigned type has no negative values, so unsigned int reaches 4,294,967,295 (2³² − 1). Print it with %u.
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
unsigned int f = 1;
for (int i = 2; i <= n; i++) f = f * i;
printf("%d! = %u\n", n, f);
return 0;
}
Input 13:
13! = 1932053504
Unsigned overflow is not undefined: it wraps around like a car's odometer, keeping the result modulo 2³² (4,294,967,296). 6,227,020,800 − 4,294,967,296 = 1,932,053,504. Defined, but still the wrong answer.
Attempt 3: long long
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
long long f = 1;
for (int i = 2; i <= n; i++) f = f * i;
printf("%d! = %lld\n", n, f);
return 0;
}
Input 13:
13! = 6227020800
Input 20:
20! = 2432902008176640000
Input 21:
21! = -4249290049419214848
Right up to 20!, then 21! overflows long long (LLONG_MAX ≈ 9.22 × 10¹⁸): a bigger type only moves the wall. (unsigned long long also stops at 20!.)
The fix: check before you multiply
f * i > LLONG_MAX is exactly f > LLONG_MAX / i (for positive i), and the division can't overflow. Checking after multiplying is too late.
#include <stdio.h>
#include <limits.h>
int main() {
int n;
scanf("%d", &n);
if (n < 0) {
printf("no factorial for a negative number\n");
return 0;
}
long long f = 1;
for (int i = 2; i <= n; i++) {
if (f > LLONG_MAX / i) {
printf("%d! is too big for a long long\n", n);
return 0;
}
f = f * i;
}
printf("%d! = %lld\n", n, f);
return 0;
}
Input 21:
21! is too big for a long long
Input 20:
20! = 2432902008176640000
Input 13:
13! = 6227020800
Input 0:
0! = 1
Input 1:
1! = 1
Input -3:
no factorial for a negative number
Complexity: n multiplications, O(n) time, O(1) space.
| Type | Largest value | Largest n! that fits |
|---|---|---|
int |
2,147,483,647 | 12! |
unsigned int |
4,294,967,295 | 12! |
long long |
9,223,372,036,854,775,807 | 20! |
unsigned long long |
18,446,744,073,709,551,615 | 20! |
Q3: The n-th Fibonacci number
Problem. F(0) = 0, F(1) = 1, F(n) = F(n − 1) + F(n − 2): 0 1 1 2 3 5 8 13 21 34 55 … Read n (0 to 92) and print F(n). F(92) is the largest Fibonacci number that fits in a long long.
The obvious attempt: recursion
A recursive function calls itself. The base case (n <= 1) is where the calls stop.
#include <stdio.h>
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
int main() {
int n;
scanf("%d", &n);
printf("F(%d) = %d\n", n, fib(n));
return 0;
}
Input 10:
F(10) = 55
Input 50:
Time Limit Exceeded (stopped after 8 seconds, no output)
Why: the same work again and again
fib(5) calls fib(4) and fib(3); fib(4) calls fib(3) again. fib(3) is computed twice, fib(2) three times, and fib(5) makes 15 calls. The number of calls almost doubles with each step up: exponential growth. Counting them for real:
#include <stdio.h>
long long calls = 0;
int fib(int n) {
calls++;
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
int main() {
for (int n = 5; n <= 40; n += 5) {
calls = 0;
int f = fib(n);
printf("fib(%d) = %d, %lld calls\n", n, f, calls);
}
return 0;
}
Output:
fib(5) = 5, 15 calls
fib(10) = 55, 177 calls
fib(15) = 610, 1973 calls
fib(20) = 6765, 21891 calls
fib(25) = 75025, 242785 calls
fib(30) = 832040, 2692537 calls
fib(35) = 9227465, 29860703 calls
fib(40) = 102334155, 331160281 calls
fib(50) would make about 40 billion calls. Also, fib returns an int, which overflows after F(46) = 1,836,311,903.
The fix: walk forward
Keep only the last two numbers, like counting stairs.
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
if (n < 0 || n > 92) {
printf("n must be from 0 to 92\n");
return 0;
}
long long a = 0, b = 1;
for (int i = 0; i < n; i++) {
long long next = a + b;
a = b;
b = next;
}
printf("F(%d) = %lld\n", n, a);
return 0;
}
Input 50:
F(50) = 12586269025
Input 92:
F(92) = 7540113804746346429
Input 0:
F(0) = 0
Input 1:
F(1) = 1
Input 2:
F(2) = 1
Input 10:
F(10) = 55
Input 93:
n must be from 0 to 92
Complexity:
| Version | Time | Space |
|---|---|---|
| Naive recursion | O(2ⁿ) (more precisely about 1.618ⁿ) | O(n): up to n calls waiting on the stack |
| Loop with two values | O(n) | O(1) |
Complexity summary
| Question | Obvious attempt | Fixed | Extra space |
|---|---|---|---|
| GCD and LCM | O(min(a, b)), LCM overflows | O(log min(a, b)) (Euclid) | O(1) |
| Factorial | wrong from 13! (int) | O(n) with an overflow check | O(1) |
| Fibonacci | O(2ⁿ) recursion | O(n) loop | O(1) |
Common mistakes (and the real messages)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| GCD by counting down from min(a, b) | Time Limit Exceeded |
up to 2 billion steps | Euclid: gcd(b, a % b) |
int lcm = a * b / g; |
no warning: a wrong LCM | a * b overflows an int (UB) |
(long long)a / g * b |
(long long)(a * b) |
still wrong | the cast comes after the overflow | cast an operand: (long long)a * b |
int f; factorial for n = 13 |
no warning: 1932053504 |
13! > INT_MAX (UB) |
long long + check |
unsigned int f; |
no warning: 1932053504 |
wraps around modulo 2³² | a type big enough, plus the check |
long long without a check, n = 21 |
-4249290049419214848 |
21! > LLONG_MAX (UB) |
if (f > LLONG_MAX / i) before f *= i |
return fib(n - 1) + fib(n - 2); for n = 50 |
Time Limit Exceeded |
O(2ⁿ) repeated calls | a loop with two values |
int fib(...) for n = 47 |
wrong (negative) values | F(47) > INT_MAX |
long long, n ≤ 92 |
Your turn: GCD of an array (solution)
Problem. Read n, then n positive ints; print the GCD of all of them. 12 18 24 36 → 6, 7 14 21 → 7, 9 28 → 1.
Idea. gcd(a, b, c) = gcd(gcd(a, b), c): start with the first number and fold in each next one. Once the GCD is 1 it can't get smaller, so stop reading early.
Show the solution
#include <stdio.h>
int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
int n, x;
scanf("%d", &n);
scanf("%d", &x);
int g = x;
for (int i = 1; i < n; i++) {
scanf("%d", &x);
g = gcd(g, x);
if (g == 1) break; /* it can't get smaller */
}
printf("%d\n", g);
return 0;
}
Input 4 12 18 24 36:
6
Input 3 7 14 21:
7
Input 2 9 28:
1
Input 1 42:
42
Time O(n log M) where M is the largest value, space O(1).
Practice questions (with solutions)
1. LCM of 1, 2, …, n. When does it stop fitting in a long long?
Solution
#include <stdio.h>
#include <limits.h>
long long gcd(long long a, long long b) {
while (b != 0) {
long long r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
int n;
scanf("%d", &n);
long long l = 1;
for (int i = 2; i <= n; i++) {
long long step = i / gcd(l, i);
if (l > LLONG_MAX / step) {
printf("lcm(1..%d) is too big for a long long\n", n);
return 0;
}
l = l * step;
}
printf("lcm(1..%d) = %lld\n", n, l);
return 0;
}
Input 10:
lcm(1..10) = 2520
Input 20:
lcm(1..20) = 232792560
Input 42:
lcm(1..42) = 219060189739591200
Input 43:
lcm(1..43) is too big for a long long
2. Trailing zeros of n! without computing n! Each trailing zero comes from a factor 10 = 2 × 5, and there are always more 2s than 5s, so count the factors of 5: n/5 + n/25 + n/125 + …
Solution
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
long long zeros = 0;
for (long long p = 5; p <= n; p = p * 5) zeros = zeros + n / p;
printf("%lld\n", zeros);
return 0;
}
Input 5:
1
Input 25:
6
Input 100:
24
Input 2147483647:
536870902
p is a long long so p * 5 can't overflow when n is near INT_MAX. Time O(log n).
3. Is n a Fibonacci number? (0 ≤ n ≤ 10¹⁸)
Solution
#include <stdio.h>
int main() {
long long n;
scanf("%lld", &n);
long long a = 0, b = 1;
while (a < n) {
long long next = a + b;
a = b;
b = next;
}
if (a == n) printf("%lld is a Fibonacci number\n", n);
else printf("%lld is not a Fibonacci number\n", n);
return 0;
}
Input 0:
0 is a Fibonacci number
Input 1:
1 is a Fibonacci number
Input 55:
55 is a Fibonacci number
Input 56:
56 is not a Fibonacci number
Input 12586269025:
12586269025 is a Fibonacci number
F(87) ≈ 6.8 × 10¹⁷ is below 10¹⁸ and F(88) is above it, so next never overflows. Time O(log n) (Fibonacci numbers grow exponentially).
Quick quiz
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
/* count every call, including fib(5) */
(A) 15 (B) 5 (C) 9 (D) 32
Answer
(A) 15. calls(n) = 1 + calls(n − 1) + calls(n − 2), calls(0) = calls(1) = 1: 1, 1, 3, 5, 9, 15. The program above confirms it.
Interview questions
- What is Euclid's algorithm, and why does it work? gcd(a, b) = gcd(b, a % b): any common divisor of a and b also divides a % b = a − k·b, and vice versa.
- What is its complexity? O(log min(a, b)): the numbers at least halve every two steps.
- How do you compute the LCM safely?
a / gcd(a, b) * b, in a type wide enough for the result. - What happens when an
intoverflows? Anunsigned int? Signed overflow is undefined behaviour; unsigned arithmetic wraps around modulo 2ⁿ. - What is the largest factorial that fits in 64 bits? 20! = 2,432,902,008,176,640,000.
- How do you detect multiplication overflow before it happens? For positive values,
a > LIMIT / bmeansa * b > LIMIT. - Why is naive recursive Fibonacci slow, and how do you fix it? It recomputes the same subproblems (exponential calls); use a loop, or remember results (memoization).
- What is a base case? The input where a recursive function stops calling itself (
n <= 1for Fibonacci).
Glossary
| Term | Meaning | Example |
|---|---|---|
| GCD (greatest common divisor) | The biggest number dividing both | gcd(12, 18) = 6 |
| LCM (least common multiple) | The smallest number both divide | lcm(12, 18) = 36 |
| Coprime | Two numbers whose GCD is 1 | 7 and 13 |
| Euclid's algorithm | gcd(a, b) = gcd(b, a % b) until b is 0 | 48, 18 → 18, 12 → 12, 6 → 6 |
| Conditional (ternary) operator | c ? x : y gives x if c is true, else y |
a < b ? a : b |
| Cast | Converting a value to another type | (long long)a |
| Factorial (n!) | 1 × 2 × … × n; 0! = 1 | 5! = 120 |
| Integer overflow | A result too big for its type | 13! in an int |
| Undefined behaviour (UB) | Code whose result the C standard doesn't define | signed overflow |
unsigned int |
An integer type with no negatives, 0 to 4,294,967,295 | unsigned int f; |
| Wrap around | Unsigned arithmetic keeps the result modulo 2ⁿ | 6,227,020,800 → 1,932,053,504 |
%u / %lld |
printf formats for unsigned int / long long |
printf("%lld", f); |
LLONG_MAX |
The largest long long, about 9.22 × 10¹⁸, from <limits.h> |
f > LLONG_MAX / i |
| Fibonacci numbers | 0, 1, then each is the sum of the two before | 0 1 1 2 3 5 8 |
| Recursion | A function that calls itself | fib(n - 1) + fib(n - 2) |
| Base case | Where the recursion stops | if (n <= 1) return n; |
| Exponential time | Work that multiplies with each step, like O(2ⁿ) | naive fib |
| Stack (call stack) | Memory holding the calls that are still waiting | fib(50) is 50 calls deep |
| Memoization | Remembering results so they aren't recomputed | an array of computed fib values |
| Time Limit Exceeded (TLE) | The judge stopped a program that ran too long | 8 seconds here |
| Big O notation | How work grows with the input, ignoring constants | O(log n), O(n), O(2ⁿ) |
| Edge case | An input at the boundary | 0!, F(0), coprime pairs |
Summary
- GCD with Euclid:
gcd(a, b) = gcd(b, a % b), O(log n). LCM =(long long)a / g * b. - Signed overflow is undefined behaviour; unsigned wraps around; both give wrong answers silently.
- A bigger type only moves the wall: check
f > LLONG_MAX / ibefore multiplying. - Naive recursive Fibonacci is O(2ⁿ); a loop keeping the last two values is O(n) time, O(1) space.
Next episode: Number questions IV: decimal to binary and back, counting set bits, checking a power of two with n & (n - 1).