1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
rewona [7]
3 years ago
7

Give an O(log m + log n)-time algorithm that takes two sorted lists of sizes m and n, respectively, as input and returns the ith

smallest element in the union of the two lists. Justify your algorithm and analyze its running time.
Computers and Technology
1 answer:
olga2289 [7]3 years ago
7 0

Binary search is used similarly. K'th element is found in more productive way.

<u>Explanation:</u>

arr1 and arr2 are the middle elements which are compared, let us compute as mid1 and mid2. Let us predict arr1 [mid1] k, the elements are not needed after mid2 elements.  arr2 are set as last element for arr2 [mid2].  New sub problems are defined. When one array is half the size.

C++ code for the algorithm.

#include <iostream>

using namespace std;    

int kth(int *arr1, int *arr2, int *end1, int *end2, int k)

{

if (arr1 == end1)

return arr2[k];

if (arr2 == end2)

return arr1[k];

int mid1 = (end1 - arr1) / 2;

int mid2 = (end2 - arr2) / 2;

if (mid1 + mid2 < k)

{

if (arr1[mid1] > arr2[mid2])

return kth(arr1, arr2 + mid2 + 1, end1, end2,

k - mid2 - 1);

else

return kth(arr1 + mid1 + 1, arr2, end1, end2,

k - mid1 - 1);

}

else

{

if (arr1[mid1] > arr2[mid2])

return kth(arr1, arr2, arr1 + mid1, end2, k);

else

return kth(arr1, arr2, end1, arr2 + mid2, k);

}    

int main()

{

int arr1[5] = {2, 3, 6, 7, 9};

int arr2[4] = {1, 4, 8, 10};    

int k = 5;

cout << kth(arr1, arr2, arr1 + 5, arr2 + 4, k - 1);

return 0;

}

You might be interested in
A type of malicious code that appears to be a safe program but that actually has a hidden purpose is called a _____.
masha68 [24]

This is a trojan horse type of virus.

5 0
3 years ago
Read 2 more answers
The Danger zone around a robot is?
mojhsa [17]

maybe a EMP. tell me if im right

3 0
3 years ago
Read 2 more answers
Array, destination contains the number of 10 cities numbered 1 to 10 that the products were shipped to. Hence, 10 quantities of
Naddik [55]

Answer:

#include <stdlib.h>

#include <stdio.h>

void func1(int product[]){

int orders[6]={0};

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

orders[product[i]]++;

}

printf("Total number of each type of products that were bought\n");

for(int i=1;i<=5;i++){

printf("Product %d = %d\n",i,orders[i]);

}

}

void func2(int product[],int quantity[],float price[]){

float total_cost=0;

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

total_cost+= price[product[i]]* quantity[i];

}

printf("The total cost of all 70 orders = %.2f\n",total_cost);

}

void func3(int product[],int quantity[],int destination[],float price[]){

float total_cost=0;

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

if(destination[i]==8){

total_cost+= price[product[i]]* quantity[i];

}

}

printf("The total cost of all products shipped to destination 8 = %.2f\n",total_cost);

}

void func4(int product[],int quantity[],float price[]){

int total_orders=0;

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

if(price[product[i]]* quantity[i]>=50){

total_orders++;

}

}

printf("The total number of orders where each order is $50 or more = %d\n",total_orders);

}

void func5(int product[],int quantity[],int origination[],float price[]){

int total_orders=0;

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

if(origination[i]==3 && price[product[i]]* quantity[i]>=50){

total_orders++;

}

}

printf("The total number of orders that originated from 3 where each order is $50 or more. = %d\n",total_orders);

}

void func6(int product[],int quantity[],int origination[],float price[]){

float total_cost=0;

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

if(origination[i]==3 && price[product[i]] * quantity[i]>=50){

total_cost += price[product[i]] * quantity[i];

}

}

printf("The total number of orders that originated from 3 where each order is $50 or more. = %.2f\n",total_cost);

}

void func7(int origination[],int destination[]){

int total_orders=0;

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

if(origination[i]==3 && destination[i]==8){

total_orders++;

}

}

printf("The total number of orders that originated from 3 and shipped to 8. = %d\n",total_orders);

}

void func8(int product[],int quantity[],int origination[],int destination[],float price[]){

float total_cost=0;

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

if(origination[i]==3 && destination[i]==8){

total_cost += price[product[i]] * quantity[i];

}

}

printf("The total cost of orders that originated from 3 and shipped to 8. = %.2f\n",total_cost);

}

void func9(int destination[]){

int total_orders=0;

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

if(destination[i]!=8){

total_orders++;

}

}

printf("The total number of orders that was shipped to all destinations except to 8. = %d\n",total_orders);

}

