COURSES
MBAData Science & AnalyticsDoctorate Software & Tech AI | ML MarketingManagement
Professional Certificate Programme in HR Management and AnalyticsPost Graduate Certificate in Product ManagementExecutive Post Graduate Program in Healthcare ManagementExecutive PG Programme in Human Resource ManagementMBA in International Finance (integrated with ACCA, UK)Global Master Certificate in Integrated Supply Chain ManagementAdvanced General Management ProgramManagement EssentialsLeadership and Management in New Age BusinessProduct Management Online Certificate ProgramStrategic Human Resources Leadership Cornell Certificate ProgramHuman Resources Management Certificate Program for Indian ExecutivesGlobal Professional Certificate in Effective Leadership and ManagementCSM® Certification TrainingCSPO® Certification TrainingLeading SAFe® 5.1 Training (SAFe® Agilist Certification)SAFe® 5.1 POPM CertificationSAFe® 5.1 Scrum Master Certification (SSM)Implementing SAFe® 5.1 with SPC CertificationSAFe® 5 Release Train Engineer (RTE) CertificationPMP® Certification TrainingPRINCE2® Foundation and Practitioner Certification
Law
Job Linked
Bootcamps
Study Abroad
Master of Business Administration (90 ECTS)Master of Business Administration (60 ECTS)Master in Computer Science (120 ECTS)Master in International Management (120 ECTS)Bachelor of Business Administration (180 ECTS)B.Sc. Computer Science (180 ECTS)MS in Data AnalyticsMS in Project ManagementMS in Information TechnologyMasters Degree in Data Analytics and VisualizationMasters Degree in Artificial IntelligenceMBS in Entrepreneurship and MarketingMSc in Data AnalyticsMS in Data AnalyticsMaster of Science in AccountancyMS in Computer ScienceMaster of Science in Business AnalyticsMaster of Business Administration MS in Data ScienceMS in Information TechnologyMaster of Business AdministrationMS in Applied Data ScienceMaster of Business AdministrationMS in Data AnalyticsM.Sc. Data Science (60 ECTS)Master of Business AdministrationMS in Information Technology and Administrative Management MS in Computer Science Master of Business Administration MBA General Management-90 ECTSMSc International Business ManagementMS Data Science MBA Business Technologies MBA Leading Business Transformation Master of Business Administration MSc Business Intelligence and Data ScienceMS Data Analytics MS in Management Information SystemsMSc International Business and ManagementMS Engineering ManagementMS in Machine Learning EngineeringMS in Engineering ManagementMSc Data EngineeringMSc Artificial Intelligence EngineeringMPS in InformaticsMPS in Applied Machine IntelligenceMS in Project ManagementMPS in AnalyticsMS in Project ManagementMS in Organizational LeadershipMPS in Analytics - NEU CanadaMBA with specializationMPS in Informatics - NEU Canada Master in Business AdministrationMS in Digital Marketing and MediaMS in Project ManagementMaster in Logistics and Supply Chain ManagementMSc Sustainable Tourism and Event ManagementMSc in Circular Economy and Sustainable InnovationMSc in Impact Finance and Fintech ManagementMS Computer ScienceMS in Applied StatisticsMS in Computer Information SystemsMBA in Technology, Innovation and EntrepreneurshipMSc Data Science with Work PlacementMSc Global Business Management with Work Placement MBA with Work PlacementMS in Robotics and Autonomous SystemsMS in Civil EngineeringMS in Internet of ThingsMSc International Logistics and Supply Chain ManagementMBA- Business InformaticsMSc International ManagementMS Computer Science with AIML ConcentrationMBA in Strategic Data Driven ManagementMaster of Business AdministrationMSc Digital MarketingMBA Business and MarketingMaster of Business AdministrationMSc Digital MarketingMSc in Sustainable Luxury and Creative IndustriesMSc in Sustainable Global Supply Chain ManagementMSc in International Corporate FinanceMSc Digital Business Analytics MSc in International HospitalityMSc Luxury and Innovation ManagementMaster of Business Administration-International Business ManagementMS in Computer EngineeringMS in Industrial and Systems EngineeringMSc International Business ManagementMaster in ManagementMSc MarketingMSc Business ManagementMSc Global Supply Chain ManagementMS in Information Systems and Technology with Business Intelligence and Analytics ConcentrationMSc Corporate FinanceMSc Data Analytics for BusinessMaster of Business AdministrationMaster of Business Administration 60 ECTSMaster of Business Administration 90 ECTSMaster of Business Administration 60 ECTSMaster of Business Administration 90 ECTSBachelors in International Management
For College Students

Maximum product quadruple in an array

$$/$$

You are given an array, you are asked to find the maximum product quadruple in the array, i.e. the largest product that can be obtained by multiplying four numbers in the array.

 

Examples:

  1. Input: [ 11 ,3 ,5 ,6 ,23 ,1 ]
    Output: 7590 ( 11 X 23 X 5 X 6)
  2. Input: [ -10, -35, 2 ,3, 45 ,5 ]
    Output: 78750 ( -10 X -35 X 45 X 5 )
$$/$$

Now that you’ve found out the simplest way, is there a way the process can be optimised because of the time complexity of  ?
A better way would be to sort the array, and then have 3 integer variables, x, y, z, storing the values of - 

x: Product of first two and last two elements of the array - arr[0]*arr[1]*arr[n-2]*arr[n-1]
y: Product of the last four elements of the array - arr[n-4]*arr[n-3]*arr[n-2]*arr[n-1]
z: Product of the first four elements of  the array - arr[0]*arr[1]*arr[2]*arr[3]

then you compare x, y, z, and return the maximum.

 

Once the array is sorted, it is not necessary that the last four numbers of the array would give the maximum product always. There may be some negative numbers whose absolute value is greater than the last four numbers. In such cases, the product of 4 negative numbers or 2 negative and 2 positive numbers can result in the maximum product. See the below example for better understanding.

 

Example:

Suppose the array is {10,20,30,40,50,60,70,80,-90,-100}, then the sorted array will be {-100,-90,10,20,30,40,50,60,70,80}

x = -100*-90*70*80 = 50400000

y = -100*-90*10*20 = 180000

z = 50*60*70*80 = 16800000

As already mentioned, you can compare x, y, z values and return the maximum.

$$/$$

 

Till now you have seen how to get the required quadruple using the brute force approach in O() time complexity, then we tried to minimise the time complexity to O(n log n) by sorting the array and then applying some logic.

 

Another efficient approach is solving the problem in O(n) time complexity by simply traversing the array and while traversing, maintain eight variables, four to maintain the first four maximum elements of the array and four to maintain the first four minimum elements, and then calculate the following:

      x = firstMax * secondMax * thirdMax * fourthMax.

      y = firstMin * secondMin * thirdMin * fourthMin

      z = firstMin * secondMin * firstMax * secondMax

Maximum of x, y, z is the required answer.