Short C program Thank you!! Given a set of numbers your goal is to add them all,

Question

Short C program

Thank you!!

Given a set of numbers your goal is to add them all, while minimizing the cost of the addition. At any point, you may choose to add any two of the integers. The cost of doing so is simply the sum of the two numbers. For example, the cost of adding 1 and 10 is 11. 3, 6 and 2 can be added in several different ways. The minimum cost comes from adding 2+3 first to yield 5 and 5+6 to yield 11. The total cost for these two operations is 16 (5 + 11). Given a sequence of numbers calculate the minimum cost to add them into a single integer.

Input

First line of the input contains T the number of test cases. First line of each test case contains N the number of integers in the sequence. Second line contains N integers separated by a single space. N is between 1 and 500 inclusive. Each of the integers in the sequence will be between 1 and 500.

Output

For each test case output contains a single integer denoting the minimum cost.

Sample Input:

3
3

1 2 3

4

1 2 3 4

3

1 3 2

Sample Output:

9

19

9

Explanation / Answer

Ans;

#include<stdio.h>

void sorting(int arr[],int n)

{int i,j;

//using bubble sort

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

for(j=0;j<n-1;j++)

if(arr[j]>arr[j+1])

arr[j]=arr[j]+arr[j+1]-(arr[j+1]=arr[j]);//swap arr[j],arr[j+1]

}

int main()

{

int t,n,i,arr[500];

scanf("%d",&t);

while(t--)

{scanf("%d",&n);

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

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

//sort the array

if(n==1)

printf("%d ",0);

else

{sorting(arr,n);

long int cost=0;

i=0;

while(arr[n-2]!=0)

{cost=arr[i]+arr[i+1]+cost;

arr[i+1]=arr[i]+arr[i+1];

arr[i]=0;

sorting(arr,n);

i++;

}

printf("%ld ",cost);

}

}

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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