I'm having a problem to solve this one. The task is to make a program that will for a given array of N numbers ( N <= 10^5 ), print a new array that's made by joining any two adjacent elements into their sum, (the sum is replacing these two adjacent elements and the size of the array is smaller by 1), until array's size is K. I need to print a solution where GCD of new elements is maximized. (and also print GCD after printing the array).
Note: Sum of all elements in the given array is not higher than 10^6.
I've realized that I could use prefix sum somehow because the sum of all elements isn't higher than 10^6, but that didn't help me that much.
What is an optimal solution to this problem?
Your GCD will be a divisor of the sum of all elements in the array. Your sum is not greater then 10^6, so the number of divisors is not greater than 240, so you can just check all of this GCDs, and it will be fast enough. You can check if asked gcd is possible in linear time: just go through array while the current sum is not the divisor of wanted gcd. When it is just set the current sum to 0. If you have found at least k blocks, it is possible to get current gcd (you can join any 2 blocks, and gcd will be the same).