In: Computer Science
1- Write it with C++ program
§Write a function Rotate that rotates an array of size n by d elements to the left
§Use array as argument
§In the main function, call the function Rotate and show the rotated array
§Test your code
For example:
Input: [1 2 3 4 5 6 7], n = 7, d = 2
Output: [3 4 5 6 7 1 2]
2- Write it in C++
§Search Insert Position
•Given a sorted array in ascending order and a target value
•Use binary search algorithm to return the index if the target is found. If not, return the index where it would be if it is inserted in order
•You may assume no duplicates in the array
Example :
Input: [1,3,5,6], 5
Output: 2
Input: [1,3,5,6], 2
Output: 1
Q1.
#include <iostream>
using namespace std;
//function which rotates the array left by d positions
void Rotate(int arr[],int n,int d){
//find the optimal number of rotations
int rot=d%n;
//the element at this position in the current array will be our
first element in the rotated array
int start=d;
//to add elements in the rotated array
int i=0;
//create a new temporary array
int * temp = new int[n];
//start filling the temporary array(i.e, our rotated array)
//iterate n times
for(;start<d+n;start++){
temp[i]=arr[start%n];
i++;
}
//now in temp array we have our rotated array so we copy it to our
original array
for(int i=0;i<n;i++){
arr[i]=temp[i];
}
//delete the dynamically allocated temporary array
delete []temp;
return;
}
//driver function
int main(){
//testing Rotate() function with sample array
int arr[]={1,2,3,4,5,6,7};
int n=7;
int d=2;
//before rotation
cout<<"Before rotation: ";
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
Rotate(arr, n, d);
//after rotation
cout<<"After rotation: ";
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
//return
return 0;
}
OUTPUT:
Q2:
#include <iostream>
using namespace std;
//function which returns the index of target if present
otherwise the index where it would be in the sorted array
int find_pos(int arr[],int n,int target){
//using binary search
//low and high pointer
int low=0,high=n-1;
//variable to save index
int index=-1;
//while low less than equal to high
while(low<=high){
//find mid index
int mid=(low+high)/2;
//if target is greater than the element at mid position
if(arr[mid]<target){
//update low as mid + 1 to decrease the search window
low=mid+1;
}
//if target is less than the element at mid position
else if(arr[mid>target]){
//save this index as this element is larger than target so can be
our final index
index=mid;
//update high as mid - 1 to decrease the search window
high=mid-1;
}
//if target found return index
else{
return mid;
}
}
//if target not found then return the position where it would be
inserted in the sorted array
return index;
}
//driver function
int main(){
//Testing find_pos() function which uses binary search to find the
index of target if present otherwise
// the index where it would be in the sorted array
int arr[]={1, 3, 5, 6};
int target=5;
int n=4;
//call and print for target=5
cout<<find_pos(arr, n, target)<<endl;
//call and print for target=2
target=2;
cout<<find_pos(arr, n, target)<<endl;
//return
return 0;
}
OUTPUT:
NOTE: If you got any sort of help from this article please UPVOTE and in case of query , mention it in comments...