Divisible subarrays tle

#1

https://ide.codingblocks.com/#/s/14807I used dp for this problem.
Any other way?

Thankyou

1 Like
#2

Yeah, via Pigeonhole Principle in O(n).
Refer this : Divisible Arrays - Interesting Pigeonhole Application - Problem Analysis by Prateek Narang

#3

thank you :nerd_face::nerd_face:

#4

Changed code
Applied pigeonhole still not showing correctly for the 2nd test case.

Problem solved. Nothing to worry

#5

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[1000005], prefixsum[10000005];
int main(){

int n;
cin>>n;
ll sum=0;
memset(prefixsum,0,sizeof prefixsum);
prefixsum[0]=1;
for(int i=0;i<n;i++){
	cin>>a[i];
	sum+=a[i];
	sum%=n;
	sum=(sum+n)%n;
	prefixsum[sum]++;
}
ll ans=0;
for(int i=0;i<n;i++){
	cout<<prefixsum[i]<<" ";
}

}

pls help error in prefixsum array not giving the correct output

#6

what is the complexity of your code