Divisilble subarray

#1

One test case like n =5
5 5 5 5 5
sum = 25 then 25/5 = 5
but in output given as 15 . I didn’t get this ?

#2

@Vikaspal you have to calculate the number of good subarrays, how did you come up with the formula of 25/5 ?
5 5 5 5 5
0 1 2 3 4
You can count the good subarrays as (including indices)

  1. 0
  2. 0 1
  3. 0 1 2
  4. 0 1 2 3
  5. 0 1 2 3 4
  6. 1
  7. 1 2
  8. 1 2 3
  9. 1 2 3 4
  10. 2
  11. 2 3
  12. 2 3 4
  13. 3
  14. 3 4
  15. 4

As you can see the total number of subarrays is 15, so we report the answer as 15

1 Like
#3

thanks @IshitagambhirI got the intution.

#4

@Vikaspal please mark the doubt as resolved if you are satisfied

#5

|ai|<=10^9 means the every element of can take max 10^9 = 1000000000 but when i store in a integer like this int a=1000000000 after print out a then it will working fine

#6

@Vikaspal constraints not only hint you about the data type that you should use but also about the complexity of the program. This is why reading them carefully is necessary, Your code is working in this case but when you go to more difficult problems having a lengthy approach might give TLE for one constraint,and might pass for some other.

#7

To avoid the TLE we should come up with solution less than 10^18 ?

1 Like
#8

@Vikaspal is your current code giving you any errors?

#9

@Ishitagambhir the test case is not passing

#10

@Vikaspal is it giving TLE or wrong answer?

#11

@Ishitagambhir TLE the answer is correct the execution time is slow

#12

@Vikaspal you have to apply the concept of pigeonhole principle in this question. Brute force has o(n^2) complexity

#13

@Ishitagambhir yes , but i didin’t understand the concepts

#14

@Ishitagambhir can you check this piece of code
#include
using namespace std;

int squareNum(int num) {
int square =0;
int last_digits=0;
while(num >= 1) {
last_digits = num%10;
square += last_digits * last_digits;
num = num/10; // remove one digits from the number
}

return square;

}

bool isHappy(int num) {
int happy=0; // by default number is not happy
int result=0;
while(1) { // true make infinite loop
result = squareNum(num);
if(result == 1) {
happy = 1;
break;
}
}
return happy;
}

int main() {
int num;
cin >> num;
cout << isHappy(num) << endl;
return 0;
}

#15

@Vikaspal what did you not understand? I suggest you go through the video again and focus on the application part and try to code it. If you are still stuck let me know :slight_smile:

#16

@Ishitagambhir okay i will do it

#17

@Ishitagambhir
In this problem, I am not able to understand the combination part after we have calculate the cumlative sum with %n. then we get the array like that 0 1 4 1 2 1 can you explain that ?

#18

@Vikaspal see after this step, the pigeonhole principle says that there must exist at least 2 elements in the resultant array such that their value is the same. This gives you the values of the subarrays.
for eg, here 1, 3, and 5 index have same value, ie 1. So now our subarray is from (index1, index2]
you have the indices, you have to make nC2 pairs now.
Another example,

array : 1 2 3 4 5
c_sum: 0 1 3 6 10 15
c_sum % n: 0 1 3 1 0 0
see now there are multiple repeating values, so what you can do is make a frequncy array for (0 -> n -1)
freq arrat: 3 2 0 1 0
if freq >= 2
calculate nc2 and add to answer

#19

when wre are making the frequency as in the above example
0 1 3 1 0 0
fre[] = 3 2 1 X X
if we make the frequency then 0 appears 3 times, 1 appear 2 and 3 one times . I didn’t get the order in which the fre arry is made

#20

the Frequency array follow the order in based on the index of the array
0 1 2 3 4 index then fre 3, 2, 0 , 1 ,0 Right?