void func10(int product[],int quantity[],int destination[],float price[]){

float total_cost=0;

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

if(destination[i]!=8){

total_cost += price[product[i]] * quantity[i];;

}

}

printf("The total cost of orders that was shipped to all destinations except to 8. = %.2f\n",total_cost);

}

int main(){

int product[70] = {4, 2, 4, 2, 4, 5, 5, 2, 2, 5, 5, 4, 3, 5, 4, 2, 5, 3, 1, 2, 2, 3, 3, 4, 5, 5, 4, 5, 3, 5, 5, 1, 4, 5, 1, 5, 3, 2, 4, 1, 2, 4, 5, 1, 5, 5, 5, 5, 5, 2, 5, 1, 4, 4, 4, 2, 3, 3, 3, 3, 4, 3, 5, 5, 3, 2, 3, 5, 3, 2};

int quantity[70] = {10, 9, 6, 4, 10, 4, 9, 6, 10, 7, 3, 4, 4, 9, 1, 8, 9, 1, 5, 8, 7, 2, 3, 4, 10, 5, 6, 2, 1, 7, 2, 8, 6, 9, 8, 8, 7, 7, 9, 10, 6, 7, 8, 2, 1, 7, 6, 3, 3, 1, 8, 4, 10, 7, 1, 10, 6, 9, 8, 2, 4, 6, 1, 8, 2, 6, 10, 2, 6, 2};

int origination[70] = {2, 7, 5, 5, 7, 2, 7, 2, 7, 7, 5, 2, 5, 5, 5, 2, 2, 7, 2, 7, 7, 2, 2, 2, 2, 5, 7, 5, 7, 7, 5, 5, 2, 2, 5, 7, 2, 5, 7, 2, 5, 7, 2, 5, 7, 2, 2, 7, 2, 7, 5, 2, 2, 2, 5, 7, 2, 5, 5, 5, 7, 7, 2, 5, 2, 7, 5, 2, 5, 7};

int destination[70] = {8, 7, 3, 10, 2, 6, 4, 5, 1, 3, 5, 9, 5, 8, 6, 4, 3, 7, 1, 2, 7, 2, 8, 2, 2, 1, 2, 6, 10, 2, 7, 7, 8, 6, 8, 8, 4, 8, 3, 10, 6, 9, 4, 9, 5, 1, 7, 3, 1, 7, 5, 5, 4, 9, 3, 10, 8, 1, 1, 1, 1, 8, 10, 3, 5, 2, 8, 7, 4, 10};

float price[6]={0,11.95,7.95,19.95,24.95,15.25};

func1(product);

func2(product,quantity,price);

func3(product,quantity,destination,price);

func4(product,quantity,price);

func5(product,quantity,origination,price);

func6(product,quantity,origination,price);

func7(origination,destination);

func8(product,quantity,origination,destination,price);

func9(destination);

func10(product,quantity,destination,price);

}

Explanation:

The program inputs order, products and cities products are shipped.

After a series of conditional requirements being met, will output the destination each product os going to and the number of products with its associated price.

3 0
4 years ago
Read 2 more answers
Please, give me a comic or story idea. I will mark brainliest. ( i need 5 slides with 2 characters in the story or comic) Please
salantis [7]

Answer:

Jack and John

Explanation:

Jack called John and offered him to come with him and some other friends to go out to the mall.

.....

8 0
3 years ago
Read 2 more answers
Which options can you choose to determine the width and height of data or cells in a spreadsheet? You can choose the or rulers t
Tju [1.3M]

Answer :

Double click on boarder width an height will automatically adjust.

Manual procedure are following:

1.Open desire file of spreadsheet

2. Click on home tab in cell group and then click format.

3. Under cell size click on default width.

4. In standered column width box type new measurements and then click OK.

4 0
3 years ago
Other questions:
  • James is planning to expand his DTP business. He has most of the basic DTP hardware and software components, but now he wants to
    12·2 answers
  • Digital art is created by using
    6·1 answer
  • What is the purpose of the overload keyword in the ip nat inside source list 1 pool nat_pool overload command?
    8·1 answer
  • Select the correct answer.
    5·1 answer
  • Un producto tecnológico puede ser tangible o intangible?
    6·1 answer
  • A team member who feels uncomfortable when disagreeing with another team member is likely from a(n) _______(fill in the blank) c
    5·1 answer
  • Which term describes the process of training a machine to do simple, repetitive tasks, and adapt or correct its performance base
    9·1 answer
  • Why is the Microsoft website considered the best source for information about pagefile.sys?​
    15·1 answer
  • Every windows service has the 3 start types what are those service types?
    15·1 answer
  • What changes could you make so that a message, "User input deemed invalid." during designing a simple calculator program for you
    8·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!