ASSIGNMENT 3
[Link] PROBLEM
USING SLL:
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* next;
};
// Function to create a new node
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->next = NULL;
return node;
// Function to create a circular singly linked list of size n
struct Node* createList(int n) {
struct Node* head = newNode(1);
struct Node* prev = head;
for (int i = 2; i <= n; i++) {
prev->next = newNode(i);
prev = prev->next;
prev->next = head; // make it circular
return head;
// Josephus elimination using SLL
int josephus(int n, int k) {
struct Node* head = createList(n);
struct Node* ptr = head;
struct Node* prev = NULL;
while (ptr->next != ptr) { // until one node left
// move k-1 steps
for (int count = 1; count < k; count++) {
prev = ptr;
ptr = ptr->next;
// eliminate current node
printf("Eliminated: %d\n", ptr->data);
prev->next = ptr->next;
free(ptr);
ptr = prev->next;
int survivor = ptr->data;
free(ptr);
return survivor;
int main() {
int n = 7, k = 3;
int safe = josephus(n, k);
printf("Josephus Position (Safe): %d\n", safe);
return 0;
[Link] NODE FROM LEFT AND
RIGHT
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* next;
};
// Function to create a new node
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->next = NULL;
return node;
// Function to print Nth node from the left
void nthFromLeft(struct Node* head, int n) {
int count = 1;
while (head != NULL) {
if (count == n) {
printf("Nth node from left: %d\n", head->data);
return;
head = head->next;
count++;
printf("Node not found (left)\n");
// Function to print Nth node from the right
void nthFromRight(struct Node* head, int n) {
int length = 0;
struct Node* temp = head;
// First count total nodes
while (temp != NULL) {
length++;
temp = temp->next;
// Position from left = length - n + 1
int target = length - n + 1;
if (target <= 0) {
printf("Node not found (right)\n");
return;
temp = head;
for (int i = 1; i < target; i++) {
temp = temp->next;
printf("Nth node from right: %d\n", temp->data);
}
int main() {
// Create linked list: 10 -> 20 -> 30 -> 40 -> 50
struct Node* head = newNode(10);
head->next = newNode(20);
head->next->next = newNode(30);
head->next->next->next = newNode(40);
head->next->next->next->next = newNode(50);
int n = 2;
nthFromLeft(head, n); // 2nd from left
nthFromRight(head, n); // 2nd from right
return 0;
[Link] A STRING USING
STACK
#include <stdio.h>
#include <string.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char c) { stack[++top] = c; }
char pop() { return stack[top--]; }
int main() {
char str[] = "HELLO";
int n = strlen(str);
for (int i = 0; i < n; i++) push(str[i]);
printf("Reversed String: ");
for (int i = 0; i < n; i++) printf("%c", pop());
return 0;
[Link] SPAN PROBLEM
#include <stdio.h>
#include <stdlib.h>
// Structure to hold stock price and its index
typedef struct {
int price;
int index;
} StackItem;
// Function to calculate stock span
void calculateSpan(int prices[], int n, int span[]) {
StackItem stack[n]; // stack to store items
int top = -1; // stack pointer
for (int i = 0; i < n; i++) {
// Pop elements from stack while stack is not empty
// and top price <= current price
while (top >= 0 && stack[top].price <= prices[i]) {
top--;
// If stack is empty, span is i+1
if (top == -1) {
span[i] = i + 1;
} else {
// Otherwise, span is difference between current index and top
index
span[i] = i - stack[top].index;
// Push current price and index onto stack
stack[++top].price = prices[i];
stack[top].index = i;
int main() {
int prices[] = {100, 80, 60, 70, 60, 75, 85};
int n = sizeof(prices) / sizeof(prices[0]);
int span[n];
calculateSpan(prices, n, span);
printf("Stock Prices: ");
for (int i = 0; i < n; i++) {
printf("%d ", prices[i]);
printf("\nSpan Values: ");
for (int i = 0; i < n; i++) {
printf("%d ", span[i]);
printf("\n");
return 0;
#include <stdio.h>
#include <string.h>
[Link] PARENTHESES
#define MAX 100
char stack[MAX];
int top = -1;
void push(char c) { stack[++top] = c; }
char pop() { return stack[top--]; }
int isBalanced(char* expr) {
for (int i = 0; i < strlen(expr); i++) {
if (expr[i] == '(') push('(');
else if (expr[i] == ')') {
if (top == -1) return 0;
pop();
return top == -1;
int main() {
char expr[] = "(a+b)*(c+d)";
if (isBalanced(expr)) printf("Balanced\n");
else printf("Not Balanced\n");
return 0;
[Link] SMALLEST
ELEMENT (LEFT AND RIGHT)
#include <stdio.h>
void previousSmaller(int arr[], int n) {
printf("Previous smaller (Left): ");
for (int i = 0; i < n; i++) {
int smaller = -1;
for (int j = i - 1; j >= 0; j--) {
if (arr[j] < arr[i]) { smaller = arr[j]; break; }
printf("%d ", smaller);
printf("\n");
void nextSmaller(int arr[], int n) {
printf("Next smaller (Right): ");
for (int i = 0; i < n; i++) {
int smaller = -1;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[i]) { smaller = arr[j]; break; }
printf("%d ", smaller);
printf("\n");
int main() {
int arr[] = {4, 5, 2, 10, 8};
int n = sizeof(arr)/sizeof(arr[0]);
previousSmaller(arr, n);
nextSmaller(arr, n);
return 0;
}
THE END