These are the notes for C Coding Questions, episode 2, placement practice for people who finished the SyntaxPilot C course. Three more pattern questions that keep appearing in campus tests: a diamond, Floyd's triangle and Pascal's triangle. The last one hides a trap that catches most students: the textbook factorial formula overflows an int.
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), the SyntaxPilot compiler's C command with warnings on, and every output below is real.
Reminder: the plan from episode 1
- The outer loop walks the rows; the inner loops print the columns (character positions) of one row;
printf("\n")ends the row. - Write a table of row
iagainst spaces and symbols, and read the formula off it. - Check the first and the last row, so you don't make an off-by-one error (a loop that runs one time too many or too few).
- Test
n = 1,n = 0and the limits. Compile with-Wall.
Q1: Diamond
Problem. Read n, the number of rows in the top half (including the widest row), and print a diamond of 2n - 1 rows.
Example. Input 3:
*
***
*****
***
*
Think out loud
| Half | Rows | Spaces in row i |
Stars in row i |
|---|---|---|---|
| top | i = 1 .. n |
n - i |
2i - 1 |
| bottom | i = n - 1 .. 1 |
n - i |
2i - 1 |
The top half is the pyramid from episode 1; the bottom half is the same rows in reverse. Edge cases: n = 1 is one star, n = 0 prints nothing.
The obvious attempt
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int s = 0; s < n - i; s++) printf(" ");
for (int j = 0; j < 2 * i - 1; j++) printf("*");
printf("\n");
}
for (int i = n; i >= 1; i--) {
for (int s = 0; s < n - i; s++) printf(" ");
for (int j = 0; j < 2 * i - 1; j++) printf("*");
printf("\n");
}
return 0;
}
Input 3:
*
***
*****
*****
***
*
The widest row is printed twice: the diamond has a doubled waist.
Why it failed
Think of drawing a diamond by folding paper: you draw the top half ending on the widest line, fold, and trace the mirror image. If you trace the fold line too, it appears twice. Row n belongs to the top half; the bottom loop started at i = n and drew it again. That's an off-by-one error in where the loop starts.
The fix
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int s = 0; s < n - i; s++) printf(" ");
for (int j = 0; j < 2 * i - 1; j++) printf("*");
printf("\n");
}
for (int i = n - 1; i >= 1; i--) {
for (int s = 0; s < n - i; s++) printf(" ");
for (int j = 0; j < 2 * i - 1; j++) printf("*");
printf("\n");
}
return 0;
}
All the test cases:
Input 3:
*
***
*****
***
*
Input 1:
*
Input 0:
(no output)
For n = 1 the bottom loop starts at i = 0, so its condition i >= 1 is false and it doesn't run.
Complexity: 2n - 1 rows of at most 2n - 1 characters: O(n²) time, O(1) space.
Q2: Floyd's triangle
Problem. Read n and print n rows; row i has i numbers, and the numbers keep counting 1, 2, 3, ... across rows. Print each number in 4 columns.
Example. Input 4:
1
2 3
4 5 6
7 8 9 10
Think out loud
- The shape is the right-angle triangle from episode 1.
- The value is one counter,
num, increased after every print. %4dprints an integer right-aligned in a field of 4 columns, so 1-digit and 2-digit numbers line up.- A check you can compute in advance: the last number is
n(n+1)/2. 4 rows end at 10; 7 rows end at 28. - Edge cases:
n = 1(just 1), a biggernlike 7.
The obvious attempt
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int num = 1;
for (int j = 1; j <= i; j++) {
printf("%4d", num);
num++;
}
printf("\n");
}
return 0;
}
Input 4:
1
1 2
1 2 3
1 2 3 4
It compiles cleanly, with no warning, and the count restarts on every row.
Why it failed: scope
A clinic's token machine gives out token 1, 2, 3, ... If someone resets it every hour, the first patient of every hour gets token 1 again. int num = 1; is inside the outer loop, so it runs again at the start of every row.
Where a variable is declared decides where it exists and how long it lives: that's its scope. A variable declared inside a loop's body is created fresh on every turn. Declare the counter once, before the loops, so it lives across all rows.
The fix
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int num = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
printf("%4d", num);
num++;
}
printf("\n");
}
return 0;
}
All the test cases:
Input 4:
1
2 3
4 5 6
7 8 9 10
Input 1:
1
Input 7:
1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21
22 23 24 25 26 27 28
Seven rows end at 28 = 7 × 8 / 2, as predicted.
Complexity: n(n+1)/2 numbers printed: O(n²) time, O(1) space.
Q3: Pascal's triangle
First, nCr
A pizza shop has 4 toppings and you may pick 2. There are 6 different pizzas. This count is n choose r, written nCr or C(n, r): the number of ways to choose r things from n. Here 4C2 = 6.
The textbook formula uses factorials (the product of all integers from 1 up to a number, written n!; 4! = 24):
nCr = n! / (r! × (n - r)!)
4C2 = 24 / (2 × 2) = 6
Write the counts for each n in a row and you get Pascal's triangle. Row r holds rC0, rC1, ..., rCr; each number is the sum of the two above it.
Problem. Read n and print rows 0 to n - 1 of Pascal's triangle, numbers separated by spaces.
Example. Input 5:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Edge cases: n = 1 prints just 1; a bigger n means much bigger numbers.
The obvious attempt: the factorial formula
#include <stdio.h>
int fact(int x) {
int f = 1;
for (int i = 2; i <= x; i++) f = f * i;
return f;
}
int main() {
int n;
scanf("%d", &n);
for (int r = 0; r < n; r++) {
for (int k = 0; k <= r; k++)
printf("%d ", fact(r) / (fact(k) * fact(r - k)));
printf("\n");
}
return 0;
}
It looks fine for small inputs, and gcc -Wall prints no warning:
Input 5:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Input 14:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 4 24 88 221 399 532 532 399 221 88 24 4 1
Row 13 (the last row for input 14) is wrong. It should be 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1.
Why it failed: integer overflow
| Value | Size | Fits in an int? |
|---|---|---|
INT_MAX |
2,147,483,647 | the largest int |
| 12! | 479,001,600 | yes |
| 13! | 6,227,020,800 | no |
| 20! | 2,432,902,008,176,640,000 | fits in long long (max about 9.22 × 10¹⁸) |
| 21! | 51,090,942,171,709,440,000 | not even in long long |
When a result is too big for its type, that's integer overflow. For signed types like int, overflow is undefined behaviour (UB): the C standard makes no promise about what happens. With this compiler and these options we got the wrong numbers above, but another compiler or option could give different garbage, or remove code. Never rely on UB. A bigger type only delays the problem: long long breaks at 21!.
The fix: build each entry from the previous one
Never build the giant factorials. Every row starts with 1, and
C(r, 0) = 1
C(r, k+1) = C(r, k) × (r - k) / (k + 1)
Row 4: 1 → 1·4/1 = 4 → 4·3/2 = 6 → 6·2/3 = 4 → 4·1/4 = 1.
Multiply first, then divide. C(r, k) × (r - k) always equals C(r, k+1) × (k + 1), a whole multiple of k + 1, so the integer division is exact. Dividing first (c / (k + 1) * (r - k)) throws away the remainder and gives wrong values. The intermediate number is at most about r times the answer, so with long long it stays safe for every row up to 60 (see "Your turn").
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
for (int r = 0; r < n; r++) {
long long c = 1;
for (int k = 0; k <= r; k++) {
printf("%lld ", c);
c = c * (r - k) / (k + 1);
}
printf("\n");
}
return 0;
}
All the test cases:
Input 5:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Input 14:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
Input 1:
1
Complexity
| Method | Work per entry | Total time | Extra space | Correct? |
|---|---|---|---|---|
| Factorial formula | three factorials, about 3r multiplications | O(n³) | O(1) | no: overflows at 13! with int |
| Next from previous | one multiply, one divide | O(n²) | O(1) | yes, up to row 60 in long long |
The triangle has n(n+1)/2 entries, so O(n²) is the best possible: printing them is the work.
Common mistakes (and the real messages)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
bottom half for (int i = n; i >= 1; i--) |
no error: the widest row twice | row n belongs to the top half |
start at i = n - 1 |
int num = 1; inside the row loop |
no error: 1, 1 2, 1 2 3 |
the counter is re-created every row (scope) | declare it before the loops |
int factorials for nCr |
no warning: wrong numbers from row 13 (undefined behaviour) | 13! > INT_MAX |
c = c * (r - k) / (k + 1) in long long |
c = c / (k + 1) * (r - k); |
no error: wrong values | integer division drops the remainder | multiply first, then divide |
printf("%d ", c) with long long c |
warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=] |
wrong format for the type | %lld |
Your turn: one row of Pascal's triangle (solution)
Problem. Read r (0 to 60) and print only row r. Input 6 → 1 6 15 20 15 6 1.
Show the solution
#include <stdio.h>
int main() {
int r;
scanf("%d", &r);
long long c = 1;
for (int k = 0; k <= r; k++) {
printf("%lld ", c);
c = c * (r - k) / (k + 1);
}
printf("\n");
return 0;
}
Input 6:
1 6 15 20 15 6 1
Input 0:
1
Why is r = 60 safe? The biggest entry of row 60 is 60C30 ≈ 1.18 × 10¹⁷. Before each division the intermediate value is an entry times r - k; the largest one in row 60 is about 3.5 × 10¹⁸, still below the long long maximum of about 9.22 × 10¹⁸. (We also checked it with gcc's -fsanitize=undefined, which reports any signed overflow: none.) Time O(r), space O(1).
Practice questions (with solutions)
1. A hollow diamond of stars (only the edges).
Solution
A star at the first and last position of each row, spaces between. A small function prints one row so both halves share it.
#include <stdio.h>
void row(int n, int i) {
for (int s = 0; s < n - i; s++) printf(" ");
for (int j = 1; j <= 2 * i - 1; j++) printf("%c", (j == 1 || j == 2 * i - 1) ? '*' : ' ');
printf("\n");
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) row(n, i);
for (int i = n - 1; i >= 1; i--) row(n, i);
return 0;
}
Input 3:
*
* *
* *
* *
*
2. Floyd's triangle upside down (start from the largest number).
Solution
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int num = n * (n + 1) / 2;
for (int i = n; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
printf("%4d", num);
num--;
}
printf("\n");
}
return 0;
}
Input 4:
10 9 8 7
6 5 4
3 2
1
3. A diamond of numbers.
Solution
#include <stdio.h>
void row(int n, int i) {
for (int s = 1; s <= n - i; s++) printf(" ");
for (int j = 1; j <= i; j++) printf("%d", j);
for (int j = i - 1; j >= 1; j--) printf("%d", j);
printf("\n");
}
int main() {
int n;
scanf("%d", &n);
if (n < 1 || n > 9) {
printf("n must be 1 to 9\n");
return 0;
}
for (int i = 1; i <= n; i++) row(n, i);
for (int i = n - 1; i >= 1; i--) row(n, i);
return 0;
}
Input 3:
1
121
12321
121
1
Quick quiz
int c = 1;
for (int k = 0; k < 3; k++)
c = c * (5 - k) / (k + 1);
printf("%d\n", c);
(A) 10 (B) 6 (C) 60 (D) 5
Answer
(A) 10. 1·5/1 = 5, 5·4/2 = 10, 10·3/3 = 10. That's 5C3 = 10.
Interview questions
- Why does the factorial formula fail for nCr in C? Factorials grow very fast: 13! already exceeds
INT_MAXand 21! exceedslong long. Signed overflow is undefined behaviour, so the results are garbage. - How do you compute nCr without overflow? Build it step by step:
C(n, k+1) = C(n, k) * (n - k) / (k + 1), multiplying before dividing; also useC(n, r) = C(n, n - r)to take the smallerr. - Why must you multiply before dividing? The product is an exact multiple of
k + 1; dividing first loses the remainder in integer division. - What is scope? The part of the program where a variable exists. A variable declared inside a loop body is created again on every turn.
- What is undefined behaviour? Code whose result the C standard doesn't define, such as signed overflow; the compiler may do anything, so correct programs must avoid it.
- Time complexity of printing Pascal's triangle with n rows? O(n²) with the step formula; O(n³) with factorials.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Diamond pattern | A pyramid followed by the same rows in reverse | 1, 3, 5, 3, 1 stars |
| Floyd's triangle | A right-angle triangle of consecutive numbers | 1 · 2 3 · 4 5 6 |
| Pascal's triangle | A triangle where row r holds rC0 … rCr; each entry is the sum of the two above | 1 4 6 4 1 |
| nCr (n choose r) | The number of ways to choose r things from n | 4C2 = 6 |
Factorial n! |
The product 1 × 2 × … × n | 4! = 24 |
| Counter | A variable that counts up as the program runs | num++ |
| Scope | Where in the program a variable exists | num inside the loop body is new every turn |
%4d |
printf format: an int right-aligned in 4 columns |
" 7" |
%lld |
printf format for long long |
printf("%lld", c) |
long long |
An integer type of at least 64 bits, up to about 9.22 × 10¹⁸ | long long c = 1; |
INT_MAX |
The largest int: 2,147,483,647 here |
from <limits.h> |
| Integer overflow | A result too big for its type | 13! in an int |
| Undefined behaviour (UB) | Code whose result C does not define; anything may happen | signed overflow |
| Integer division | Division of two integers, dropping the remainder | 7 / 2 == 3 |
| Off-by-one error | A loop that runs one time too many or too few | the diamond's doubled middle |
| Edge case | An input at the boundary | n = 0, n = 1 |
| Time complexity | How the work grows with the input | O(n²) vs O(n³) |
| Space complexity | How the extra memory grows with the input | O(1) |
Summary
- Diamond: top half
i = 1..n, bottom halfi = n - 1..1; the widest row is printed once. - Floyd's triangle: one counter, declared before the loops (scope).
- nCr counts the ways to choose; Pascal's triangle lists them row by row.
- Factorials overflow fast: 13! doesn't fit in an
int, and signed overflow is undefined behaviour. - Build each entry from the previous one:
c = c * (r - k) / (k + 1), multiply first, inlong long. - All three patterns are O(n²) time and O(1) extra space; the factorial version is O(n³) and wrong.
Next episode: Number questions I: reverse a number, palindrome number, sum of digits (negative numbers and overflow).