Problems and their solution:
Practice Problems on “Array” (MOODLE)
Problem 1: Floor, Ceil within an array
A[] = {96, 21, 58, 34, 46}
Number | Floor | Ceil |
15 | -1 | 21 |
21 | 21 | 21 |
30 | 21 | 34 |
96 | 96 | 96 |
98 | 96 | -1 |
Solution:
Sort them, then find floor and ceil from the array.
Use selection sort:
void selectionSort(int arr[], int n) {
int i, j, minIndex, temp;
for (i = 0; i < n - 1; i++) {
minIndex = i;
// Find the index of the smallest element in the remaining array
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
// Swap the found minimum element with the first element
if (minIndex != i) {
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
then:
#include<stdio.h>
void selectionSort(int arr[], int n);
void printArray(int arr[], int n);
int main()
{int C,F;
int arr[5]={15,21,30,96,98};
selectionSort(arr, 5);
for(int i=1; i<=5;i++)
{
int n; scanf("%d", &n);
if(n<arr[0]){C= -1; F=arr[0];}
else if(n>arr[4]){C=arr[4]; F=-1;}
else{
for(int j=0; j<n; j++)
{if(n==arr[j]){C=arr[j]; F= arr[j]; break;}
else if(n>arr[j] && n<arr[j+1]){C= arr[j]; F=arr[j+1]; break;}}
}
printf(" %d %d ", C, F);
}
}
void selectionSort(int arr[], int n)
{int idx, temp;
for(int i=0; i<n-1; i++)
{
idx=i;
for(int j=i+1; j<n; j++)
{
if(arr[j]<arr[idx])
idx=j;
}
if(idx!=i)
{
temp=arr[i];
arr[i]=arr[idx];
arr[idx]=temp;
}
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
Problem 2: Print all possible pairs that have a common factor other than 1
A [ ] = {5, 3, 15, 4, 2}
(5, 15), (15,5), (2,4), (4,2) (3,15), (15, 3)
Solution:
We can use function to make it easy. Common Factor function:
int commonfactor(int a, int b)
{int x;
int count;
if(a<b){x=a;}
else x=b;
for(int i=2; i<=x; i++)
{count =0;
if(a%i==0 && b%i==0)
{count++;}
}
if(a<2 || b<2){return 0;}
else if(count>0){printf("%d %d", a, b);}
else return 0;
}
Then we can use 2 loops. Then we can use them in this function.
#include<stdio.h>
int commonfactor(int a, int b);
int main()
{int arr[5]={5, 3, 15, 4, 2};
for(int i=0; i<5; i++)
{
for(int j=0; j<5; j++)
{
commonfactor(arr[i], arr[j]);
}
}
return 0;
}
int commonfactor(int a, int b)
{int x;
int count=0;
if(a<b){x=a;}
else x=b;
for(int i=2; i<=x; i++)
{
if(a%i==0 && b%i==0)
{count++;}
}
if(a<2 || b<2 || a==b){return 0;}
else if(count>0){printf("%d %d ", a, b); return 1;}
else return 0;
return 1;
}
Problem 3: Implement Binary Search where Elements can be repeated. Find:
(1) First occurrence
(2) Last occurrence
(3) All occurrences
Solution:
Binary Search:
How Binary Search Works?
-
Start with the whole sorted array.
-
Find the middle element.
-
If the middle element equals the target, you found it!
-
If the target is smaller than the middle element, search the left half of the array.
-
If the target is larger, search the right half.
-
Repeat the process on the selected half until you find the target or the subarray size becomes zero (meaning target not found).
int binarysearch(int arr[], int n, int t)
{int l=0;
int r=n-1;
while(r>=l){
int mid = l+(r-l)/2;
if(t==arr[mid]) return mid;
else if(arr[mid]<t) l=1+mid;
else r=mid-1;
}
return 0;
}
#include<stdio.h>
#include<stdlib.h>
int FindFirst(int arr[],int n, int t)
{
int l=0; int r=n-1; int rev=-1;
while(r>=l)
{
int mid= l+(r-l)/2;
if(arr[mid]==t)
{rev=mid; r=mid-1; }
else if(arr[mid]<t)
l=mid+1;
else r=mid-1;
}
return rev;
}
int FindLast(int arr[],int n, int t)
{
int l=0; int r=n-1; int rev=-1;
while(r>=l)
{
int mid= l+(r-l)/2;
if(arr[mid]==t)
{rev=mid; l=mid+1; }
else if(arr[mid]<t)
l=mid+1;
else r=mid-1;
}
return rev;
}
int Qsort(const void *a, const void *b)
{
return (*(int*)a-*(int*)b);
}
int main()
{int arr[5] = {1, 43, 34, 43, 34};
qsort(arr, 5, sizeof(int), Qsort);
int result = FindFirst(arr, 5, 34);
int result2 = FindLast(arr, 5, 43);
printf("First 34 at: %d\n", result);
printf("Last 43 at: %d\n", result2);
for(int i = 0; i < 5; i++)
printf("%d ", arr[i]);
}
# shift 2 box left :
#include <stdio.h>
void shiftLeft(int arr[], int size, int positions) {
int temp[positions];
// Store first 'positions' elements
for (int i = 0; i < positions; i++) {
temp[i] = arr[i];
}
// Shift remaining elements left
for (int i = 0; i < size - positions; i++) {
arr[i] = arr[i + positions];
}
// Copy stored elements to end
for (int i = 0; i < positions; i++) {
arr[size - positions + i] = temp[i];
}
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int size = sizeof(arr)/sizeof(arr[0]);
shiftLeft(arr, size, 2);
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
return 0;
}
#shift n position right:
#include <stdio.h>
void shiftRight(int arr[], int size, int n) {
n = n % size; // Handle if n > size
if (n == 0) return; // No shift needed
int temp[n];
// Copy last n elements to temp
for (int i = 0; i < n; i++) {
temp[i] = arr[size - n + i];
}
// Shift the rest to the right
for (int i = size - 1; i >= n; i--) {
arr[i] = arr[i - n];
}
// Copy back the n elements to the start
for (int i = 0; i < n; i++) {
arr[i] = temp[i];
}
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6};
int size = sizeof(arr) / sizeof(arr[0]);
int n = 3;
shiftRight(arr, size, n);
// Print result
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
return 0;
}
# largest paliondrome:
#include <stdio.h>
// Function to check if a subarray is a palindrome
int isPalindrome(int arr[], int start, int end) {
while (start < end) {
if (arr[start] != arr[end]) {
return 0; // Not a palindrome
}
start++;
end--;
}
return 1; // Is a palindrome
}
// Function to find and print the longest palindromic subarray
void longestPalindrome(int arr[], int n) {
int maxLen = 1;
int startIdx = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (isPalindrome(arr, i, j)) {
int len = j - i + 1;
if (len > maxLen) {
maxLen = len;
startIdx = i;
}
}
}
}
// Print the longest palindrome subarray
printf("[");
for (int i = startIdx; i < startIdx + maxLen; i++) {
printf("%d", arr[i]);
if (i < startIdx + maxLen - 1)
printf(", ");
}
printf("]\n");
}
int main() {
// Example input
int arr[] = {3, 2, 1, 2, 3, 4, 5, 4, 3, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
longestPalindrome(arr, n);
return 0;
}
#intersection union:
#include <stdio.h>
int main()
{
int n1, n2;
int arr1[100]; int arr2[100];
int uni[100];
int x=0;
scanf("%d", &n1);
for(int i=0; i<n1; i++)
{
scanf("%d", &arr1[i]);
}
int uniq1[100];
int uniq2[100];
int a=0, b=0;
scanf("%d", &n2);
for(int i=0; i<n2; i++)
{
scanf("%d", &arr2[i]);
}
for(int i=0; i<n1; i++)
{ int count =0;
for(int j=0; j<i; j++)
{
if(arr1[i]==arr1[j])
{ count=1; break;
}
}
if(count==0){ uniq1[a++]=arr1[i];}
}
for(int i=0; i<n2; i++)
{ int count =0;
for(int j=0; j<i; j++)
{
if(arr1[i]==arr1[j])
{ count=1; break;
}
}
if(count==0){uniq2[b++] =arr2[i];}
}
for(int i=0; i<a; i++)
{
for(int j=0; j<b; j++)
{
if(uniq1[i]==uniq2[j])
{ printf("%d", uniq1[i]); break;} }
}
4..
#include <stdio.h>
// Function to find length of LIS
int longestIncreasingSubsequence(int arr[], int n) {
int lis[n];
// Initialize LIS values for all indexes as 1
for (int i = 0; i < n; i++) {
lis[i] = 1;
}
// Compute LIS values
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
lis[i] = lis[j] + 1;
}
}
}
// Find the maximum value in lis[]
int max = lis[0];
for (int i = 1; i < n; i++) {
if (lis[i] > max) {
max = lis[i];
}
}
return max;
}
int main() {
// Example input
int arr1[] = {10, 9, 2, 5, 3, 7};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
printf("%d\n", longestIncreasingSubsequence(arr1, n1)); // Output: 3
int arr2[] = {1, 2, 3, 4, 5};
int n2 = sizeof(arr2) / sizeof(arr2[0]);
printf("%d\n", longestIncreasingSubsequence(arr2, n2)); // Output: 5
int arr3[] = {4, 3, 2, 1};
int n3 = sizeof(arr3) / sizeof(arr3[0]);
printf("%d\n", longestIncreasingSubsequence(arr3, n3)); // Output: 1
return 0;
}
Comments
Post a Comment