Question

In: Computer Science

1- Write it with C++ program §Write a function Rotate that rotates an array of size...

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

Solutions

Expert Solution

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...


Related Solutions

In c++ Array expander Write a function that accepts an int array and the arrays size...
In c++ Array expander Write a function that accepts an int array and the arrays size as arguments. The function should create a new array that is twice the size of the argument array. The function should create a new array that is twice the size of the argument array. The function should copy the contents of the argument array to the new array and initialize the unused elements of the second array with 0. The function should return a...
C++ 9.10: Reverse Array Write a function that accepts an int array and the array’s size...
C++ 9.10: Reverse Array Write a function that accepts an int array and the array’s size as arguments. The function should create a copy of the array, except that the element values should be reversed in the copy. The function should return a pointer to the new array. Demonstrate the function by using it in a main program that reads an integer N (that is not more than 50) from standard input and then reads N integers from a file...
1) Write a function searchValue that accepts an array of integers, the size of the array,...
1) Write a function searchValue that accepts an array of integers, the size of the array, and an integer. Find the last occurrence of the integer passed in as an input argument in the array. Return the index of the last occurrence of the value. If the value is not found, return a -1 2) Write the line of code to call the previous function assuming you have an array vec with length n, and are looking for the number...
write a program in C Write a function that is passed an array of characters containing...
write a program in C Write a function that is passed an array of characters containing letter grades of A, B, C, D, and F, and returns the total number of occurrences of each letter grade. Your function should accept both lower and upper case grades, for example, both 'b' and 'B' should be bucketed into your running total for B grades. Any grade that is invalid should be bucketed as a grade of 'I' for Incomplete. You must use...
use c++ 1 a)Write a console program that creates an array of size 100 integers. Then...
use c++ 1 a)Write a console program that creates an array of size 100 integers. Then use Fibonacci function Fib(n) to fill up the array with Fib(n) for n = 3 to n = 103: So this means the array looks like: { Fib(3), Fib(4), Fib(5), ...., Fib[102) }. For this part of the assignment, you should first write a recursive Fib(n) function. .For testing, print out the 100 integers. b) For the second part of this assignment, you must...
C Language - Programming Write a function that takes an array of ints, and the size...
C Language - Programming Write a function that takes an array of ints, and the size of the array – another int. It also returns a double. Call this one ‘average.’ Return a double that is the average of the values in the array. Demonstrate that it works by finding the average of an array with these values {78, 90, 56, 99, 88, 68, 92} Write a function that takes one double parameter, and returns a char. The parameter represents...
C++ Write a function that accepts an array of doubles and the array's size as arguments....
C++ Write a function that accepts an array of doubles and the array's size as arguments. The function should display the contents of the array to the screen.
Write a C program to Declare an integer array of size 10 with values initialized as...
Write a C program to Declare an integer array of size 10 with values initialized as follows. int intArray[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; Compute each item of a new array of same size derived from the above array by: adding first item (intArray[0]) of the array with 3rd, 2nd with 4th, 3rd with 5th and so on. For the last-but-one item intArray[8], add it with first item and for the last item (intArray[9])...
In C, write a program that initializes a 3D array (the exact size doesn't matter) that...
In C, write a program that initializes a 3D array (the exact size doesn't matter) that contain what ever arbitrary integers and print out the array including the elements and use different functions so that the main only contains variables and function calls.
Write a C++ function, smallestIndex, that takes as parameters an int array and its size and...
Write a C++ function, smallestIndex, that takes as parameters an int array and its size and returns the index of the first occurrence of the smallest element in the array. Write another C++ function,lastLargestIndex, that takes as parameters an int array and its size and returns the index of the last occurrence of the largest element in the array. An analysis and design of the function smallestIndex is given below. Write an analysis and design for the function lastLargestIndex. Write...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT