You are given an array A of n distinct integers, and an integer k such that 1 <=

Question

You are given an array A of n distinct integers, and an integer k such that 1 <= k <= n. The square distance between a pair of integers x, y is de?ned as the quantity (x ? y)^2. Your goal is to design an O(n) time algorithm to ?nd k elements in A with the smallest square distance to the median (i.e., the element of rank ?n/2? in A). and proof of correctness. For instance, if A = [9, 5, ?3, 1, ?2] and k = 2, then the median element is 1, and the 2 elements in A with the smallest square distance to the median are {1, ?2}. If k = 3, then you can output either {1, ?2, ?3} or {1, ?2, 5}.

Explanation / Answer

#include<stdio.h>

void main()

{

int a[10],i,j,n,k;

printf("enter the no of elements:");

scanf("%d",&n);

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

{

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

}

printf("enter the value for the integer k:");

scanf("%d",&k);

if((n%2)==1)

{

j=n/2;

printf("the median is %d",a[j]);

}

else

{

j=(n)/2;

printf("the median are %d %d",a[j],a[j+1]);

}

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

{

if(a[i]<j)

{

int l=0;

b[l]=a[i];

l++;

}

}

printf("the smallest square distance to the median are");

for(i=0;i<l;i++)

{

printf("%d",b[i]);

}

}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.