Write each function yourself first, then open the solution – every solution was compiled and run, and the output shown is the real output. Tick "Mark as solved" to track your progress.
Question 1Easy
Write gcd() (Euclid's algorithm) and lcm() that cannot overflow for large inputs.
Solution
main.c
#include <stdio.h>
int gcd(int a, int b) {
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return a;
}
long long lcm(int a, int b) {
return (long long) (a / gcd(a, b)) * b; /* divide first, then multiply */
}
int main(void) {
printf("gcd(48, 180) = %d, lcm(48, 180) = %lld\n", gcd(48, 180), lcm(48, 180));
return 0;
}
Output Verified by compiling and running
gcd(48, 180) = 12, lcm(48, 180) = 720
Euclid: gcd(a, b) = gcd(b, a mod b) until b is 0. For the LCM, dividing before multiplying keeps the intermediate value small, and the long long result has room for large products.
Write is_prime() that tests divisors only up to √n, and print all primes up to 50.
Solution
main.c
#include <stdbool.h>
#include <stdio.h>
bool is_prime(int n) {
if (n < 2)
return false;
if (n % 2 == 0)
return n == 2;
for (int d = 3; d * d <= n; d += 2) /* only odd divisors up to sqrt(n) */
if (n % d == 0)
return false;
return true;
}
int main(void) {
for (int n = 1; n <= 50; n++)
if (is_prime(n))
printf("%d ", n);
printf("\n");
return 0;
}
Output Verified by compiling and running
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
If n has a divisor larger than √n, it also has one smaller, so checking up to √n is enough. d * d <= n avoids calling sqrt(), and skipping even divisors halves the work.
Find the largest element of an array with a recursive function.
Solution
main.c
#include <stdio.h>
int max_of(const int *a, int n) {
if (n == 1)
return a[0]; /* base case: one element */
int rest = max_of(a + 1, n - 1); /* max of the remaining elements */
return a[0] > rest ? a[0] : rest;
}
int main(void) {
int a[] = {17, 42, 8, 99, 23};
printf("max = %d\n", max_of(a, 5));
return 0;
}
Output Verified by compiling and running
max = 99
The maximum of n elements is the larger of the first element and the maximum of the other n − 1. a + 1 passes the rest of the array without copying it.
Print the first 10 Fibonacci numbers with an iterative function – no exponential recursion.
Solution
main.c
#include <stdio.h>
void print_fib(int count) {
long long a = 0, b = 1;
for (int i = 0; i < count; i++) {
printf("%lld ", a);
long long next = a + b;
a = b;
b = next;
}
printf("\n");
}
int main(void) {
print_fib(10);
return 0;
}
Output Verified by compiling and running
0 1 1 2 3 5 8 13 21 34
Keep only the last two numbers and slide them forward: O(n) time, O(1) memory. The naive recursive version makes an exponential number of calls.
Print the binary form of a number with a recursive function.
Solution
main.c
#include <stdio.h>
void to_binary(unsigned n) {
if (n > 1)
to_binary(n / 2); /* print the higher bits first */
putchar('0' + (int) (n % 2));
}
int main(void) {
unsigned tests[] = {0, 5, 10, 255};
for (int i = 0; i < 4; i++) {
printf("%u = ", tests[i]);
to_binary(tests[i]);
putchar('\n');
}
return 0;
}
Output Verified by compiling and running
0 = 0
5 = 101
10 = 1010
255 = 11111111
The last binary digit is n % 2, but it must be printed last. Recursing on n / 2 before printing puts the digits in the right order with no array. The n > 1 test makes 0 print as "0".
Write is_palindrome() for numbers by reversing the digits.
Solution
main.c
#include <stdio.h>
int reverse_digits(int n) {
int r = 0;
while (n > 0) {
r = r * 10 + n % 10;
n /= 10;
}
return r;
}
int is_palindrome(int n) {
return n >= 0 && reverse_digits(n) == n;
}
int main(void) {
int tests[] = {121, 123, 1221, 10};
for (int i = 0; i < 4; i++)
printf("%d %s\n", tests[i], is_palindrome(tests[i]) ? "yes" : "no");
return 0;
}
Output Verified by compiling and running
121 yes
123 no
1221 yes
10 no
n % 10 takes the last digit and n / 10 drops it; building r from those digits reverses the number. 10 reversed is 1, so it is not a palindrome.
Print every Armstrong number from 1 to 1000 (a k-digit number equal to the sum of its digits each raised to the power k), using small helper functions.
Solution
main.c
#include <stdio.h>
int count_digits(int n) {
int c = 0;
do {
c++;
n /= 10;
} while (n > 0);
return c;
}
int ipow(int base, int exp) {
int r = 1;
while (exp-- > 0)
r *= base;
return r;
}
int is_armstrong(int n) {
int k = count_digits(n), sum = 0;
for (int m = n; m > 0; m /= 10)
sum += ipow(m % 10, k);
return sum == n;
}
int main(void) {
for (int n = 1; n <= 1000; n++)
if (is_armstrong(n))
printf("%d ", n);
printf("\n");
return 0;
}
Output Verified by compiling and running
1 2 3 4 5 6 7 8 9 153 370 371 407
Three tiny functions each do one job, which keeps is_armstrong() readable. 153 = 1³ + 5³ + 3³. An integer ipow() avoids the rounding errors of pow() from <math.h>.
Write a reusable count_if() that counts the elements for which a given test function returns true.
Solution
main.c
#include <stdbool.h>
#include <stdio.h>
size_t count_if(const int *a, size_t n, bool (*pred)(int)) {
size_t count = 0;
for (size_t i = 0; i < n; i++)
if (pred(a[i]))
count++;
return count;
}
static bool is_even(int x) { return x % 2 == 0; }
static bool is_negative(int x) { return x < 0; }
int main(void) {
int a[] = {4, -3, 7, -8, 0, 12, -1};
size_t n = sizeof a / sizeof a[0];
printf("even: %zu, negative: %zu\n", count_if(a, n, is_even), count_if(a, n, is_negative));
return 0;
}
Output Verified by compiling and running
even: 4, negative: 3
The loop is written once; the test is passed in as a function pointer. Even numbers: 4, −8, 0, 12. Negative: −3, −8, −1. This is the same idea as the comparator you give to qsort().
We use Google Analytics cookies to see how LearnFrenzy is used and make it better, and Google AdSense to keep it free.
No analytics or ad cookies are set until you accept. Privacy Policy
·