C Programming

ASSIGNMENT 5

Assignment

1. Given an array of n integers, the task is to find the third largest element using C
language.

#include <stdio.h>
#include <limits.h>
void findThirdLargest(int arr[], int n) {
// There must be at least three elements
if (n < 3) {
printf("Invalid Input\n");
return;
}
// Initialize the three largest elements to minimum possible integer value int
first = INT_MIN, second = INT_MIN, third = INT_MIN;
for (int i = 0; i < n; i++) {
// If current element is greater than first
if (arr[i] > first) {
third = second;
second = first;
first = arr[i]; } // If current element is between first and second
else if (arr[i] > second && arr[i] != first) {
third = second;
second = arr[i]; }
// If current element is between second and third
else if (arr[i] > third && arr[i] != second && arr[i] != first)
{
third = arr[i];
}
}
if (third == INT_MIN)
printf("Third largest element does not exist\n");
else printf("The third largest element is %d\n", third);
}
int main() {
int arr[] = {12, 13, 1, 10, 34, 16};
int n = sizeof(arr) / sizeof(arr[0]);
findThirdLargest(arr, n);
 return 0;
}

Examples :
Input: arr[] = [2, 4, 1, 3, 5]
Output: 3

Key Logic Steps

a. Initialization: Use three variables (first, second, third) initialized to INT_MIN from the
<limits.h> library.
b. Single Pass: Traverse the array. For each element:
o If it's greater than first, shift values down (third = second, second = first) and
update first.
o If it's smaller than first but larger than second, shift second down to third and
update second.
o If it's smaller than second but larger than third, simply update third.
c. Distinct Values: Using && arr[i] != first ensures that duplicate values are not counted
as the next largest distinct element.
d. Edge Case: If the array has fewer than three elements, the third largest cannot be
determined.

2. Reverse an Array in groups

To reverse an array in groups of size (k) in C, you can iterate through the array in
steps of (k) and reverse each sub-segment in place. If the final group has fewer
than (k) elements, the remaining elements are reversed as they are

#include <stdio.h>
// Helper function to reverse a segment of the array [left,
right]
void reverse(int arr[], int left, int right)
{ while (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp; left++; right--;
}
} // Function to reverse the array in groups of size k void
reverseInGroups(int arr[], int n, int k) {
for (int i = 0; i < n; i += k) { int left = i;
// The right boundary is either (i + k - 1) or the last index of
the array int
right = (i + k - 1 < n - 1) ? (i + k - 1) : (n - 1);
reverse(arr, left, right);
}
}
int main() {
 int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
int k = 3;
int n = sizeof(arr) / sizeof(arr[0]);
reverseInGroups(arr, n, k);
printf("Array after reversing in groups of %d: ", k);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}

Examples:
Input: arr[] = [1, 2, 3, 4, 5, 6, 7, 8], k = 3
Output: [3, 2, 1, 6, 5, 4, 8, 7]
Explanation: Elements is reversed: [1, 2, 3] → [3, 2, 1], [4, 5, 6] → [6, 5, 4], and the
last group [7, 8](size < 3) is reversed as [8, 7].

Key Logic
a. Iteration: The main loop jumps by k at each step (i += k) to reach the start of every
group.
b. Boundary Handling: To avoid going out of bounds, the end of the current group is
calculated as min(i + k - 1, n - 1).
c. In-Place Swap: For each group, two pointers (start and end) move toward the
middle, swapping elements using a temporary variable.

3. Rotate an Array by d - Counterclockwise or Left

To rotate an array by (d) positions counterclockwise (left) in C, you can use several
methods ranging from a simple iterative approach to an optimized "reversal
algorithm

Method 1: The Reversal Algorithm (Optimal)

This is the most efficient way to rotate an array in-place with (O(n)) time complexity
and (O(1)) extra space.
1. Reverse the first (d) elements.
2. Reverse the remaining (n - d) elements.
3. Reverse the entire array.

Method 2: Using a Temporary Array

This approach is easier to understand but uses \(O(d)\) extra space. [1]
Step 1: Store the first \(d\) elements in a temporary array.
Step 2: Shift the rest of the array elements to the left by \(d\) positions.
Step 3: Copy the elements from the temporary array back to the end of the original
array.
Method 3: Rotate One by One (Naive)
This method shifts all elements one position to the left, repeating the process (d)
times.
Time Complexity: (O(n times d)).
Space Complexity: (O(1))

