/**Set of methods used in Lectures on Complexity*/
public class BaseMethods {
	
	/**calculate the sum of squares of the first n integers*/
	public static int squares1(int n){
		int i=0;
		int sum=0;
		while (i<n){
			i++;
			sum+=i*i;}
		return(sum);
			
		}
	
	/**faster version*/
	public static int squares2(int n){
		int sum=(n*(n+1)*(2*n+1))/6;
		return sum;
	}
	
	/**calculate the integer part of the square root of n*/
	public static int intSqrt1(int n){
		int i=0;
		while((i+1)*(i+1)<=n) i++;
		return i;
	}
	
	/**faster version */
	public static int intSqrt2(int n){
		int l=0;
		int h=n;
		int d=0;
		while (h!=l+1){
			d=(l+h)/2;
			if(d*d<=n) l=d;
			else h=d;
		}
		return l;
		
	}
		
	

	public static int [] prefixAverages1(int [] x){
		int [] a = new int [x.length];
		for (int i=0;i<a.length;i++){
			int b=0;
			for (int j=0;j<=i;j++)
				b=b+x[j];
			a[i]=b/(i+1);
				
			}
		return a;
		}
	
	/**faster version*/
	public static int [] prefixAverages2(int [] x){
		int [] a = new int [x.length];
		int s=0;
		for (int i=0;i<a.length;i++){
			s=s+x[i];
			a[i]=s/(i+1);
		}
		return a;
		}

	
	
	
	}