public static int timeComplexityOptimized(int[] input){

		if(input.length <=0){
			System.out.println("Input array contains no elements");
			return 0;
		}

		int sum = 0;
		int mostCommonInteger = input[0];			// To store the most common integer
		int highestReoccurrenceCount = 0;			// To store the repeat count
		
		int noOfComparisons = 0;					// To measure time complexity
		
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();

		for(int i=0; i<input.length; i++){		//Runs from 0 to N-1 where N is input size
			noOfComparisons++;
			if(map.containsKey(input[i])){
				int reoccurrenceCount = map.get(input[i]) + 1;			//If element available in the map the increment its reoccurence count stored as its value
				if(highestReoccurrenceCount < reoccurrenceCount){
					highestReoccurrenceCount = reoccurrenceCount;
					mostCommonInteger = input[i];
				}
				map.put(input[i], reoccurrenceCount);
			}else{
				if(highestReoccurrenceCount < 1){
					highestReoccurrenceCount = 1;
					mostCommonInteger = input[i];
				}
				map.put(input[i], 1);
			}
		}

		if(highestReoccurrenceCount > 1){
			System.out.println("\n*****************  Time Complexity Optimized O(n)***************************************");
			System.out.println("Input Array Size = "+ input.length);
			System.out.println("NoOfComparisons to find the solution = " +noOfComparisons);
			System.out.println("Most Common Integer = " + mostCommonInteger +" with repeating count = "+ highestReoccurrenceCount);
			sum = mostCommonInteger * highestReoccurrenceCount;		// Step to calculate the most common integer's sum
			System.out.println("Sum of Most Common Integer = "+ sum);
		}else
			System.out.println("No re-occuring element in the array");
		return sum;
	}