SyntaxPilot
Courses/C Coding Questions/Lesson 5
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C Coding Questions · Lesson 5 of 30

Number questions III

GCD and LCM (Euclid's algorithm)factorial and integer overflow (int vs long long vs unsigned)n-th Fibonacci (loop vs naive recursion)

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
  1. The third LCM is wrong: a * b is 9,999,900,000, far more than INT_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.
  2. 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

  1. 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.
  2. What is its complexity? O(log min(a, b)): the numbers at least halve every two steps.
  3. How do you compute the LCM safely? a / gcd(a, b) * b, in a type wide enough for the result.
  4. What happens when an int overflows? An unsigned int? Signed overflow is undefined behaviour; unsigned arithmetic wraps around modulo 2ⁿ.
  5. What is the largest factorial that fits in 64 bits? 20! = 2,432,902,008,176,640,000.
  6. How do you detect multiplication overflow before it happens? For positive values, a > LIMIT / b means a * b > LIMIT.
  7. 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).
  8. What is a base case? The input where a recursive function stops calling itself (n <= 1 for 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 / i before 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).