We are given an array of integers of size ’n’. There is an infinite supply of each integer of the array. Now, for each index in the array, the task is to calculate all the possible ways in which the integer present at that index can be obtained by adding up 3 integers from arr[0], arr[1]…arr[i-1] (considering the calculation is being done for the index ‘i’). Since, there is infinite supply, repetition of one element is allowed, i.e., all the three integers can come from the same index of the array.

Constraints: Size of array could be as large as 10⁵

Astro is getting bored and want to play some interesting game. He noticed some random words written on a page of a book, and now he is wondering the maximum length of a palindrome that can be formed by concatenating any number of words.
Can you please help Astro?

Complete the 'maxConcatenatedPalindrome' function below.
The function is expected to return an INTEGER.
* The function accepts STRING ARRAY words as parameter.
Please complete the function maxConcatenatedPalindrome which takes following input:
int maxConcatenatedPalindrome (int words_count, char** words) {
words = List of strings

Integer denoting maximum length of a palindrome that can be formed by
concatenating any number of words and if no palindrome can be formed, return
Constraints
• The length of each string in words [] is at most 1000 characters.
• The number of strings in words [] is at most 1000.
•The total length of all strings in words [] does not exceed 10% characters.
• Each string in words[] can be used at most once.

Input
[words = ("ab", "ba", "xyx", "de");
Output:
7
Explanation: All possible words that are palindrome:
1. хух
2. abxyxba — by concating ab, ba, xyx
Hence the length of maximum word that can formed which is also a palindrome is 7

You have 5 jars of pills. Each pill weighs 10 grams, except for contaminated pills contained in one jar, where each pill weighs 9 grams. Given a scale, how could you tell which jar had the contaminated pills in just one measurement?