CareerCup

package Epic;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
/**********************************************************************
 * 2.write a program to diaplay the advisered average for the list of  
 *   numbers my omitting the largest number in the series.
 * eg :3,6,12,55,289,600,534,900 and 172.
 * avg=(3+6+12+55+289+172) /6and eliminating 534,900,600
 * 
 * My understanding 1:
 * 	Just eliminate the largest number.
 * 	Algorithm:
 * 		1. Iterate through the number list. 
 * 		2. Keep on adding and keep track of the largest number you have 
 * 		   encountered.
 * 		3. When loops end. Subtract the largest number.
 * 
 * 	Complexity: O(n)
 * 
 * 
 * My Understanding 2:	
 *   Eliminate the "n" largest number, where n is passed as the argument
 *   Algorithm:
 *   	1. Sort the number list. (I am using Java function for it)
 *   	2. Take the average of list.length -n. 
 *   
 *   Complexity: O(n2)  (For basic sorting algorithm.)
 *   			 O(nlogn) for quick/merge sort.
 *   
 * @author jhaxx030
 */
public class AdvertisedAverage {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Integer a[]=new Integer[] {3,6,12,55,289,600,534,900,172};
		List<Integer> numberList = Arrays.asList(a);

		averageUsingApproch1(numberList);
		averageUsingApproch2(numberList,3);
	}
	
	/************************************************************
	 * Approach1
	 */
	static void averageUsingApproch1(List<Integer> numberList){
		int sum = 0;
		int largestNumber = 0;
		for (Integer number: numberList){
			sum += number;
			if(largestNumber  < number){
				largestNumber = number;
			}
		}
		// Subtracting the largest number.
		sum -= largestNumber;
		// Removing "1" for largest number. 
		double averageValue = sum / numberList.size()-1;
		System.out.println("Advertised Average is:"+averageValue);
	}
	
	/************************************************************
	 * Approach2
	 */
	static void averageUsingApproch2(List<Integer> numberList, 
			int countNotToconsider){
		
		// Sort the list.
		Collections.sort(numberList);
		
		int sum = 0;
		for(int i=0;i<numberList.size()-countNotToconsider;i++){
			sum += numberList.get(i);
		}
		
		// Removing "countNotToconsider". 
		double averageValue=sum/numberList.size()-countNotToconsider;
		System.out.println("Advertised Average is:"+averageValue);
	}
}

How many largest number do you wanna eliminate each interaction? 1/3 of the total largest numbers?

I would like to know why you miss 534 900 600? 534 is not event the x3 times 289?

This is Straight O(n) Algo.

1> For each element in a list
2> Sum up the values.
3> track the largest value observed so far.
4> end of Loop
5> Eliminate the largest value from the summation . Sum - largest.
6> Divide the sum by the (counter-1) from the loop.

1-4 is O(n) and the 5,6 is constant 2 steps overall O(n)

#include<iostream>
using namespace std;
int main()
{
double a[10000];
float average=0,sum=0;
int n,i;
cout<<"Enter The number of your digit plz \n";
cin>>n;
cout<<"The num of your digit is ="<<n;
cout<<"\n Enter your num now \n";
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++)
sum+=a[i];
average =sum/n;
cout<<"The average is ="<<average;
return 0;
}

please help me...i didnt understand this questuion

cpp


#include <iostream>
#include <vector>

using namespace std;

void main()
{
vector <int> m_vec;

int m_in;
cout<<"Use control-z to stop"<<endl;

while(cin >> m_in )
{
m_vec.push_back(m_in);
}


vector<int>::size_type ix, i_max;
int m_max, m_min, m_remove;

m_remove=3;

for (int i=0; i!=m_remove; ++i)
{
m_max= m_vec[0];
i_max=0;

for (ix=1; ix!=m_vec.size(); ++ix)
{
if (m_vec[ix]> m_max)
{
m_max=m_vec[ix];
i_max=ix;
}

}
m_vec.erase(m_vec.begin()+i_max);

}

int m_avg=0;

double m_result=0;

for (ix=0; ix!=m_vec.size(); ++ix)
{
m_avg+=m_vec[ix];

}

m_result=(double)m_avg/m_vec.size();

cout<< m_result<< endl;
}

This one is O(n) to get the largest m numbers in an array of size n

public class AdviseredAverage
{
	public static double getAdviseredAverage(int[] list, int n)
	{
		if (n >= list.length)
		{
			System.out.println(" Input Error: n must be < list.length");
			return -1;
		}

		// Intialize elimination list
		int[] eliminationList = new int[n];

		// Initialize currentMin in elimination
		int currentMin = list[0];
		int currentMinIndex = 0;

		// Initialize sum to 0
		int sum = 0;

		for (int i = 0; i < n; i++)
		{
			eliminationList[i] = list[i];
			if (eliminationList[i] < currentMin)
			{
				// update minimum
				currentMin = eliminationList[i];
				currentMinIndex = i;
			}
			sum += list[i];
		}

		for (int i = n; i < list.length; i++)
		{
			if (list[i] > currentMin)
			{
				eliminationList[currentMinIndex] = list[i];

				// update minimum
				currentMin = eliminationList[0];
				currentMinIndex = 0;
				for (int j = 0; j < n; j++)
				{
					if (eliminationList[j] < currentMin)
					{
						// update minimum
						currentMin = eliminationList[j];
						currentMinIndex = j;
					}
				}
			}
			// add current number to sum
			sum += list[i];
		}

		// subtract largest n numbers from sum
		for (int i = 0; i < n; i++)
		{
			sum -= eliminationList[i];
		}
		return (double) (((double) sum) / ((double) (list.length - n)));
	}

	public static void main(String[] args)
	{
		int[] list = { 15,500,16,18,29,65,98,789,654,12,32,59,744,32,56,1254,12 };
		System.out.println(getAdviseredAverage(list, 5));
	}

}

simply use a heap man