Solution 3 for Scaler Topics Fortnightly Contest - 12

This article is part of the Scaler Topics Fortnightly Contest - 12

Build an AI-First Career, Master the Complete Skillset

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

NSDC Certified

AI Forward Deployed Engineer Program

Full-stack engineering, production AI and client-facing consulting

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

Solution Approach

• Note that the Brute force of $O(N^4)$ can be reduced to $O(N^3)$ by considering the fact that only tuple with property $j-i = l-k$ will be counted.
• Can you optimize it further?
• This question can be solved in $O(n^2)$ by mapping all elements into very big elements let's say in the range 1 to $10^15$ and the sum of subarrays can be used as hash values.
• Now we can just store the sum in the map to find an answer in $O(N^2)$.
• Note that a similar array must have the same sum, although the converse is not true: for example $1+3 = 2 +2$ but 1, 2, and 3 are randomly mapped to a very big integer.
• Thus the possibility of collision is very low.

C++ Implementation

Java Implementation

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation