Array ( [0] => [1] => questions [2] => Arrays [3] => Contiguous-Square-Sum ) Arrays | Contiguous Square Sum | THE INQUISITIVE






Contiguous Square Sum

LEVEL:Beginner

Description

Let's consider some array A. The following algorithm calculates it's force:
1. Find all the continuous blocks where all the elemens of A are equal.
2. Calculate sum of squared lengths of these blocks.
For example if array A = {2, 3, 3, 1, 1, 1, 4, 2, 2} its force will be 12 + 22 + 32 + 12 + 22 = 19
We can reorder some elements and get array with greater force. In the example above we can move the first element of A to the end and get array A = {3, 3, 1, 1, 1, 4, 2, 2, 2} with force 22 + 32 + 12 + 32 = 23.
You are given an array. What is the maximum force you can get by reordering some of its elements?

Input Format

The first line contains integer T denoting the number of test cases. The following T lines contain 4 integers each: A[0], A[1], N, MOD.
Array A of N elements is generated by the following way:
A[0], A[1] are given
A[i] = (A[i - 1] + A[i - 2]) modulo MOD for 1 < i < N.

Output Format

For each test case output one integer on the separate line - answer for the question.


Example 1:

Input
2
0 1 6 4
1 1 10 3
Output
12
38
Example 2:

Input
3
1 2 8 3
2 3 10 5
4 2 6 4
Output
22
24
18
Example 3:

Input
4
10 12 18 13
22 13 10 15
24 23 16 14
14 32 20 25
Output
34
16
26
34

oops

Login to see Discussion




Approach

Approach1: Sorting
Step-i) Declare a new array of size n.
Step-ii) Iterate a for loop from 2 to n.
Step-iii) Assign values in new array as a[i]=(a[i-1]+a[i-2])%mod.
Step-iv) Now sort the array using any sorting algorithm.
Step-v) We can get the continuous block of elements by comparing the adjacent elements and finding the no. of same elements.
Step-vi) Add the square of length into other variable.
Step-vii) Finally return the sum.

Time Complexity: O(n logn)
Space Complexity: O(n)

Approach2: Frequency Counter

Step-i)Here we are using frequency array concept.
Step-ii)We are calculating the required array elements based on given formula.
Step-iii)At the same time we are incrementing the value postion in the frequency array.
eg: If value=3,then we are incrementing frequency array as frequency[value] i.e frequency[3].
Step-iv)Continue the same process until N value
Step-v)After that square value at every index in frequency array and add to sum.
Step-vi)Finally print the sum.

Time Complexity: O(n)
Space Complexity: O(10^6)


Note :

Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.

oops

Login to see Solution






     Recommended Questions      

Topic: Arrays

Beginner

1. Arithmetic Progression2. Geometric Progression3. Harmonic Progression4. No of triangles 5. Area of Polygon6. Trailing Zeros7. Min Platforms 8. Trapping Rain 9. Jump numbers10. Segregation of 0’s and 1’s11. Two SUM12. Triplet sum 13. Diagonal Sum14. Addition of two matrixes15. Subtraction of two matrixes16. Multiplication of two matrixes17. Transpose of given array18. Spiral Matrix19. Most Frequent Element20. Majority Element 21. Max difference 22. Odd occurring23. Second Largest and Second Smallest24. Next greater number25. Count Unique Elements26. Common elements 27. Removing Duplicates28. Balanced Array29. Rotating Array by k times30. Reverse Array31. Wave Array32. Merge arrays 33. Constraint Sort34. Find element in Sorted rotated array35. Sub Array Sum36. Largest subarray of 0’s and 1’s 37. K-Sub Array38. Max subarray sum39. Contiguous Square Sum