Need a C code for this problem. Gerald’s brother, Charlie, recently had a birthd

Question

Need a C code for this problem.

Gerald’s brother, Charlie, recently had a birthday party. Since all of Charlie’s friends know that he wants to become a D.J. when he grows up, they gave him many cool new gifts related to music. However, the best gift was a new stereo which had a fancy graphic visualizer on the front. A graphic visualizer is a feature found in electronic music devices which generates animated imagery synchronized to music being played. Charlie’s visualizer has n different columns of squares which represent the amplitude of a particular frequency. Gerald is very jealous of his little brother’s new stereo and can’t stand to listen to the music that his brother plays through its speakers, so he has devised a plot to solve his problem. He has a theory for how sound works, and it is this: All sounds can be assigned a value s. To calculate s, you must sum all the absolute difference in heights between each pair of adjacent columns. For example, in the left image above, column 0 and column 1 are 4 apart, column 1 and column 2 are 1 apart, and so on. If you add all these differences you would get a value of s = 15. Gerald also believes that if a sound wave’s columns are rearranged in such a way that s is as large as possible and then is played at the same time as the original sound, the two will cancel out and no sound will be heard. There may be more than one valid way to do this. If you are to rearrange the columns in the original wave to the order on the right, you can achieve a maximum s = 24. Note that an entire column must be rearranged when done so and not just portions of it.

The Problem: Help Gerald find the maximum value of s for a given sound wave represented by n columns when he is able to swap around any columns. This way he can cancel out all of his brother’s music and never be bothered again.

The Input: The first line will contain a single, positive integer, t, representing the number of different wave forms that need to be processed. The next t lines will start with an integer, n (1 n 10), followed by n integers, c0 through cn-1 (0 ci 108 ), representing the height of each column in a wave representation.

The Output: For each wave, output a single line of the form “Wave #i: s” where i represents the number of the wave which you are processing (starting from 1), and s represents the maximum s value of that wave.

Sample Input:

3

3 1 2 3

5 9 2 5 3 1

10 7 3 4 5 5 7 6 8 5 4

Sample Output:

Wave #1: 3

Wave #2: 21

Wave #3: 24

Explanation / Answer

#include <stdio.h>
#include <stdlib.h>

  
/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */
void merge(int arr[], int l, int m, int r);

// Utility function to find minimum of two integers
int min(int x, int y) { return (x<y)? x :y; }


/* Iterative mergesort function to sort arr[0...n-1] */
void mergeSort(int arr[], int n)
{
int curr_size; // For current size of subarrays to be merged
// curr_size varies from 1 to n/2
int left_start; // For picking starting index of left subarray
// to be merged

// Merge subarrays in bottom up manner. First merge subarrays of
// size 1 to create sorted subarrays of size 2, then merge subarrays
// of size 2 to create sorted subarrays of size 4, and so on.
for (curr_size=1; curr_size<=n-1; curr_size = 2*curr_size)
{
// Pick starting point of different subarrays of current size
for (left_start=0; left_start<n-1; left_start += 2*curr_size)
{
// Find ending point of left subarray. mid+1 is starting
// point of right
int mid = left_start + curr_size - 1;

int right_end = min(left_start + 2*curr_size - 1, n-1);

// Merge Subarrays arr[left_start...mid] & arr[mid+1...right_end]
merge(arr, left_start, mid, right_end);
}
}
}

/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

/* create temp arrays */
int L[n1], R[n2];

/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];

/* Merge the temp arrays back into arr[l..r]*/
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}

/* Copy the remaining elements of L[], if there are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}

/* Copy the remaining elements of R[], if there are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}

/* Function to print an array */
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf(" ");
}

int main()
{
   int t;
   printf("Enter number of waves: ");
   scanf("%d",&t);
   while(t--)
   {
   printf("Enter size of this wave: ");
int n;
   scanf("%d",&n);
   int arr[n];
   int i;
   printf("Enter heights: ");
   for ( i = 0; i < n; ++i)
   {
       scanf("%d",&arr[i]);
   }


mergeSort(arr, n); // sorting the array first

int sum = arr[n-1] + arr[n-2] - 2* arr[0];
for ( i = 1; i <= n/2; ++i)
{
   sum = sum + arr[n-i] + arr[n-i-2] - 2* arr[i]; // finding maximum sum
}
printf("Maximum value of s: %d ", sum);
}

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

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