Scribd
Upload
8 views4 pages

Daa 3&4

The document contains C code for two algorithms: one for finding the kth smallest element in an array using merge sort and another for large number multiplication using the Karatsuba algorithm. The merge sort implementation includes functions for merging and sorting, while the Karatsuba algorithm recursively multiplies two large numbers. Both algorithms include input prompts for user interaction and error handling for invalid inputs.

Uploaded by

30,XI,Aarya Shimpi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views4 pages

Daa 3&4

The document contains C code for two algorithms: one for finding the kth smallest element in an array using merge sort and another for large number multiplication using the Karatsuba algorithm. The merge sort implementation includes functions for merging and sorting, while the Karatsuba algorithm recursively multiplies two large numbers. Both algorithms include input prompts for user interaction and error handling for invalid inputs.

Uploaded by

30,XI,Aarya Shimpi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

1) kth smallest element of an array using merge sort:

#include <stdio.h>

void merge(int arr[], int le , int mid, int right) {

int n1 = mid - le + 1;

int n2 = right - mid;

int L[n1], R[n2

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

L[i] = arr[le + i];

for (int j = 0; j < n2; j++) {

R[j] = arr[mid + 1 + j];

int i = 0, j = 0, k = le ;

while (i < n1 && j < n2) {

if (L[i] <= R[j]) {

arr[k] = L[i];

i++;

} else {

arr[k] = R[j];

j++;

k++;

while (i < n1) {

arr[k] = L[i];

i++;

k++;

while (j < n2) {

arr[k] = R[j];

j++;

k++;

void mergeSort(int arr[], int le , int right) {

if (le < right) {

int mid = le + (right - le ) / 2;


mergeSort(arr, le , mid);

mergeSort(arr, mid + 1, right);

merge(arr, le , mid, right);

int findKthSmallest(int arr[], int n, int k) {

mergeSort(arr, 0, n - 1);

return arr[k - 1

int main() {

int n, k;

prin ("Enter the number of elements in the array: ");

scanf("%d", &n);

int arr[n];

prin ("Enter %d elements:\n", n);

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

scanf("%d", &arr[i]);

prin ("Enter the value of k: ");

scanf("%d", &k);

if (k < 1 || k > n) {

prin ("Invalid value of k. Please enter a value between 1 and %d.\n", n);

return 1;

int kthSmallest = findKthSmallest(arr, n, k);

prin ("The %dth smallest element is: %d\n", k, kthSmallest);

return 0;

OUTPUT:
NAME: AARYA SHIMPI

ROLL NO. : 66

SY COMP C DIVISION

1) Large number mul plica on:


PROGRAM:

#include <stdio.h>

#include <math.h>

int get_size(long);

long karatsuba(long X, long Y){

// Base Case

if (X < 10 && Y < 10)

return X * Y;

// determine the size of X and Y

int size = fmax(get_size(X), get_size(Y));

if(size < 10)

return X * Y;

// rounding up the max length

size = (size/2) + (size%2);

long mul plier = pow(10, size);

long b = X/mul plier;

long a = X - (b * mul plier);

long d = Y / mul plier;

long c = Y - (d * size);

long u = karatsuba(a, c);

long z = karatsuba(a + b, c + d);

long v = karatsuba(b, d);

return u + ((z - u - v) * mul plier) + (v * (long)(pow(10, 2 * size))); }

int get_size(long value){

int count = 0;

while (value > 0) {

count++;

value /= 10;

return count;

int main(){
long x,y;

// two numbers

prin ("Enter first number: ");

scanf("%ld", &x);

prin ("Enter second number: ");

scanf("%ld", &y);

prin ("The final product is: %ld\n", karatsuba(x, y)); return 0;

You might also like