An array is a data structure that stores a collection of elements, typically of the same data type, in a contiguous block of memory. Arrays are indexed, which means each element can be accessed by its position in the array, starting from zero.
Characteristics:
Fixed Size: The size of an array is defined at the time of its declaration and cannot be changed.
Homogeneous Elements: All elements in an array are of the same data type.
Contiguous Memory Allocation: Elements are stored in continuous memory locations.
Indexed Access: Each element can be accessed using its index.
Types of Arrays
Single-Dimensional Arrays
A single-dimensional array, also known as a one-dimensional array, is a list of elements stored in a single row.
Example in C:
int numbers[5] = {1, 2, 3, 4, 5};
Multi-Dimensional Arrays
Multi-dimensional arrays consist of more than one row or column. The most common multi-dimensional array is the two-dimensional array.
Example in C:
int matrix[3][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
Advantages:
Fast Access: Elements can be accessed quickly using their index.
Ease of Iteration: Arrays can be easily iterated using loops.
Memory Efficiency: Arrays have minimal overhead compared to other data structures.
Disadvantages:
Fixed Size: The size of the array cannot be changed once defined.
Wasted Memory: If the array size is overestimated, memory may be wasted.
Costly Insertion/Deletion: Inserting or deleting elements can be costly as it may require shifting elements.
Explanation of Row Major Order
Row major order is a method for storing multi-dimensional arrays in linear memory. In this arrangement, the elements of each row of a multi-dimensional array are stored in contiguous memory locations. This means that the complete row is stored before the next row begins.
For example, consider a 2-D array:
int matrix[3][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
In row major order, the elements will be stored in memory as:
1, 2, 3, 4, 5, 6, 7, 8, 9
Address Calculation Formula for 1-D and 2-D Arrays
1-D Array
For a 1-D array, the address of an element can be calculated using the formula:
Address of A[i] = Base_Address + (i * Size_of_Element)
Where:
Base_Address
is the address of the first element of the array.i
is the index of the element.Size_of_Element
is the size of each element in the array (e.g., 4 bytes for anint
).
2-D Array
For a 2-D array stored in row major order, the address of an element can be calculated using the formula:
Address of A[i][j] = Base_Address + [(i * Number_of_Columns) + j] * Size_of_Element
Where:
Base_Address
is the address of the first element of the array.i
is the row index.j
is the column index.Number_of_Columns
is the total number of columns in the 2-D array.Size_of_Element
is the size of each element in the array.
1-D Array Example
Consider a 1-D array int arr[5] = {10, 20, 30, 40, 50};
with Base_Address = 1000
and Size_of_Element = 4 bytes
.
To find the address of arr[3]
:
Address of arr[3] = 1000 + (3 * 4) = 1000 + 12 = 1012
2-D Array Example
Consider a 2-D array int matrix[3][3]
with Base_Address = 2000
and Size_of_Element = 4 bytes
.
To find the address of matrix[2][1]
:
Address of matrix[2][1] = 2000 + [(2 * 3) + 1] * 4
= 2000 + [6 + 1] * 4
= 2000 + 7 * 4
= 2000 + 28
= 2028
Dynamic Memory Allocation (DMA) – 1-D and 2-D Arrays
Dynamic memory allocation allows programs to allocate memory during runtime. This is particularly useful when the size of the data structure (such as an array) is not known at compile time. The allocated memory can be resized or freed as needed, enabling efficient use of memory.
Allocating Memory for 1-D Arrays Dynamically
To allocate memory for a 1-D array dynamically, you can use the malloc()
or calloc()
functions in C.
malloc()
allocates a specified number of bytes and returns a pointer to the first byte of the allocated memory.
int *arr;
int n = 5;
arr = (int *)malloc(n * sizeof(int));
Allocating Memory for 2-D Arrays Dynamically
To allocate memory for a 2-D array dynamically, you typically use an array of pointers.
int **matrix;
int rows = 3, cols = 3;
matrix = (int **)malloc(rows * sizeof(int *));
for (int i = 0; i < rows; i++) {
matrix[i] = (int *)malloc(cols * sizeof(int));
}
Allocating Memory for 2-D Jagged Arrays Dynamically
A jagged array, also known as an array of arrays, is a 2-D array where the rows can have different lengths.
int **jaggedArray;
int rows = 3;
jaggedArray = (int **)malloc(rows * sizeof(int *));
jaggedArray[0] = (int *)malloc(2 * sizeof(int)); // 1st row with 2 elements
jaggedArray[1] = (int *)malloc(3 * sizeof(int)); // 2nd row with 3 elements
jaggedArray[2] = (int *)malloc(4 * sizeof(int)); // 3rd row with 4 elements
To avoid memory leaks, it is crucial to deallocate memory that was allocated dynamically using the free()
function.
Deallocating 1-D Array
free(arr);
Deallocating 2-D Array
for (int i = 0; i < rows; i++) {
free(matrix[i]);
}
free(matrix);
Deallocating 2-D Jagged Array
for (int i = 0; i < rows; i++) {
free(jaggedArray[i]);
}
free(jaggedArray);
Pointers to Array, Pointer to Structure, Array of Pointers
Pointers are variables that store the memory address of another variable. They are powerful tools in programming because they allow for direct memory access and manipulation, which can lead to more efficient and flexible code. Pointers are essential for dynamic memory allocation, handling arrays, and structures.
Pointers to Arrays and Their Usage
A pointer to an array holds the address of the first element of the array. It can be used to iterate over the array elements or to pass arrays to functions efficiently.
int arr[5] = {1, 2, 3, 4, 5};
int *ptr = arr; // ptr points to the first element of arr
for (int i = 0; i < 5; i++) {
printf("%d ", *(ptr + i)); // Access array elements using the pointer
}
Pointer to Structure and Accessing Structure Members Using Pointers
A pointer to a structure stores the address of a structure variable. You can access the structure members using the arrow operator (->
).
struct Point {
int x;
int y;
};
struct Point p1 = {10, 20};
struct Point *ptr = &p1;
printf("x = %d, y = %d\n", ptr->x, ptr->y); // Access members using the pointer
Arrays of Pointers and Their Applications
An array of pointers is a collection of pointers, each pointing to a different variable or memory block. This is useful for creating arrays of strings, arrays of dynamic arrays, or managing multiple dynamic memory allocations.
Example: Array of Strings
char *arr[] = {"Hello", "World", "Pointers", "in", "C"};
int n = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < n; i++) {
printf("%s ", arr[i]); // Print each string using the array of pointers
}
Example: Array of Dynamic Arrays
int *arr[3];
int sizes[] = {2, 3, 4};
// Allocating memory for each row
for (int i = 0; i < 3; i++) {
arr[i] = (int *)malloc(sizes[i] * sizeof(int));
}
// Initializing and printing values
for (int i = 0; i < 3; i++) {
for (int j = 0; j < sizes[i]; j++) {
arr[i][j] = i + j;
printf("%d ", arr[i][j]);
}
printf("\n");
}
// Freeing allocated memory
for (int i = 0; i < 3; i++) {
free(arr[i]);
}
Pointer to Array Example
int arr[3] = {10, 20, 30};
int (*ptr)[3] = &arr; // Pointer to the entire array
for (int i = 0; i < 3; i++) {
printf("%d ", (*ptr)[i]); // Access elements using pointer to array
}
Pointer to Structure Example
struct Student {
int id;
char name[20];
};
struct Student s1 = {1, "John Doe"};
struct Student *ptr = &s1;
printf("ID: %d, Name: %s\n", ptr->id, ptr->name); // Access members using pointer
Array of Pointers Example
int a = 10, b = 20, c = 30;
int *arr[3] = {&a, &b, &c}; // Array of pointers to integers
for (int i = 0; i < 3; i++) {
printf("%d ", *arr[i]); // Print values using array of pointers
}
Array Abstract Data Type (ADT)
An Abstract Data Type (ADT) is a mathematical model for data types, where a data type is defined by its behavior (semantics) from the point of view of a user, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. An ADT encapsulates the underlying data structure, providing an interface to the user while hiding the implementation details.
Importance of ADTs:
Encapsulation: Hides the implementation details and exposes only necessary operations.
Modularity: Promotes modular design, making code easier to manage and maintain.
Reusability: ADTs can be reused across different programs and projects.
Interchangeability: Allows changing the underlying data structure without altering the external interface.
An array ADT encapsulates an array and provides a set of operations that can be performed on the array. Here is how you can implement an array as an ADT in C.
Structure Definition
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int *data; // Pointer to the array elements
int size; // Current number of elements
int capacity; // Maximum capacity of the array
} ArrayADT;
Initialize Array ADT
ArrayADT* createArray(int capacity) {
ArrayADT *arr = (ArrayADT *)malloc(sizeof(ArrayADT));
arr->data = (int *)malloc(capacity * sizeof(int));
arr->size = 0;
arr->capacity = capacity;
return arr;
}
Operations on Array ADT
Insertion
void insert(ArrayADT *arr, int element) {
if (arr->size == arr->capacity) {
printf("Array is full\n");
return;
}
arr->data[arr->size] = element;
arr->size++;
}
Deletion
void delete(ArrayADT *arr, int index) {
if (index < 0 || index >= arr->size) {
printf("Invalid index\n");
return;
}
for (int i = index; i < arr->size - 1; i++) {
arr->data[i] = arr->data[i + 1];
}
arr->size--;
}
Traversal
void traverse(ArrayADT *arr) {
for (int i = 0; i < arr->size; i++) {
printf("%d ", arr->data[i]);
}
printf("\n");
}
Search
int search(ArrayADT *arr, int element) {
for (int i = 0; i < arr->size; i++) {
if (arr->data[i] == element) {
return i; // Element found, return its index
}
}
return -1; // Element not found
}
Implementing an Enhanced Array ADT
Implement an Array Abstract Data Type (ADT) in a programming language of your choice that supports the following operations:
Creation: Initialize the array with a given capacity.
Insertion:
Insert an element at the end of the array.
Insert an element at a specified position (middle of the array).
Deletion:
Delete an element from the end of the array.
Delete an element from a specified position (middle of the array).
Search: Find the index of a specified element.
Data Retrieval:
Retrieve a single value at a specified index.
Retrieve a sub-array from a specified start index to an end index (not inclusive).
Free Memory: Deallocate the memory used by the array.
Increase Capacity: Automatically increase the capacity of the array if it becomes full.
ADT Structure
typedef struct {
int *data; // Pointer to the array elements
int size; // Current number of elements
int capacity; // Maximum capacity of the array
} ArrayADT;
Function Signatures
Create Array
ArrayADT* createArray(int capacity);
Insert at End
void insertAtEnd(ArrayADT *arr, int element);
Insert at Position
void insertAtPosition(ArrayADT *arr, int element, int position);
Delete from End
void deleteFromEnd(ArrayADT *arr);
Delete from Position
void deleteFromPosition(ArrayADT *arr, int position);
Search
int search(ArrayADT *arr, int element);
Retrieve Single Value
int retrieveValue(ArrayADT *arr, int index);
Retrieve Sub-Array
ArrayADT* retrieveSubArray(ArrayADT *arr, int from, int to);
Free Memory
void freeArray(ArrayADT *arr);
Increase Capacity
void increaseCapacity(ArrayADT *arr);
Pseudo Code for Each Function
Create Array
function createArray(capacity): arr = allocate memory for ArrayADT arr.data = allocate memory for capacity elements arr.size = 0 arr.capacity = capacity return arr
Insert at End
function insertAtEnd(arr, element): if arr.size == arr.capacity: increaseCapacity(arr) arr.data[arr.size] = element arr.size = arr.size + 1
Insert at Position
function insertAtPosition(arr, element, position): if arr.size == arr.capacity: increaseCapacity(arr) if position < 0 or position > arr.size: print "Invalid position" return for i = arr.size to position step -1: arr.data[i] = arr.data[i - 1] arr.data[position] = element arr.size = arr.size + 1
Delete from End
function deleteFromEnd(arr): if arr.size == 0: print "Array is empty" return arr.size = arr.size - 1
Delete from Position
function deleteFromPosition(arr, position): if position < 0 or position >= arr.size: print "Invalid position" return for i = position to arr.size - 2: arr.data[i] = arr.data[i + 1] arr.size = arr.size - 1
Search
function search(arr, element): for i = 0 to arr.size - 1: if arr.data[i] == element: return i return -1
Retrieve Single Value
function retrieveValue(arr, index): if index < 0 or index >= arr.size: print "Invalid index" return -1 return arr.data[index]
Retrieve Sub-Array
function retrieveSubArray(arr, from, to): if from < 0 or to > arr.size or from >= to: print "Invalid indices" return null subArray = createArray(to - from) for i = from to to - 1: insertAtEnd(subArray, arr.data[i]) return subArray
Free Memory
function freeArray(arr): free(arr.data) free(arr)
Increase Capacity
function increaseCapacity(arr): newCapacity = arr.capacity * 2 newData = allocate memory for newCapacity elements for i = 0 to arr.size - 1: newData[i] = arr.data[i] free(arr.data) arr.data = newData arr.capacity = newCapacity
Instructions
Implement the ArrayADT structure and each function in your chosen programming language.
Ensure that your program handles edge cases, such as inserting or deleting from an empty array or inserting/deleting at invalid positions.
Test your implementation with various inputs to verify correctness and robustness.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int *data; // Pointer to the array elements
int size; // Current number of elements
int capacity; // Maximum capacity of the array
} ArrayADT;
// Function to create an array with a given capacity
ArrayADT* createArray(int capacity) {
ArrayADT *arr = (ArrayADT *)malloc(sizeof(ArrayADT));
arr->data = (int *)malloc(capacity * sizeof(int));
arr->size = 0;
arr->capacity = capacity;
return arr;
}
// Function to increase the capacity of the array
void increaseCapacity(ArrayADT *arr) {
int newCapacity = arr->capacity * 2;
int *newData = (int *)malloc(newCapacity * sizeof(int));
for (int i = 0; i < arr->size; i++) {
newData[i] = arr->data[i];
}
free(arr->data);
arr->data = newData;
arr->capacity = newCapacity;
printf("Array capacity increased to %d\n", newCapacity);
}
// Function to insert an element at the end of the array
void insertAtEnd(ArrayADT *arr, int element) {
if (arr->size == arr->capacity) {
increaseCapacity(arr);
}
arr->data[arr->size] = element;
arr->size++;
}
// Function to insert an element at a specified position in the array
void insertAtPosition(ArrayADT *arr, int element, int position) {
if (position < 0 || position > arr->size) {
printf("Invalid position\n");
return;
}
if (arr->size == arr->capacity) {
increaseCapacity(arr);
}
for (int i = arr->size; i > position; i--) {
arr->data[i] = arr->data[i - 1];
}
arr->data[position] = element;
arr->size++;
}
// Function to delete an element from the end of the array
void deleteFromEnd(ArrayADT *arr) {
if (arr->size == 0) {
printf("Array is empty\n");
return;
}
arr->size--;
}
// Function to delete an element from a specified position in the array
void deleteFromPosition(ArrayADT *arr, int position) {
if (position < 0 || position >= arr->size) {
printf("Invalid position\n");
return;
}
for (int i = position; i < arr->size - 1; i++) {
arr->data[i] = arr->data[i + 1];
}
arr->size--;
}
// Function to search for an element in the array
int search(ArrayADT *arr, int element) {
for (int i = 0; i < arr->size; i++) {
if (arr->data[i] == element) {
return i;
}
}
return -1;
}
// Function to retrieve a single value from the array
int retrieveValue(ArrayADT *arr, int index) {
if (index < 0 || index >= arr->size) {
printf("Invalid index\n");
return -1;
}
return arr->data[index];
}
// Function to retrieve a sub-array from the array
ArrayADT* retrieveSubArray(ArrayADT *arr, int from, int to) {
if (from < 0 || to > arr->size || from >= to) {
printf("Invalid indices\n");
return NULL;
}
ArrayADT *subArray = createArray(to - from);
for (int i = from; i < to; i++) {
insertAtEnd(subArray, arr->data[i]);
}
return subArray;
}
// Function to free the memory allocated for the array
void freeArray(ArrayADT *arr) {
free(arr->data);
free(arr);
}
int main() {
ArrayADT *arr = createArray(3); // Start with a small capacity
// Insert more elements to exceed the initial capacity
insertAtEnd(arr, 1);
insertAtEnd(arr, 2);
insertAtEnd(arr, 3);
insertAtEnd(arr, 4); // This should trigger an increase in capacity
insertAtEnd(arr, 5); // Add more elements to ensure capacity increase
printf("Array after insertion: ");
for (int i = 0; i < arr->size; i++) {
printf("%d ", arr->data[i]);
}
printf("\n");
// Demonstrating other operations
insertAtPosition(arr, 20, 2);
printf("Array after inserting 20 at position 2: ");
for (int i = 0; i < arr->size; i++) {
printf("%d ", arr->data[i]);
}
printf("\n");
deleteFromEnd(arr);
printf("Array after deleting from end: ");
for (int i = 0; i < arr->size; i++) {
printf("%d ", arr->data[i]);
}
printf("\n");
deleteFromPosition(arr, 1);
printf("Array after deleting from position 1: ");
for (int i = 0; i < arr->size; i++) {
printf("%d ", arr->data[i]);
}
printf("\n");
int index = search(arr, 15);
if (index != -1) {
printf("Element 15 found at index %d\n", index);
} else {
printf("Element 15 not found\n");
}
int value = retrieveValue(arr, 1);
if (value != -1) {
printf("Element at index 1 is %d\n", value);
}
ArrayADT *subArray = retrieveSubArray(arr, 0, 3);
printf("Sub-array from index 0 to 3: ");
for (int i = 0; i < subArray->size; i++) {
printf("%d ", subArray->data[i]);
}
printf("\n");
freeArray(subArray);
freeArray(arr);
return 0;
}
String Representation in C
In C, strings are represented as arrays of characters terminated by a null character ('\0'
). This null character indicates the end of the string.
Basic String Operations
#include <stdio.h>
#include <string.h>
int main() {
char str1[20] = "Hello";
char str2[20] = "World";
// Concatenation without strcat
int len1 = 0;
while (str1[len1] != '\0') len1++;
int len2 = 0;
while (str2[len2] != '\0') len2++;
for (int i = 0; i < len2; i++) {
str1[len1 + i] = str2[i];
}
str1[len1 + len2] = '\0';
printf("Concatenated string (without strcat): %s\n", str1);
// Length without strlen
int length = 0;
while (str1[length] != '\0') {
length++;
}
printf("Length of concatenated string (without strlen): %d\n", length);
// Copy without strcpy
char str3[20];
int i = 0;
while (str1[i] != '\0') {
str3[i] = str1[i];
i++;
}
str3[i] = '\0';
printf("Copied string (without strcpy): %s\n", str3);
// Comparison without strcmp
int cmp = 0;
for (int j = 0; str1[j] != '\0' || str2[j] != '\0'; j++) {
if (str1[j] != str2[j]) {
cmp = str1[j] - str2[j];
break;
}
}
if (cmp == 0) {
printf("Strings are equal (without strcmp).\n");
} else if (cmp > 0) {
printf("str1 is greater than str2 (without strcmp).\n");
} else {
printf("str1 is less than str2 (without strcmp).\n");
}
// Reset strings for standard functions
strcpy(str1, "Hello");
strcpy(str2, "World");
// Concatenation with strcat
strcat(str1, str2);
printf("Concatenated string (with strcat): %s\n", str1);
// Length with strlen
length = strlen(str1);
printf("Length of concatenated string (with strlen): %d\n", length);
// Copy with strcpy
strcpy(str3, str1);
printf("Copied string (with strcpy): %s\n", str3);
// Comparison with strcmp
cmp = strcmp(str1, str2);
if (cmp == 0) {
printf("Strings are equal (with strcmp).\n");
} else if (cmp > 0) {
printf("str1 is greater than str2 (with strcmp).\n");
} else {
printf("str1 is less than str2 (with strcmp).\n");
}
return 0;
}
Introduction to Pattern Matching
Pattern matching involves finding a substring, known as a pattern, within a larger string, known as the text. This is a fundamental operation in computer science, particularly in string processing and searching algorithms. The goal is to identify all occurrences of the pattern in the text efficiently.
A pattern is a sequence of characters that we aim to find within a larger string (the text). Patterns can vary in length and complexity, and they are specified by the user or the application that requires the search.
Examples:
Pattern: "abc", Text: "abcabcabc"
- The pattern "abc" appears at positions 0, 3, and 6 in the text.
Pattern: "test", Text: "this is a test string for testing pattern matching"
- The pattern "test" appears at positions 10 and 29 in the text.
Common Pattern Matching Algorithms
Naive Algorithm
Knuth-Morris-Pratt (KMP) Algorithm
Boyer-Moore Algorithm
Naive Algorithm
The Naive algorithm for pattern matching is the simplest method. It involves sliding the pattern over the text one character at a time and checking for a match at each position. If a match is found, the starting index is recorded. If not, the pattern is shifted one position to the right, and the process is repeated until the end of the text is reached.
Steps of the Naive Algorithm:
Start at the beginning of the text.
Check if the pattern matches the substring of the text starting at the current position.
If it matches, record the starting index.
Move the starting position one character to the right.
Repeat until the end of the text is reached.
Example:
Pattern: "abc", Text: "abcabcabc"
Start at position 0: Compare "abc" with "abc" - Match found.
Move to position 1: Compare "abc" with "bca" - No match.
Move to position 2: Compare "abc" with "cab" - No match.
Move to position 3: Compare "abc" with "abc" - Match found.
Move to position 4: Compare "abc" with "bca" - No match.
Move to position 5: Compare "abc" with "cab" - No match.
Move to position 6: Compare "abc" with "abc" - Match found.
The pattern "abc" is found at positions 0, 3, and 6 in the text.
Naive Pattern Matching Algorithm in C:
#include <stdio.h>
#include <string.h>
// Function to perform naive pattern matching
void naivePatternMatching(char *text, char *pattern) {
int n = strlen(text); // Length of the text
int m = strlen(pattern); // Length of the pattern
// Slide the pattern over the text one character at a time
for (int i = 0; i <= n - m; i++) {
int j;
// Check if the pattern matches the substring of the text starting at position i
for (j = 0; j < m; j++) {
if (text[i + j] != pattern[j]) {
break;
}
}
// If the pattern matches, print the starting index
if (j == m) {
printf("Pattern found at index %d\n", i);
}
}
}
int main() {
char text[] = "abcabcabc";
char pattern[] = "abc";
naivePatternMatching(text, pattern);
return 0;
}
In this example, the naivePatternMatching
function takes the text and pattern as inputs and prints all starting indices where the pattern is found in the text. The algorithm has a time complexity of O(n * m), where n is the length of the text and m is the length of the pattern. This makes it inefficient for large texts and patterns, but it is simple and easy to understand, making it useful for smaller inputs and educational purposes.
Introduction to Polynomials
A polynomial is a mathematical expression consisting of variables (also known as indeterminates) and coefficients. Polynomials are often represented as arrays in C.
Polynomial Addition
#include <stdio.h>
#define MAX 100
typedef struct {
int coeff[MAX];
int degree;
} Polynomial;
// Function to add two polynomials
Polynomial addPolynomials(Polynomial p1, Polynomial p2) {
Polynomial result;
result.degree = (p1.degree > p2.degree) ? p1.degree : p2.degree;
for (int i = 0; i <= result.degree; i++) {
result.coeff[i] = 0;
if (i <= p1.degree) result.coeff[i] += p1.coeff[i];
if (i <= p2.degree) result.coeff[i] += p2.coeff[i];
}
return result;
}
// Function to subtract two polynomials
Polynomial subtractPolynomials(Polynomial p1, Polynomial p2) {
Polynomial result;
result.degree = (p1.degree > p2.degree) ? p1.degree : p2.degree;
for (int i = 0; i <= result.degree; i++) {
result.coeff[i] = 0;
if (i <= p1.degree) result.coeff[i] += p1.coeff[i];
if (i <= p2.degree) result.coeff[i] -= p2.coeff[i];
}
return result;
}
// Function to multiply two polynomials
Polynomial multiplyPolynomials(Polynomial p1, Polynomial p2) {
Polynomial result;
result.degree = p1.degree + p2.degree;
for (int i = 0; i <= result.degree; i++) {
result.coeff[i] = 0;
}
for (int i = 0; i <= p1.degree; i++) {
for (int j = 0; j <= p2.degree; j++) {
result.coeff[i + j] += p1.coeff[i] * p2.coeff[j];
}
}
return result;
}
// Function to divide two polynomials and get quotient and remainder
void dividePolynomials(Polynomial dividend, Polynomial divisor, Polynomial* quotient, Polynomial* remainder) {
*quotient = (Polynomial){{0}, 0};
*remainder = dividend;
while (remainder->degree >= divisor.degree) {
int deg_diff = remainder->degree - divisor.degree;
int coeff_div = remainder->coeff[remainder->degree] / divisor.coeff[divisor.degree];
Polynomial term = {{0}, deg_diff};
term.coeff[deg_diff] = coeff_div;
*quotient = addPolynomials(*quotient, term);
Polynomial temp = multiplyPolynomials(term, divisor);
*remainder = subtractPolynomials(*remainder, temp);
}
}
// Function to print a polynomial
void printPolynomial(Polynomial p) {
for (int i = p.degree; i >= 0; i--) {
printf("%dx^%d", p.coeff[i], i);
if (i > 0) printf(" + ");
}
printf("\n");
}
int main() {
Polynomial p1 = {{5, 0, 10, 6}, 3}; // 6x^3 + 10x^2 + 5
Polynomial p2 = {{1, 2, 4}, 2}; // 4x^2 + 2x + 1
// Addition
Polynomial sum = addPolynomials(p1, p2);
printf("Sum of polynomials: ");
printPolynomial(sum);
// Subtraction
Polynomial diff = subtractPolynomials(p1, p2);
printf("Difference of polynomials: ");
printPolynomial(diff);
// Multiplication
Polynomial product = multiplyPolynomials(p1, p2);
printf("Product of polynomials: ");
printPolynomial(product);
// Division
Polynomial quotient, remainder;
dividePolynomials(p1, p2, "ient, &remainder);
printf("Quotient of polynomials: ");
printPolynomial(quotient);
printf("Remainder of polynomials: ");
printPolynomial(remainder);
return 0;
}
Introduction to Matrix Operations
Matrices are rectangular arrays of numbers, symbols, or expressions, arranged in rows and columns. Common matrix operations include addition, subtraction, multiplication, determinant, transpose, and inverse.
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
// Function to add two matrices
void addMatrices(int first[MAX][MAX], int second[MAX][MAX], int result[MAX][MAX], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
result[i][j] = first[i][j] + second[i][j];
}
}
}
// Function to subtract two matrices
void subtractMatrices(int first[MAX][MAX], int second[MAX][MAX], int result[MAX][MAX], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
result[i][j] = first[i][j] - second[i][j];
}
}
}
// Function to multiply two matrices
void multiplyMatrices(int first[MAX][MAX], int second[MAX][MAX], int result[MAX][MAX], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
result[i][j] = 0;
for (int k = 0; k < n; k++) {
result[i][j] += first[i][k] * second[k][j];
}
}
}
}
// Function to transpose a matrix
void transposeMatrix(int matrix[MAX][MAX], int result[MAX][MAX], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
result[j][i] = matrix[i][j];
}
}
}
// Function to find the determinant of a matrix
int determinant(int matrix[MAX][MAX], int n) {
int det = 0;
if (n == 1) {
return matrix[0][0];
} else if (n == 2) {
return (matrix[0][0] * matrix[1][1]) - (matrix[0][1] * matrix[1][0]);
} else {
int submatrix[MAX][MAX];
for (int x = 0; x < n; x++) {
int sub_i = 0;
for (int i = 1; i < n; i++) {
int sub_j = 0;
for (int j = 0; j < n; j++) {
if (j == x) continue;
submatrix[sub_i][sub_j] = matrix[i][j];
sub_j++;
}
sub_i++;
}
det += (x % 2 == 0 ? 1 : -1) * matrix[0][x] * determinant(submatrix, n - 1);
}
}
return det;
}
// Function to find the inverse of a matrix
void inverseMatrix(int matrix[MAX][MAX], float inverse[MAX][MAX], int n) {
int det = determinant(matrix, n);
if (det == 0) {
printf("Inverse doesn't exist as determinant is zero.\n");
return;
}
// Calculate the adjoint
int adj[MAX][MAX];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int submatrix[MAX][MAX], sub_i = 0;
for (int k = 0; k < n; k++) {
if (k == i) continue;
int sub_j = 0;
for (int l = 0; l < n; l++) {
if (l == j) continue;
submatrix[sub_i][sub_j] = matrix[k][l];
sub_j++;
}
sub_i++;
}
adj[j][i] = (i + j) % 2 == 0 ? determinant(submatrix, n - 1) : -determinant(submatrix, n - 1);
}
}
// Calculate the inverse
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
inverse[i][j] = (float) adj[i][j] / det;
}
}
}
// Function to print a matrix
void printMatrix(int matrix[MAX][MAX], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
}
// Function to print a float matrix
void printFloatMatrix(float matrix[MAX][MAX], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%.2f ", matrix[i][j]);
}
printf("\n");
}
}
int main() {
int n;
int firstMatrix[MAX][MAX], secondMatrix[MAX][MAX], result[MAX][MAX];
float inverse[MAX][MAX];
// Input matrix size
printf("Enter the size of the matrices (n x n): ");
scanf("%d", &n);
// Input first matrix
printf("Enter elements of the first matrix (%d x %d):\n", n, n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &firstMatrix[i][j]);
}
}
// Input second matrix
printf("Enter elements of the second matrix (%d x %d):\n", n, n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &secondMatrix[i][j]);
}
}
// Matrix addition
addMatrices(firstMatrix, secondMatrix, result, n);
printf("Sum of the matrices:\n");
printMatrix(result, n);
// Matrix subtraction
subtractMatrices(firstMatrix, secondMatrix, result, n);
printf("Difference of the matrices:\n");
printMatrix(result, n);
// Matrix multiplication
multiplyMatrices(firstMatrix, secondMatrix, result, n);
printf("Product of the matrices:\n");
printMatrix(result, n);
// Transpose of the first matrix
transposeMatrix(firstMatrix, result, n);
printf("Transpose of the first matrix:\n");
printMatrix(result, n);
// Determinant of the first matrix
int det = determinant(firstMatrix, n);
printf("Determinant of the first matrix: %d\n", det);
// Inverse of the first matrix
inverseMatrix(firstMatrix, inverse, n);
printf("Inverse of the first matrix:\n");
printFloatMatrix(inverse, n);
return 0;
}
Introduction to Sparse Matrices
A sparse matrix is a matrix in which most of the elements are zero. Storing sparse matrices efficiently is important to save space and computational time. One common representation is the use of arrays to store non-zero elements and their positions.
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
typedef struct {
int row;
int col;
int value;
} Element;
typedef struct {
int rows;
int cols;
int num;
Element elements[MAX];
} SparseMatrix;
// Function to add two sparse matrices
SparseMatrix addSparseMatrices(SparseMatrix sm1, SparseMatrix sm2) {
SparseMatrix result;
result.rows = sm1.rows;
result.cols = sm1.cols;
result.num = 0;
int i = 0, j = 0;
while (i < sm1.num && j < sm2.num) {
if (sm1.elements[i].row < sm2.elements[j].row ||
(sm1.elements[i].row == sm2.elements[j].row && sm1.elements[i].col < sm2.elements[j].col)) {
result.elements[result.num++] = sm1.elements[i++];
} else if (sm1.elements[i].row > sm2.elements[j].row ||
(sm1.elements[i].row == sm2.elements[j].row && sm1.elements[i].col > sm2.elements[j].col)) {
result.elements[result.num++] = sm2.elements[j++];
} else {
result.elements[result.num] = sm1.elements[i];
result.elements[result.num++].value = sm1.elements[i++].value + sm2.elements[j++].value;
}
}
while (i < sm1.num) {
result.elements[result.num++] = sm1.elements[i++];
}
while (j < sm2.num) {
result.elements[result.num++] = sm2.elements[j++];
}
return result;
}
// Function to subtract two sparse matrices
SparseMatrix subtractSparseMatrices(SparseMatrix sm1, SparseMatrix sm2) {
SparseMatrix result;
result.rows = sm1.rows;
result.cols = sm1.cols;
result.num = 0;
int i = 0, j = 0;
while (i < sm1.num && j < sm2.num) {
if (sm1.elements[i].row < sm2.elements[j].row ||
(sm1.elements[i].row == sm2.elements[j].row && sm1.elements[i].col < sm2.elements[j].col)) {
result.elements[result.num++] = sm1.elements[i++];
} else if (sm1.elements[i].row > sm2.elements[j].row ||
(sm1.elements[i].row == sm2.elements[j].row && sm1.elements[i].col > sm2.elements[j].col)) {
result.elements[result.num] = sm2.elements[j++];
result.elements[result.num++].value = -result.elements[result.num - 1].value;
} else {
result.elements[result.num] = sm1.elements[i];
result.elements[result.num++].value = sm1.elements[i++].value - sm2.elements[j++].value;
}
}
while (i < sm1.num) {
result.elements[result.num++] = sm1.elements[i++];
}
while (j < sm2.num) {
result.elements[result.num] = sm2.elements[j++];
result.elements[result.num++].value = -result.elements[result.num - 1].value;
}
return result;
}
// Function to transpose a sparse matrix
SparseMatrix transposeSparseMatrix(SparseMatrix sm) {
SparseMatrix result;
result.rows = sm.cols;
result.cols = sm.rows;
result.num = sm.num;
int index = 0;
for (int col = 0; col < sm.cols; col++) {
for (int i = 0; i < sm.num; i++) {
if (sm.elements[i].col == col) {
result.elements[index].row = sm.elements[i].col;
result.elements[index].col = sm.elements[i].row;
result.elements[index].value = sm.elements[i].value;
index++;
}
}
}
return result;
}
// Function to multiply two sparse matrices
SparseMatrix multiplySparseMatrices(SparseMatrix sm1, SparseMatrix sm2) {
SparseMatrix result;
result.rows = sm1.rows;
result.cols = sm2.cols;
result.num = 0;
if (sm1.cols != sm2.rows) {
printf("Matrix multiplication not possible.\n");
return result;
}
SparseMatrix sm2T = transposeSparseMatrix(sm2);
int temp[MAX][MAX] = {0};
for (int i = 0; i < sm1.num; i++) {
for (int j = 0; j < sm2T.num; j++) {
if (sm1.elements[i].col == sm2T.elements[j].col) {
temp[sm1.elements[i].row][sm2T.elements[j].row] += sm1.elements[i].value * sm2T.elements[j].value;
}
}
}
for (int i = 0; i < sm1.rows; i++) {
for (int j = 0; j < sm2.cols; j++) {
if (temp[i][j] != 0) {
result.elements[result.num].row = i;
result.elements[result.num].col = j;
result.elements[result.num++].value = temp[i][j];
}
}
}
return result;
}
// Function to print a sparse matrix
void printSparseMatrix(SparseMatrix sm) {
printf("Row\tColumn\tValue\n");
for (int i = 0; i < sm.num; i++) {
printf("%d\t%d\t%d\n", sm.elements[i].row, sm.elements[i].col, sm.elements[i].value);
}
}
int main() {
SparseMatrix sm1 = {3, 3, 4, {{0, 0, 3}, {0, 2, 5}, {1, 1, 7}, {2, 2, 9}}};
SparseMatrix sm2 = {3, 3, 3, {{0, 1, 6}, {1, 1, 3}, {2, 2, 8}}};
// Addition
SparseMatrix sum = addSparseMatrices(sm1, sm2);
printf("Sum of sparse matrices:\n");
printSparseMatrix(sum);
// Subtraction
SparseMatrix diff = subtractSparseMatrices(sm1, sm2);
printf("Difference of sparse matrices:\n");
printSparseMatrix(diff);
// Transpose
SparseMatrix trans = transposeSparseMatrix(sm1);
printf("Transpose of the first sparse matrix:\n");
printSparseMatrix(trans);
// Multiplication
SparseMatrix product = multiplySparseMatrices(sm1, sm2);
printf("Product of sparse matrices:\n");
printSparseMatrix(product);
return 0;
}
Explanation with example of sparse matrix sum
This code defines a function addSparseMatrices
that takes two sparse matrices (sm1
and sm2
) and returns their sum as a new sparse matrix (result
). A sparse matrix is a matrix in which most elements are zero, and it's stored efficiently by only keeping track of the non-zero elements.
Let's consider two sparse matrices sm1
and sm2
for the example.
Sparse Matrix 1 (sm1)
Row | Col | Value |
0 | 1 | 3 |
1 | 2 | 5 |
2 | 0 | 7 |
Sparse Matrix 2 (sm2)
Row | Col | Value |
0 | 1 | 4 |
1 | 2 | -5 |
2 | 1 | 2 |
Step-by-Step Execution
Initialization:
SparseMatrix result; result.rows = sm1.rows; result.cols = sm1.cols; result.num = 0;
The result matrix is initialized with the same number of rows and columns as
sm1
(andsm2
since they should have the same dimensions).result.num
is set to 0, indicating that no elements have been added yet.
Merging Non-Zero Elements:
int i = 0, j = 0; while (i < sm1.num && j < sm2.num) {
- Two pointers
i
andj
are initialized to 0 to traverse the elements ofsm1
andsm2
, respectively.
- Two pointers
Comparison and Addition:
if (sm1.elements[i].row < sm2.elements[j].row || (sm1.elements[i].row == sm2.elements[j].row && sm1.elements[i].col < sm2.elements[j].col)) { result.elements[result.num++] = sm1.elements[i++]; } else if (sm1.elements[i].row > sm2.elements[j].row || (sm1.elements[i].row == sm2.elements[j].row && sm1.elements[i].col > sm2.elements[j].col)) { result.elements[result.num++] = sm2.elements[j++]; } else { result.elements[result.num] = sm1.elements[i]; result.elements[result.num++].value = sm1.elements[i++].value + sm2.elements[j++].value; }
This part of the code compares the current elements of
sm1
andsm2
and decides which element to add to the result.If
sm1.elements[i]
comes beforesm2.elements[j]
, it is added to the result.If
sm2.elements[j]
comes beforesm1.elements[i]
, it is added to the result.If both elements are at the same position (
row
andcol
), their values are added and stored in the result.
Let's see how this works with our example:
First elements (0,1,3) and (0,1,4):
- They are at the same position, so (0,1,3+4=7) is added to the result.
Next elements (1,2,5) and (1,2,-5):
- They are at the same position, so (1,2,5+(-5)=0) is not added to the result as the value is 0.
Next elements (2,0,7) and (2,1,2):
- (2,0,7) comes before (2,1,2), so it is added to the result.
Finally, (2,1,2) is added to the result.
Adding Remaining Elements:
while (i < sm1.num) { result.elements[result.num++] = sm1.elements[i++]; } while (j < sm2.num) { result.elements[result.num++] = sm2.elements[j++]; }
- If there are any remaining elements in
sm1
orsm2
, they are added to the result. In our case, all elements have already been processed.
- If there are any remaining elements in
Final Result
The resulting sparse matrix would be:
Row | Col | Value |
0 | 1 | 7 |
2 | 0 | 7 |
2 | 1 | 2 |
Basic Problems
Second Largest Element: Write a program that takes an array of integers and finds the second largest element in the array. Ensure your solution works efficiently for both small and large arrays, and handles cases where there are duplicate elements or the array size is less than two.
Jagged Array Sum: Create a jagged array (array of arrays) where each row has a different number of columns. Write a program to calculate the sum of all elements in the jagged array and print the result. Ensure that your solution can handle varying row sizes and empty rows.
Array Element Deletion: Write a program that takes an array of integers and an integer value, then removes all occurrences of that value from the array. The program should shift the remaining elements to the left and reduce the size of the array accordingly, ensuring that no empty slots are left in the middle.
Transpose of a Matrix: Given an MxN matrix of integers, write a program to find the transpose of the matrix. The transpose of a matrix is obtained by swapping its rows and columns. Ensure your program works efficiently for both square and rectangular matrices.
Diagonal Sum of a Square Matrix: Write a program to calculate the sum of the primary and secondary diagonals of a square matrix. The primary diagonal runs from the top-left to the bottom-right, while the secondary diagonal runs from the top-right to the bottom-left. Ensure your program handles matrices of varying sizes.
Matrix Multiplication: Write a program to multiply two matrices and print the resultant matrix. The program should ensure that matrix multiplication is valid (i.e., the number of columns in the first matrix is equal to the number of rows in the second matrix) and handle matrices of varying dimensions.
Merge Two Sorted Arrays: Write a program that takes two sorted arrays of integers and merges them into a single sorted array. Ensure your solution handles arrays of different lengths and merges the arrays in O(n) time complexity, where n is the total number of elements in both arrays.
Find Missing Number in Array: Given an array containing n-1 distinct numbers taken from the range 1 to n, write a program to find the missing number in the array. Ensure your solution works efficiently without using extra space.
Check for Magic Square: Write a program to check if a given 2D square matrix of integers is a magic square. A magic square is a grid where the sums of the numbers in each row, each column, and both main diagonals are the same. The program should handle matrices of varying sizes.
Find Peak Element in Array: Write a program to find a peak element in an array of integers. A peak element is an element that is greater than or equal to its neighbors. The program should return the index of any peak element and handle arrays of different lengths.
Frequency Count in Array: Write a program to count the frequency of each element in an array of integers. The program should output each element along with its frequency and handle arrays of varying sizes, ensuring efficient performance for large arrays.
Two Pointer Technique
The two-pointer technique is a common algorithmic approach used to solve various problems in computer science, especially in array and string manipulation. The idea is to use two pointers to traverse the data structure, allowing the algorithm to check pairs of elements or maintain a window of elements efficiently. This technique is often used to reduce the time complexity of an algorithm from \(O(n^2)\) to \(O(n)\) by avoiding nested loops.
One Pointer Left Fixed While Right is Probing
Longest Substring Without Repeating Characters: Given a string, write a program to find the length of the longest substring without repeating characters. Use one pointer to fix the start of the substring and another pointer to expand the substring by probing further into the string, adjusting the pointers as necessary.
Count Subarrays with Sum Less than K: Given an array of integers and an integer K, write a program to count the number of subarrays where the sum of the elements is less than K. Use one pointer to fix the start of the subarray and another pointer to expand the subarray by probing further, adjusting the pointers based on the sum condition.
Left and Right Moving Towards Each Other
Two Sum Sorted Array: Given a sorted array of integers and a target value, write a program to find two numbers such that they add up to a specific target number. Use two pointers starting from the beginning and end of the array, and move them towards each other until the target sum is found.
Palindrome Check: Given a string, write a program to check if it is a palindrome. Use two pointers, one starting at the beginning and the other at the end of the string, moving towards each other while comparing characters until they meet in the middle.
Sliding Window Technique
The sliding window technique is an efficient way to solve problems involving subarrays or substrings. Instead of using nested loops to iterate over all possible subarrays, a window of fixed or variable size slides over the data structure to maintain a subset of elements that can be processed incrementally. This technique reduces the time complexity to \(O(n)\) by maintaining the window and updating it as it moves.
Fixed Sliding Window
Maximum Sum Subarray of Size K: Given an array of integers and an integer K, write a program to find the maximum sum of a subarray of size K. Use the sliding window technique to maintain a window of size K and slide it across the array, updating the sum as you go.
Average of Subarrays of Size K: Given an array of integers and an integer K, write a program to find the average of all subarrays of size K. Use the sliding window technique to maintain the sum of elements in the window and compute the average as the window slides across the array.
Variable Sliding Window (Either Left or Right Boundary Can Move)
Smallest Subarray with Sum Greater than S: Given an array of integers and an integer S, write a program to find the length of the smallest subarray with a sum greater than S. Use the sliding window technique where the right boundary expands to increase the sum and the left boundary contracts to find the minimum length subarray.
Longest Substring with At Most K Distinct Characters: Given a string and an integer K, write a program to find the length of the longest substring that contains at most K distinct characters. Use the sliding window technique to expand the right boundary to include new characters and contract the left boundary to maintain at most K distinct characters.
Solutions
Sure, here are the same programs with comments added to explain the code:
1. Second Largest Element
#include <stdio.h>
#include <limits.h>
// Function to find the second largest element in an array
void findSecondLargest(int arr[], int n) {
if (n < 2) {
printf("Array size is less than two.\n");
return;
}
int first = INT_MIN, second = INT_MIN;
// Traverse the array to find the largest and second largest elements
for (int i = 0; i < n; i++) {
if (arr[i] > first) {
second = first; // Update second largest
first = arr[i]; // Update largest
} else if (arr[i] > second && arr[i] != first) {
second = arr[i]; // Update second largest
}
}
if (second == INT_MIN) {
printf("There is no second largest element.\n");
} else {
printf("The second largest element is %d\n", second);
}
}
int main() {
int arr[] = {12, 35, 1, 10, 34, 1};
int n = sizeof(arr) / sizeof(arr[0]);
findSecondLargest(arr, n);
return 0;
}
2. Jagged Array Sum
#include <stdio.h>
#include <stdlib.h>
int main() {
int rows = 3; // Number of rows in the jagged array
int *jagged[rows];
int sizes[] = {3, 2, 4}; // Number of columns in each row
// Allocating and initializing jagged array
jagged[0] = (int[]) {1, 2, 3};
jagged[1] = (int[]) {4, 5};
jagged[2] = (int[]) {6, 7, 8, 9};
int totalSum = 0; // Variable to store the total sum of elements
for (int i = 0; i < rows; i++) {
for (int j = 0; j < sizes[i]; j++) {
totalSum += jagged[i][j]; // Calculate sum of all elements
}
}
printf("Total sum of elements in jagged array: %d\n", totalSum);
return 0;
}
3. Array Element Deletion
#include <stdio.h>
// Function to delete all occurrences of a value from the array
void deleteElement(int arr[], int *n, int value) {
int i, j;
for (i = 0; i < *n; i++) {
if (arr[i] == value) {
// Shift elements to the left to overwrite the deleted element
for (j = i; j < *n - 1; j++) {
arr[j] = arr[j + 1];
}
(*n)--; // Decrease the size of the array
i--; // Check the current index again after shifting
}
}
}
int main() {
int arr[] = {1, 2, 3, 4, 2, 2, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int value = 2;
deleteElement(arr, &n, value);
printf("Array after deletion: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
4. Transpose of a Matrix
#include <stdio.h>
// Function to transpose a matrix
void transpose(int arr[][3], int m, int n, int result[][3]) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
result[j][i] = arr[i][j]; // Swap rows and columns
}
}
}
int main() {
int arr[3][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
int result[3][3];
transpose(arr, 3, 3, result);
printf("Transpose of the matrix:\n");
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
printf("%d ", result[i][j]);
}
printf("\n");
}
return 0;
}
5. Diagonal Sum of a Square Matrix
#include <stdio.h>
// Function to calculate the sum of primary and secondary diagonals
void diagonalSum(int arr[][3], int n) {
int primaryDiagonalSum = 0, secondaryDiagonalSum = 0;
for (int i = 0; i < n; i++) {
primaryDiagonalSum += arr[i][i]; // Sum of primary diagonal
secondaryDiagonalSum += arr[i][n - 1 - i]; // Sum of secondary diagonal
}
printf("Primary Diagonal Sum: %d\n", primaryDiagonalSum);
printf("Secondary Diagonal Sum: %d\n", secondaryDiagonalSum);
}
int main() {
int arr[3][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
diagonalSum(arr, 3);
return 0;
}
6. Matrix Multiplication
#include <stdio.h>
// Function to multiply two matrices
void multiplyMatrices(int first[][2], int second[][2], int result[][2], int r1, int c1, int r2, int c2) {
if (c1 != r2) {
printf("Matrix multiplication not possible\n");
return;
}
// Initialize the result matrix with zeros
for (int i = 0; i < r1; i++) {
for (int j = 0; j < c2; j++) {
result[i][j] = 0;
for (int k = 0; k < c1; k++) {
result[i][j] += first[i][k] * second[k][j]; // Multiply and accumulate
}
}
}
}
int main() {
int first[2][2] = {
{1, 2},
{3, 4}
};
int second[2][2] = {
{5, 6},
{7, 8}
};
int result[2][2];
multiplyMatrices(first, second, result, 2, 2, 2, 2);
printf("Resultant matrix after multiplication:\n");
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
printf("%d ", result[i][j]);
}
printf("\n");
}
return 0;
}
7. Merge Two Sorted Arrays
#include <stdio.h>
// Function to merge two sorted arrays
void merge(int arr1[], int n1, int arr2[], int n2, int result[]) {
int i = 0, j = 0, k = 0;
// Merge elements from both arrays in sorted order
while (i < n1 && j < n2) {
if (arr1[i] <= arr2[j]) {
result[k++] = arr1[i++];
} else {
result[k++] = arr2[j++];
}
}
// Copy remaining elements from arr1
while (i < n1) {
result[k++] = arr1[i++];
}
// Copy remaining elements from arr2
while (j < n2) {
result[k++] = arr2[j++];
}
}
int main() {
int arr1[] = {1, 3, 5, 7};
int arr2[] = {2, 4, 6, 8};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int n2 = sizeof(arr2) / sizeof(arr2[0]);
int result[n1 + n2];
merge(arr1, n1, arr2, n2, result);
printf("Merged array: ");
for (int i = 0; i < n1 + n2; i++) {
printf("%d ", result[i]);
}
printf("\n");
return 0;
}
8. Find Missing Number in Array
#include <stdio.h>
// Function to find the missing number in the array
int findMissingNumber(int arr[], int n) {
int total = (n * (n + 1)) / 2; // Calculate sum of first n natural numbers
for (int i = 0; i < n - 1; i++) {
total -= arr[i]; // Subtract each element from the total
}
return total; // The remaining value is the missing number
}
int main() {
int arr[] = {1, 2, 4, 6, 3, 7, 8};
int
n = sizeof(arr) / sizeof(arr[0]) + 1; // Total number of elements (n)
int missing = findMissingNumber(arr, n);
printf("Missing number is %d\n", missing);
return 0;
}
9. Check for Magic Square
#include <stdio.h>
#include <stdbool.h>
// Function to check if a given 2D matrix is a magic square
bool isMagicSquare(int arr[][3], int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[0][i]; // Calculate the sum of the first row
}
// Check sums of all rows
for (int i = 1; i < n; i++) {
int rowSum = 0;
for (int j = 0; j < n; j++) {
rowSum += arr[i][j];
}
if (rowSum != sum) {
return false;
}
}
// Check sums of all columns
for (int i = 0; i < n; i++) {
int colSum = 0;
for (int j = 0; j < n; j++) {
colSum += arr[j][i];
}
if (colSum != sum) {
return false;
}
}
// Check sum of primary diagonal
int diag1Sum = 0, diag2Sum = 0;
for (int i = 0; i < n; i++) {
diag1Sum += arr[i][i];
diag2Sum += arr[i][n - 1 - i];
}
if (diag1Sum != sum || diag2Sum != sum) {
return false;
}
return true;
}
int main() {
int arr[3][3] = {
{2, 7, 6},
{9, 5, 1},
{4, 3, 8}
};
if (isMagicSquare(arr, 3)) {
printf("The matrix is a magic square.\n");
} else {
printf("The matrix is not a magic square.\n");
}
return 0;
}
10. Find Peak Element in Array
#include <stdio.h>
// Function to find a peak element in the array
int findPeakElement(int arr[], int n) {
for (int i = 0; i < n; i++) {
// Check if the current element is a peak element
if ((i == 0 || arr[i] >= arr[i - 1]) && (i == n - 1 || arr[i] >= arr[i + 1])) {
return i;
}
}
return -1; // This should never be reached if array has at least one element
}
int main() {
int arr[] = {1, 3, 20, 4, 1, 0};
int n = sizeof(arr) / sizeof(arr[0]);
int peakIndex = findPeakElement(arr, n);
if (peakIndex != -1) {
printf("Peak element is at index %d with value %d\n", peakIndex, arr[peakIndex]);
} else {
printf("No peak element found.\n");
}
return 0;
}
11. Frequency Count in Array
#include <stdio.h>
#include <stdlib.h>
// Function to count the frequency of each element in the array
void countFrequency(int arr[], int n) {
int *frequency = (int *)calloc(n, sizeof(int));
// Count frequency of each element
for (int i = 0; i < n; i++) {
frequency[arr[i]]++;
}
// Print frequency of each element
printf("Element frequency:\n");
for (int i = 0; i < n; i++) {
if (frequency[arr[i]] != 0) {
printf("%d: %d times\n", arr[i], frequency[arr[i]]);
frequency[arr[i]] = 0; // Set to 0 to avoid duplicate printing
}
}
free(frequency); // Free allocated memory
}
int main() {
int arr[] = {1, 2, 2, 3, 4, 4, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
countFrequency(arr, n);
return 0;
}
12. Longest Substring Without Repeating Characters
#include <stdio.h>
#include <string.h>
int longestSubstringWithoutRepeatingChars(char *str) {
int n = strlen(str);
int maxLength = 0;
int start = 0; // Pointer to fix the start of the substring
int charIndex[256]; // Array to store the last index of each character
// Initialize all elements to -1
for (int i = 0; i < 256; i++) {
charIndex[i] = -1;
}
for (int end = 0; end < n; end++) {
// If character is already seen, move the start pointer
if (charIndex[str[end]] >= start) {
start = charIndex[str[end]] + 1;
}
// Update the last index of the character
charIndex[str[end]] = end;
// Update the maximum length of substring
maxLength = maxLength > (end - start + 1) ? maxLength : (end - start + 1);
}
return maxLength;
}
int main() {
char str[] = "abcabcbb";
int length = longestSubstringWithoutRepeatingChars(str);
printf("Length of the longest substring without repeating characters: %d\n", length);
return 0;
}
13. Count Subarrays with Sum Less than K
#include <stdio.h>
int countSubarraysWithSumLessThanK(int arr[], int n, int k) {
int count = 0;
int start = 0; // Pointer to fix the start of the subarray
int sum = 0;
for (int end = 0; end < n; end++) {
sum += arr[end]; // Expand the window by adding the current element
// While sum is not less than k, contract the window from the start
while (sum >= k && start <= end) {
sum -= arr[start++];
}
// All subarrays ending at 'end' and starting from 'start' to 'end' are valid
count += (end - start + 1);
}
return count;
}
int main() {
int arr[] = {1, 11, 2, 3, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 10;
int count = countSubarraysWithSumLessThanK(arr, n, k);
printf("Number of subarrays with sum less than %d: %d\n", k, count);
return 0;
}
14. Two Sum Sorted Array
#include <stdio.h>
#include <stdbool.h>
bool twoSumSortedArray(int arr[], int n, int target, int *num1, int *num2) {
int left = 0;
int right = n - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
*num1 = arr[left];
*num2 = arr[right];
return true;
} else if (sum < target) {
left++; // Move the left pointer to the right
} else {
right--; // Move the right pointer to the left
}
}
return false; // No two numbers found
}
int main() {
int arr[] = {2, 7, 11, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 9;
int num1, num2;
if (twoSumSortedArray(arr, n, target, &num1, &num2)) {
printf("Numbers found: %d and %d\n", num1, num2);
} else {
printf("No two numbers found that add up to %d\n", target);
}
return 0;
}
15. Palindrome Check
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool isPalindrome(char *str) {
int left = 0;
int right = strlen(str) - 1;
while (left < right) {
if (str[left] != str[right]) {
return false; // Characters do not match
}
left++;
right--;
}
return true; // String is a palindrome
}
int main() {
char str[] = "racecar";
if (isPalindrome(str)) {
printf("The string \"%s\" is a palindrome.\n", str);
} else {
printf("The string \"%s\" is not a palindrome.\n", str);
}
return 0;
}
16. Maximum Sum Subarray of Size K
#include <stdio.h>
int maxSumSubarrayOfSizeK(int arr[], int n, int k) {
int maxSum = 0;
int currentSum = 0;
// Calculate the sum of the first window of size K
for (int i = 0; i < k; i++) {
currentSum += arr[i];
}
maxSum = currentSum;
// Slide the window from start to end of the array
for (int i = k; i < n; i++) {
currentSum += arr[i] - arr[i - k]; // Add the next element and remove the first element of the previous window
if (currentSum > maxSum) {
maxSum = currentSum; // Update the maximum sum
}
}
return maxSum;
}
int main() {
int arr[] = {2, 1, 5, 1, 3, 2};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
int maxSum = maxSumSubarrayOfSizeK(arr, n, k);
printf("Maximum sum of a subarray of size %d: %d\n", k, maxSum);
return 0;
}
17. Average of Subarrays of Size K
#include <stdio.h>
void averageOfSubarraysOfSizeK(int arr[], int n, int k) {
double currentSum = 0;
// Calculate the sum of the first window of size K
for (int i = 0; i < k; i++) {
currentSum += arr[i];
}
// Slide the window from start to end of the array
for (int i = k; i < n; i++) {
printf("Average of subarray [%d, %d]: %.2f\n", i - k + 1, i, currentSum / k);
currentSum += arr[i] - arr[i - k]; // Add the next element and remove the first element of the previous window
}
// Print the average of the last subarray
printf("Average of subarray [%d, %d]: %.2f\n", n - k, n - 1, currentSum / k);
}
int main() {
int arr[] = {1, 3, 2, 6, -1, 4, 1, 8, 2};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 5;
averageOfSubarraysOfSizeK(arr, n, k);
return 0;
}
18. Smallest Subarray with Sum Greater than S
#include <stdio.h>
int smallestSubarrayWithSumGreaterThanS(int arr[], int n, int s) {
int minLength = n + 1;
int currentSum = 0;
int start = 0;
for (int end = 0; end < n; end++) {
currentSum += arr[end]; // Expand the window by adding the current element
// Contract the window from the start while the current sum is greater than S
while (currentSum > s) {
if (end - start + 1 < minLength) {
minLength = end - start + 1; // Update the minimum length
}
currentSum -= arr[start++]; // Remove the start element from the current sum
}
}
return minLength == n + 1 ? 0 : minLength;
}
int main() {
int arr[] = {2, 1, 5, 2, 3, 2};
int n = sizeof(arr) / sizeof(arr[0]);
int s = 7;
int minLength = smallestSubarrayWithSumGreaterThanS(arr, n, s);
if (minLength == 0) {
printf("No subarray found with sum greater than %d\n", s);
} else {
printf("Length of the smallest subarray with sum greater than %d: %d\n", s, minLength);
}
return 0;
}
19. Longest Substring with At Most K Distinct Characters
#include <stdio.h>
#include <string.h>
int longestSubstringWithAtMostKDistinctChars(char *str, int k) {
int n = strlen(str);
int maxLength = 0;
int start = 0; // Pointer to fix the start of the substring
int charCount[256] = {0}; // Array to store the count of each character
int distinctCount = 0; // Count of distinct characters in the current window
for (int end = 0; end < n; end++) {
if (charCount[str[end]] == 0) {
distinctCount++; // Increment distinct character count
}
charCount[str[end]]++;
// While distinct character count exceeds K, contract the window from the start
while (distinctCount > k) {
charCount[str[start]]--;
if (charCount[str[start]] == 0) {
distinctCount--; // Decrement distinct character count
}
start++;
}
// Update the maximum length of substring
maxLength = maxLength > (end - start + 1) ? maxLength : (end - start + 1);
}
return maxLength;
}
int main() {
char str[] = "eceba";
int k = 2;
int length = longestSubstringWithAtMostKDistinctChars(str, k);
printf("Length of the longest substring with at most %d distinct characters: %d\n", k, length);
return 0;
}