#include <stdio.h>
// Function to reverse a section of the array
void reverse(int arr[], int start, int end) {
while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp; start++; end--; }
}
// Optimized left rotation
void leftRotate(int arr[], int d, int n) {
if (n == 0) return;
d = d % n;
// Handle cases where d >= n
reverse(arr, 0, d - 1); // Step 1: Reverse first d
reverse(arr, d, n - 1); // Step 2: Reverse remaining
reverse(arr, 0, n - 1);
// Step 3: Reverse all
} int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
int d = 2;
leftRotate(arr, d, n);
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}

Output: 3 4 5 6 7 1 2

4. Given an integer array, find a maximum product of a triplet in the array using C
language.
To find the maximum product of a triplet in an integer array using C, the most
efficient approach is to identify the three largest numbers and the two smallest
numbers (which could be negative). The maximum product will be the greater of

The product of the three largest numbers (max1 *max2 * max3).

The product of the two smallest numbers and the largest number

(min1 * min2 * max1)

#include <stdio.h>

#include <limits.h>

long long maxTripletProduct(int arr[], int n) {

if (n < 3) return -1; // Initialize 3 largest and 2 smallest

values

int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;

int min1 = INT_MAX, min2 = INT_MAX;

for (int i = 0; i < n; i++) { // Update 3 largest values

if (arr[i] > max1) {

max3 = max2; max2 = max1;

max1 = arr[i]; }

else if (arr[i] > max2) {

max3 = max2;

max2 = arr[i]; }

else if (arr[i] > max3) {

max3 = arr[i]; } // Update 2 smallest values

if (arr[i] < min1) { min2 = min1; min1 = arr[i];

else if (arr[i] < min2) { min2 = arr[i];

long long prod1 = (long long)max1 * max2 * max3;

long long prod2 = (long long)min1 * min2 * max1;

return (prod1 > prod2) ? prod1 : prod2; }

int main() {

int arr[] = {-10, -10, 5, 2};

int n = sizeof(arr) / sizeof(arr[0]);

printf("Maximum Product: %lld\n", maxTripletProduct(arr, n));

return 0;

}
Examples:
Input: arr[ ] = [10, 3, 5, 6, 20]
Output: 1200
Explanation: Multiplication of 10, 6 and 20
Input: arr[ ] = [-10, -3, -5, -6, -20]
Output: -90
Input: arr[ ] = [1, -4, 3, -6, 7, 0]
Output: 168

5. Move all Zeros to End of Array

Given an array of integers arr[], move all the zeros to the end of the array while
maintaining the relative order of all non-zero elements.

Examples:
Input: arr[] = [1, 2, 0, 4, 3, 0, 5, 0]
Output: [1, 2, 4, 3, 5, 0, 0, 0]

The Strategy

Traverse the array: Use a counter to track the position where the next non-zero
element should go.
Shift non-zeros: Whenever you encounter a non-zero number, place it at the
counter's index and increment the counter.
Fill remaining zeros: Once the loop finished, all non-zero elements are at the front.
Fill the remaining spots from the current counter index to the end of the array with

#include <stdio.h>

void moveZerosToEnd(int arr[], int n) {

int count = 0; // Index of next non-zero element // Step 1:

Move all non-zero elements to the front

for (int i = 0; i < n; i++) {

if (arr[i] != 0) {

arr[count++] = arr[i];

} // Step 2: Fill the rest of the array with zeros

while (count < n) {

 arr[count++] = 0;

int main() {

int arr[] = {1, 0, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0};

int n = sizeof(arr) / sizeof(arr[0]);

moveZerosToEnd(arr, n);

printf("Modified array: ");

for (int i = 0; i < n; i++) {

printf("%d ", arr[i]);

return 0;

6. Find 0 with Farthest 1s in a Binary Array

Algorithm Strategy
The most efficient way to solve this is a two-pass approach with \(O(N)\) time
complexity:
a. First Pass (Left-to-Right): Calculate the distance of each 0 to the nearest 1 on its
left.
b. Second Pass (Right-to-Left): Calculate the distance of each 0 to the nearest 1 on
its right and keep the minimum of the two directions for each index.
c. Result: The maximum value among all these calculated minimum distances is
your answer

#include <stdio.h>
#include <limits.h>
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
void findFarthestZero(int arr[], int n) {
int dist[n];
int lastOne = -1;
// First Pass: Distance to nearest '1' on the left
for (int i = 0; i < n; i++) {
if (arr[i] == 1) {
lastOne = i;
dist[i] = 0; }
else {
dist[i] = (lastOne == -1) ? INT_MAX : (i - lastOne);
}
 } // Second Pass: Distance to nearest '1' on the right
lastOne = -1;
int maxDist = -1;
int targetIndex = -1;
for (int i = n - 1; i >= 0; i--) {
if (arr[i] == 1) { lastOne = i; }
else {
int currentDistToRight = (lastOne == -1) ? INT_MAX : (lastOne -
i);
// The actual distance to the nearest '1' is the min of left
and right
int actualDist = MIN(dist[i], currentDistToRight);
if (actualDist > maxDist) { maxDist = actualDist;
targetIndex = i;
}
}
}
if (targetIndex != -1) {
printf("The 0 at index %d is farthest from its nearest 1s
(Distance: %d)\n", targetIndex, maxDist);
}
else {
printf("No 0 found or no 1s present in the array.\n");
}
}
int main() {
int arr[] = {1, 0, 0, 0, 1, 0, 1}; // Example array
int n = sizeof(arr) / sizeof(arr[0]);
findFarthestZero(arr, n);
return 0;
}

Key Considerations
 Edge Cases: If the array starts or ends with zeros (e.g., 0, 0, 1, 0), the distance for
those zeros is only constrained by a 1 on one side. The INT_MAX check ensures we
handle these "open-ended" distances correctly.
 Time Complexity: (O(N)), as we traverse the array only twice.
 Space Complexity: (O(N)) for the dist array. This can be reduced to (O(1)) if you only
store the index of the previous 1 and calculate the distance on the fly during a
second pass
7. Common Slot for Meeting of Two Persons

To find a common meeting slot for two people in C, the most efficient approach is

the Two-Pointer Algorithm. This method finds the intersection of two sorted lists

of availability intervals in (O(N + M)) time.

Examples:
Input: slt1[][] = [[10,50], [60,120], [140,210]], slt2[][] = [[0,15], [60,70]], d = 8
Output: [60,68]
Explanation: The only overlap is [60,70] (10 minutes), which is enough for an 8-
minute meeting, so answer is [60,68]

The Core Logic

A common slot between two intervals, ([s1, e1]) and ([s2, e2]), is defined by: [1]
Start Time: (max(s1, s2))
End Time: (min(e1, e2))
If the End Time Start Time greater than les than ) Duration, you have found a
valid meeting slot

#include <stdio.h>
#include <stdlib.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
typedef struct {
int start;
int end; } Slot;
// Function to find the earliest common slot
void findEarliestSlot(Slot slots1[], int n1, Slot slots2[],
int n2, int duration) {
int i = 0, j = 0;
while (i < n1 && j < n2) {
// Calculate the intersection of the current two slots
int commonStart = MAX(slots1[i].start, slots2[j].start); int
commonEnd = MIN(slots1[i].end, slots2[j].end); // Check if the
intersection is long enough
if (commonEnd - commonStart >= duration) {
printf("Earliest Slot: [%d, %d]\n", commonStart, commonStart +
duration);
return; } // Advance the pointer of the slot that ends earlier
if (slots1[i].end < slots2[j].end) {
i++; }
else {
j++; }
} printf("No common slot found.\n"); }
 int main() { // Note: Slots must be sorted by start time Slot
person1[] = {{10, 50}, {60, 120}, {140, 210}};
Slot person2[] = {{0, 15}, {60, 70}};
int duration = 8;
int n1 = sizeof(person1) / sizeof(person1[0]);
int n2 = sizeof(person2) / sizeof(person2[0]);
findEarliestSlot(person1, n1, person2, n2, duration);
return 0;
}

Steps Explained

a. Sort Intervals: Ensure both people's availability lists are sorted by start time. In many
competitive programming problems (like on LeetCode), this is a prerequisite.
b. Initialize Pointers: Use two indices (\(i\) and \(j\)) to track current positions in each
person's schedule.
c. Find Intersection: At each step, calculate the potential overlap. If the commonEnd -
commonStart meets the duration, return that slot immediately as the "earliest"
option.
d. Pointer Movement: Move the pointer of the interval that finishes earlier. This is
crucial because that specific slot cannot possibly overlap with any future slots from
the other person.

8. Write a C program to find out Smallest Missing Positive Number

Given an unsorted array arr[] with both positive and negative elements, find
the smallest positive number missing from the array.
Examples:
Input: arr[] = [2, -3, 4, 1, 1, 7]
Output: 3
Explanation: 3 is the smallest positive number missing from the array.

[Naive approach] By Sorting - O(n*log n) Time and O(1) Space

The idea is to sort the array and assume the missing number as 1. Now, iterate
over the array and for each element arr[i],
If arr[i] == missing number, then increment missing number by 1.
If arr[i] < missing number, then continue to search for the missing number.
If arr[i] > missing number, then break and return the missing numbe

#include <stdio.h>

int cmp(const int *a, const int *b) {

return (*a - *b);
}
int missingNumber(int arr[], int size) {

// sort the array

qsort(arr, size, sizeof(int), (int(*)(const void*, const void*))cmp);

// res will hold the current smallest missing number,

// initially set to 1
int res = 1;
for (int i = 0; i < size; i++) {

// If we have found 'res' in the array,

// 'res' is no longer missing, so increment it
if (arr[i] == res) {
res++;
}

// If the current element is larger than 'res',

// 'res' cannot be found in the array,
// so it is our final answer
else if (arr[i] > res) {
break;
}
}
return res;
}

int main() {
int arr[] = {2, -3, 4, 1, 1, 7};
int size = sizeof(arr) / sizeof(arr[0]);

printf("%d", missingNumber(arr, size));

return 0;
}

Output 3
 9. Write a C program to find out Next Smallest Palindrome.

To find the next smallest palindrome larger than a given number in C, you can
use an efficient (O(n)) approach that manipulates the digits directly rather than
checking every subsequent number.

Input: num[] = [9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2]

Output: [9, 4, 1, 8, 8, 0, 8, 8, 1, 4, 9]
Explanation: Next smallest palindrome is 9 4 1 8 8 0 8 8 1 4 9
#include <stdio.h>

#include <string.h>

#include <stdbool.h>

// Helper to check if all digits in the string are '9'

bool areAll9s(char* num, int n) {

for (int i = 0; i < n; i++)

if (num[i] != '9') return false;

return true;

void findNextPalindrome(char* num) {

int n = strlen(num); // Case 1: All 9s (e.g., 999 -> 1001)

if (areAll9s(num, n)) {

printf("1"); for (int i = 1; i < n; i++)

printf("0"); printf("1\n");

return; } // Case 2 & 3: General handling

int mid = n / 2;

int i = mid - 1;

int j = (n % 2 == 0) ? mid : mid + 1; // Skip digits that are

already identical from center outwards

bool leftSmaller = false;

while (i >= 0 && num[i] == num[j]) {

i--;

j++; } // Check if we need to increment the middle digit

if (i < 0 || num[i] < num[j]) {

leftSmaller = true; } // Mirror the left side to the right

side

int left = mid - 1;

int right = (n % 2 == 0) ? mid : mid + 1;

while (left >= 0) {

num[right++] = num[left--];

} // If mirroring wasn't enough, increment the middle and

propagate carry

if (leftSmaller) {

int carry = 1;

i = mid - 1;

if (n % 2 == 1) {

int val = (num[mid] - '0') + carry;

carry = val / 10;

num[mid] = (val % 10) + '0';

j = mid + 1; } else { j = mid; }

while (i >= 0) {

int val = (num[i] - '0') + carry;

carry = val / 10;

num[i] = (val % 10) + '0';

num[j++] = num[i--]; // Copy incremented left to right } }

printf("%s\n", num); }

int main() {

char num1[] = "12345";

char num2[] = "999";

char num3[] = "1221";

printf("Next palindrome of 12345: ");

findNextPalindrome(num1);

printf("Next palindrome of 999: ");

findNextPalindrome(num2);

printf("Next palindrome of 1221: ");

findNextPalindrome(num3);
 return 0; }

Logical Steps Explained

1. Handle Special Case (All 9s): If the input consists only of 9s (like "99"), the next
smallest palindrome will always be (1) followed by (n-1) zeros and then another (1)
(like "101").
2. Mirroring: Copy the left half of the string to the right half. For "12345", mirroring the
left ("12") gives "12321".
3. Check Magnitude: Compare the mirrored number with the original. If the mirrored
version is already larger, you're done.
4. Increment and Propagate: If the mirrored number is smaller or equal, increment the
middle digit (or the middle two for even lengths) and propagate the carry toward the
left, updating the mirrored right side as you go.

10. Remove duplicates from Sorted Array

To remove duplicates from a sorted array in C, the most efficient method is the

two-pointer approach. Since the array is already sorted, all identical elements

are adjacent, allowing you to remove them in-place with a single pass

The Core Logic

You use two indices:
Unique Pointer (j): Tracks the position of the last unique element found.
Iterator Pointer (i): Scans through the entire array to compare elements.

When a new unique element is found ((arr[i] not eq to arr[j])), you

increment (j) and move that element to the jth position.
#include <stdio.h> /** * Removes duplicates from a sorted
array in-place. * Returns the number of unique elements (the
new size). */

int removeDuplicates(int arr[], int n) {

if (n == 0 || n == 1) {

return n;

int j = 0; // Index of the last unique element

for (int i = 1; i < n; i++) { // If the current element is

different from the last unique one

if (arr[i] != arr[j]) {

j++;
 arr[j] = arr[i]; // Move it to the next available unique slot
} }

return j + 1; // Number of unique elements is index + 1 }

int main() {

int arr[] = {1, 2, 2, 3, 4, 4, 4, 5};

int n = sizeof(arr) / sizeof(arr[0]);

int newSize = removeDuplicates(arr, n);

printf("Array after removing duplicates: ");

for (int i = 0; i < newSize; i++) {

printf("%d ", arr[i]);

return 0;

11. Write a Program to Replace all 0’s with 1’s in a Number.

#include <math.h>
#include <stdio.h>

int main()
{
int N = 102301;

int ans = 0;
int i = 0;
while (N != 0) {
// Condition to change value
if (N % 10 == 0)
ans = ans + 1 * pow(10, i);
else
ans = ans + (N % 10) * pow(10, i);

N = N / 10;
i++;
}
 printf("%d", ans);

return 0;
}
Output
112311

12. Write a C Program to find the Maximum and minimum of two numbers without
using any loop or condition.

// C Program to check
// Maximum and Minimum
// Between two numbers
// Without any condition or loop
#include <stdio.h>
#include <stdlib.h>

int main()
{
int a = 55, b = 23;

// return maximum among the two numbers

printf("max = %d\n", ((a + b) + abs(a - b)) / 2);

// return minimum among the two numbers

printf("min = %d", ((a + b) - abs(a - b)) / 2);

return 0;
}

Output
Max = 55
Min = 23
[Link] a program to check the repeating elements in C.

#include <stdio.h>

int Sort(int arr[], int size)

{
for (int i = 0; i < size - 1; i++) {

for (int j = 0; j < size - i - 1; j++) {

if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

// find repeating element

void findRepeating(int arr[], int n)
{
int count = 0;
for (int i = 0; i < n; i++) {

int flag = 0;
while (i < n - 1 && arr[i] == arr[i + 1]) {
flag = 1;
i++;
}
if (flag)
printf("%d ", (arr[i - 1]));
}

return;
}

int main()
{
int arr[] = { 1, 3, 4, 1, 2, 3, 5, 5 };

int n = sizeof(arr) / sizeof(arr[0]);

 Sort(arr,n);

findRepeating(arr,n);

return 0;
}
Output
135

14. Write a Program to sort First half in Ascending order and the Second in
Descending order.

// C Program for Sorting

// First half in Ascending order

// and Second Descending order

#include <stdio.h>

void Sort_asc_desc(int arr[], int n)

int temp;

for (int i = 0; i < n - 1; i++) {

for (int j = i + 1; j < n; j++) {

if (arr[i] > arr[j]) {

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}
 // printing first half in ascending order

for (int i = 0; i < n / 2; i++)

printf("%d ", arr[i]);

// printing second half in descending order

for (int j = n - 1; j >= n / 2; j--)

printf("%d ", arr[j]);

int main()

int arr[] = { 11, 23, 42, 16, 83, 73, 59 };

int N = sizeof(arr) / sizeof(arr[0]);

Sort_asc_desc(arr, N);

return 0;

Output

11 16 23 83 73 59 42

15. Write a Program to find the transpose of a matrix.

#include <stdio.h>

// This function stores transpose of A[][] in B[][]

void transpose(int N, int M, int A[M][N], int B[N][M])

int i, j;

for (i = 0; i < N; i++)

for (j = 0; j < M; j++)

B[i][j] = A[j][i];

int main()

int M = 3;

int N = 4;

int A[3][4] = { { 1, 1, 1, 1 },

{ 2, 2, 2, 2 },

{ 3, 3, 3, 3 } };

// Note dimensions of B[][]

int B[N][M], i, j;

transpose(N, M, A, B);

printf("Result matrix is \n");

 for (i = 0; i < N; i++) {

for (j = 0; j < M; j++)

printf("%d ", B[i][j]);

printf("\n");

return 0;

Output

123

123

123

123