Solution 3 for Scaler Topics Fortnightly Contest - 26
How many Divisions?
This article is part of the Scaler Topics Fortnightly Contest - 26
Transform Your Career
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
Solution Approach
Notice that, when we end a subarray after index i, what will be the total change in the sum. The subarray number of each element after i would increase by 1. So, if we end a subarray after i, the sum would increase by the suffix sum after index i. So, if the suffix sum is greater than 0, we should end the subarray at i, if it is less than 0, we shouldn’t end the subrray. But if it 0, we have 2 options, we may or may not end it. So, it would create 2 possibilities. So, the total number of ways to divide is 2 powered by the number of non-empty suffixes with sum equal to 0. We also ignore the suffix containing the whole array.
Time Complexity: O(|A|) Space Complexity: O(|A|)
C++ Implementation
Java Implementation
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ more
