Compute Random Permutation

Compute Random Permutation

Problem Statement 

Design an Algorithm that creates a uniform permutation from (0 - n-1).  Given a random number generator that return a number (0 - n-1 ) with equal probability.

Use as few call to it as possible. 

Problem Solving

• Immediately I thought about the shuffle algorithm. However here we are provided with a number generator and have  to create an  array of unique elements. 
• If I try to put random numbers in iterative way then there will be duplication issues so we can try to avoid them by checking if they are already present using a set and regenerating again if already present this could be very expensive in practice. 
• So basically we somehow anyways need to check for duplicates as we will never know if the random generator has given us a duplicate. 
• But there is no way of controlling the generator to give a number in a smaller range. 
• I then tried filling up the array and shuffling it. however then again the init permutation will never be a result therefor not equally likely. 
• No wait that can work actually, if the random number generator and the last place to swap are inclusive. 
• It's working fine. Find code here.  

Learning

• I got lost in thought in this problem, may be due to self doubt. Since I originally thought of the shuffle approach but then from there I was getting lost. 
• I think this is because I left randomness in between and then am very hesitant to approach these problems. 
• Also this is a very nice code I have written very concise and clear code, feels good. 
• I should complete the things I have started. Not leave things in between.

Sudoku Checker

Sudoku Checker

Problem Statement

Given  a vector<vector<int>> of size 9*9. Check whether it is a valid Sudoku or not.  

Problem Solving 

• I thought of starting with Iterators, writing Iterators for row iterator a column iterator and square iterator. 
• This got me involved in a lot of Object Oriented Problem and how to implement == nicely. 
• That got me stuck on the double dispatch problem and further after few frustrated days, I found a book, Effective C++. 
• Now after having read that book and coming to chapter 2. I thought I had one solution and I restructured the Object modeling and yes it did work.
• This whole thing took a lot of time. around 2 weeks now. 
• Then I peeked in the book and answer in the book seemed very short and concise.
• Hah.. I think I created a complex solution to a simpler problem. 
• The solution in the book is very clean, basically instead of iterators and their complex hierarchy and initialization on objects this solution has a function that takes in a row_start , row_end, col_start, col_end and the original matrix. 
• Instantly I can see how easy it would be, the signature of the function would reveal it's algorithm. 
• But okay. I think this was a good learning. 
• The solution would be iterate all rows cols and sub matrices and check if anyone has duplicates. 
• checking for duplicates can be done via a set or bit vector. 

 Learning

• Multiple learning here. 
• First I think I should fork my problem solving skill from OO modelling skills. 
• So I have picked up a new book Programming Pearls. 
• All other learning were related to c++ and it's OO nature. 
• This took a lot of time and broke the rhythm. 
• I still do not know when is the time to give up and look in the book. 

Online Sampling

Online Sampling

Problem Statement

Write a program that takes a stream and reads value from it to maintain a random subset of k elements. 

Problem Solving 

• Instantly I think about a function that takes in a stream
• First fetches k values to fill a vector of size k. 
• On further input decides whether to take this element or not based on psuedo random number. 
• Then randomly select an index in the vector and write over that value the new value. 
• But I am not sure, If I understand the question correctly. 
• I'll probably code it and run it on the EPI judge and then get back here.  
• Well this does not work. 
• After understanding the solution which is quite similar with a stark difference which solves the issue. 
• The random number generator is used to generate numbers from 0 - all number seen till now. If that number lies in 0 - k range then we replace that index with the new number. 
• However here all subset generated in sequence only differ by 1 element. 

Learning

• I have clearly to do a deep dive in probability as I had trouble understanding what makes a subset really random. 
• The offline sampling problem gave a lot of clarity however this is new. 
• Also the new random num generation lib constructs in c++ 11 needs to be defunct. 
• Huh.. few tasks here. okay it's just okay to admit that there are few things I do not know and that as this progresses, so will I. 
• Keep on...

Offline Sampling

Offline sampling 

Problem Statement 

Write a program that taken a vector on n integers and return a random sample of size k. All sample must be equally likely. 

Problem Solving

• At first, I had trouble understanding what exactly is a sample,how do measure a probability of such a permutation. 
• After a while I thought that may be generating randomness could be used by a lib function like rand()
• We could use rand() k times to generate a number between 0-n and then selecting it. we will loop this until we have found unique k indexes. 
• This works however this does not sound about right. 
• To do this we also would require a set to store what indexes have been selected and whether a selected index is already used or not. 
• The only problem with this is the extra over head of first storing and searching in a set. 
• We could further remove this by moving the selected element to the end of the array and then using rand() only from 1 - (n-1) . This does it in linear time without the use of any extra memory. 
• Find Code here.

 

Learning

• This problem was hard to think and easier to understand and implement. 
• The key hint is that if you have k elements found how do you select the k + 1 element. 
• This problem is a really useful one as I had never solved this problem before. 
• Also this problem was once asked in some interview, the question was how to shuffle a deck of cards. 
• So yeah this is one key concept I have learned using this problem.

Next Permutation

Next Permutation

Problem Statement

Given a permutation M, return the next permutation.

Problem Solving 

•  In this problem, the first thing that clicks is to observe examples. 
• And after multiple attempts, I started seeing a pattern. 
• First of all we need to see if there is a next permutation. If the sequence is already in the descending order then there is no need to work on it. 
• So starting from the last element we need to find the first element in reverse order which is out of order. 
• Post that since we need the next permutation and the next permutation should only involve the element at the least place value. That means that we have to work with the element just next to the element that is found earlier. 
• Now we need to find an element in the range to swap it with. This came after a long time that the max element smaller than the eligible element should be swapped. 
• Here we can optimize since to find such a element in an already sorted array is a eay task. 
• Post swapping the new range should be sorted. But recalling that this sequence is already sorted we can just reverse it instead of sorting it. 
• The solution works but it took lot of time to figure out. 
• Find code here. 

Learning

• Doing examples is also frustrating emotionally until you let go of fear that you can do this. Doing these problems is raising confidence every day. I feel proud and confident. 
• Simple edge cases and off by error are really the take away. 
• Also reverse iterator to forward iterator = reviterator.base(0 but this is risky as it has a convoluted meaning.  
• I need to understand upper bound and lower bound as well as these are also confusing sometimes. 
• Overall the problem was solved and this time I paid attention to code writting it as consice as possible. 
• Also this time I first wrote it on paper and then on pc. 
• Altogether good, I am feeling the benefits of writing and pursuing this exercise.

Apply Permutation

Apply Permutation

Problem Statement

Write a program that takes a permutation array and a input array and reorder the input array as per the given permutation.

Problem Solving 

• I can see that this seems to be a linear time problem. 
• We need to apply permutation inc cycle.
• Start at 0 replace current position at 0 with previous input, swap previous input at current position. continue till end. 
• However there are multiple missing things in this solution. 
• As there can be multiple cycle in the same array. Therefore we need mechanism to break from cycle and then run on the next cycle. 
• To break the cycle we need to keep an bool index whether the position is processed or not. 
• and to go to next cycle we can always scan the processed array for non processed items and then start the process there. 
• This seems okay. 
• Find code here.  

Learning

• This question might seem simple but to implement it correctly is difficult. 
• Since I coded through the problem solving my code also looked tangled and complex. 
• After multiple debugging sessions and fixing problems. The code looked in a very bad shape. 
• However it passed all test cases. 
• Then I looked at the answer to find it to my surprise, that the code written is so much more elegant than what I had written. 
• However there is space optimization in the book's answer but ignoring that also the code was  much more simple. 
• Later I refactored my code into that shape. Felt both good and bad. 
• Writing good code is really really difficult. I understand it now. Everyone can code but to make proper sentences in the language is the art. To write pieces that are elegant and clear and concise. 
• Now that I have refactored it. It look good.
• Also one key insight is that whenever you feel like using an iterator that runs through all the elements in linear fashion use a for loop. and when needed to skip use continue or empty loop cycle. No need to write make complex iterator advances. 
• Small question lots of learning. 

Enumerate All Primes to N

Enumerate All Primes to N

Problem Statement

Write a program that takes an integer argument and returns all primes between 1 and that integer. 

Problem Solving

• There is not much of any solving here as I already know an ancient and well known algorithm for this. It's called the Sieve of Eratosthenes. 
• The idea is to create a list of all numbers to n. 
• Then iterate all number from two and at each number keep marking the multiples of those numbers as false or -1. 
• The iterate to the next non -1 number and do the same. 
• Find Code here. 

Learning

• Must always check for bounds. 
• The time complexity is n2 and space in O(n). 
• There is a way to save some space as the even numbers can be removed. 
• std::iota in the numeric header is a library function that can fill array with increasing numbers.
• There is also a Segmented Sieve which is used for large ranges and by segmenting them into smaller chunks
•  Since I could not understand all aspect of optimizations to this problem I am currently leaving behind this problem and moving on to next one.

Buy and Sell stock twice

Buy and Sell stock twice 

Problem Statement 

Given an array of stock prices on each day. Write a program that gives the maximum profit one can achieve by buying and selling a stock at most twice. 

Problem Solving

• Immediately I started to think like I solved the previous one stock problem and thought of instead of registering one max_profit I can register two maxprofits. 
• However this could make the complexity n*m where m is the number of times we can sell. 
• For eg. We would iterate the array looking for local minima and keep updating the max_profit array[2]. However we need to make sure that we evict the smallest of the profits. For 2 this could simple be a std::pair with wrapper. However for n elements we need to make a priority queue (earlier I thought of linklist which can cause quadratic runtime) which can make the eviction and insertion log n. That would make the total complexity be O(nlogm) 
• However as I saw in the book there is an linear order time complexity solution to this problem. 
• So I cheated and looked at the answer. I took me some time to understand and that's because If I would have spent some time thinking about how to optimize this solution to O(n) probably I would have fired my neurons which already know this technique because I remember I used this technique to solve the Google Interview question. That means somewhere in my brain this chain of thought is present it's only to reach that thought with reasoning. 
• So after writing about how guilty I feel, let move to the answer. 
• What we can do here is to understand that we need to make utmost 2 buy sell and strictly one after an other. 
• This one after an other also is a good hint for this technique. 
• So what we can do is that we iterate and store results from left to right and from right to left registering max_profit one could make only considering 0...i values and in the reverse array we would have max_profit from i+1 ... n. 
• Finally to get the answer we iterate both the arrays and get max of sum of both arrays and that  would be our answer. 
• One optimization that they have done here it that instead of doing the operation of calculating reverse and then adding they have clubbed the last two steps in the same array to save space and time. Smart ! 
• Find code here.

Learnings

• Do not jump to answers please. 
• This would not register in the brain properly if I haven't reasoned about it well and just looked at the answer. 
• The technique is good and easily understandable. 
• My original solution however is scalable. We can make it to calculate n sell and buy opportunities.  
• One good thing that happened was that once the algo was in my head I coded and it worked in first time without having to redo any algo changes. So that is a good sign. 

Buy and Sell Stock Once

Buy and Sell Stock Once

Problem Statement

Write a program that takes an array of stock prices and return maximum profit that can be made by buying and selling one stock. 

Problem Solving

• This question I have seen a hundred times, lets kill this once and for all. 
• So a list of array with number and we are interested in the max profit. 
• Max profit would be obtained by buying at a local minima followed by a local maxima. 
• The brute force way would be for each day consider buying and then calculate how much profit we get by selling on remaining following days.
• This would surely give correct ans with quadratic time complexity.  
• A linear approach would be to iterate through the array in ascending time and keep registering max_profit.
• At every element we check whether the element is a local minima if so the is it less than the current local minima, if yes then we update out buying option.
• Otherwise we continue iterating and registering max_profit. 
• Stop when we reach the last element.  
• Find code here.  

Learning

• Like the previous problem problem solving really is emotionally challenging despite being able to solve the problem in decent time. The emotional strength to face it is enormous. 
• Thinking the brute force way was obviously morale boosting that at least there is a way. 
• Further optimizing it was easy and confidence boosting. 
• I think I should now face problems with more confidence and these are really not that difficult. 
• One more thing, today this problem was solved without any compiler errors and in one go. 

Delete Duplicates From Sorted Array

Delete Duplicates From Sorted Array 

Problem Statement

Write a program that takes input as a sorted array and updates it so that all duplicates have been removed and the remaining elements have been shifted left to fill the empty indices.

Problem Solving

• We need to update the array in place.
• Something gives me intuition about iterating from left. 
• Now if I were to iterate from right then on encountering a duplicate I need to move it somewhere on the left but that would mess up the order. 
• I need to keep growing up a subarray of duplicate dump in the left. 
• Can we do something like the partition problem where we swap elements into respective groups. 
• One solution is to keep two iterators one tells which position to write as new elements other iterates through the array on each elements we check in a unordered set whether this elements if found or not if found then we move on else we update the write iterator with value on array_itr and then move on.
• This would require us to build a unordered hash set which can store all unique elements in the array and would cost space theta of n as we store exactly n elements in the set. 
• This idea will actually work with unsorted array too. that means this idea does not use the fact that the array is sorted. 
• Hence a better approach could be to iterate with two iterators like in the previous element but instead of checking each element in the set we iterate till we find a number that is not the last element found and update the write pointer.
• This seems to use the fact that we are bound to find duplicates in order and not random.
• Find Core here.

Learning

• Intuitions can be wrong, infact they can be exactly opposite.
• In case of ordering problems a quick way to find out that your solution is optimal is to check whether your solution works on if the elements we unordered. If so then you are not using the sorted information. Like in this case we achieved a better solution by detecting that our solution is agnostic to whether the given array is sorted.

Advancing through an Array

Advancing through an Array

Problem Statement

Write a program that takes an array of n integers, where A[i] denotes maximum we can advance from index i and return whether it is possible to reach the last index when started from the beginning  of the array. 

Problem Solving

•  A simple solution to this problem would be to calculate a max_reach at any given position and while iterating to reach the max_reach we keep updating it. If in the end we reach the end of an array then a solution is possible otherwise not.
• One optimization we can add it to stop iterating as soon as the max_reach becomes greater than size of the array. 
• Find Code here.

 Learning

• Lately I have realized that Problem Solving is as much a emotional task as it is a mental task. When we pick up a new problem all those imposter syndrome feelings and fear of unknown starts dwelling in. I worry more about the blow to confidence I would get if I could not solve this problem more than I think about how to solve the problem.

Multiply two arbitrary precision integers

Increment Arbitrary  precision number

Problem Statement

Write a program that takes two array B1 and B2 and return a new array with value B1 * B2 . 

Problem Solving

• Straight forward I think this is again a duplicate of high school method simulation. 
• We need to break down this into manageable chunks or functions.
• First we will take a two vector of integers and need a function to carry out multiplication of array with an int so we need a function for that.
• Once we are done with creating individual multiplication chunks. We need to add them with offsets as in school days. 
• So we need to separate the indexing with offset logic with the function that carries out actual addition. 
• In all these we need to maintain that all functions return correct values for individual inputs. This helps intensively in debugging. And that all functions return values in correct order, since we are using vectors here. we need to insert new elements at back which causes most computation to return values in reverse order so we need to reverse the final outputs for each function. 
• Find Code here. 

Learning

• The most difficult part was the offset addition. This added with complexity of reverse notion of number really hurt my brain. 
• However whatever doesn't kill you makes you stronger. 
• Also there were numerous compile time issues, this indicates I need to understand "const" in depth this causes me a lot of pain. 
• Also C++ compiler errors are extremely verbose or may be the right word is cryptic. May be some time will make me comfortable. 
• This was a difficult problem no doubt not in terms of problem solving but actual coding. 

 

Increment arbitrary precision number

Increment Arbitrary  precision number

 

Problem Statement

Write a program that takes an array of digits encoding a decimal number D and updates the array to represent the number D+1. 

Problem Solving

• Straight forward I can think of doing arithmetic as taught in school. 
• Add 1 to the last digit if the digit becomes more than 9 then carry repeat the process on the next digit. 
• Since we always increment the digit by 1 therefore we only need to check for digit 9.
• So we iterate the array in reverse order if the digit is non -9 then increment it by one and return else set it to 0 and keep iterating till end.
• If we reach the end that means that all digits were 9 hence we need to insert a 1 in the beginning. 
• Find Code here

 Learning 

• Due to one stupid mistake I learnt quite a few things here.   
• First since the google C++ style guide mentions that always take pointer as arguments if we wish to modify it. That makes the caller confident about what objects will be modified. 
• However to work with it we try not to use pointer in the callee function instead we cast it to a normal object. However if we try to write something like A a = *b. then a is a copy of value b. which is not what we want instead always do A &a = *b then a is a reference to the pointer value.
• This also gave me a better understanding about references and their uses in c++. 
• References are not variables that is they do not have any memory of there own they are just compiler syntactic sugar. 
• Overall the problem was naive. 
• Time complexity is linear while space is constant. 

Dutch National Flag Partitioning

Dutch National Flag Partitioning

Problem Statement

Partitioning is a common process used in other algorithms such a quicksort. In this problem, we are given an Array A and an index i. We have to rearrange A such that , all elements less than A[i] appears first followed by all elements equal to A[i] followed by all elements greater than A[i]. 

Problem Solving

• Not lying but since I have done such a problem sometime in past, this has quickly led me to think of using iterators that spans 3 ranges of less than, equal to and greater than values. 
• However the first question is to where to position each initially. 
• First I thought of positioning them at begin and end -1 position, but just initializing them there because we do not have other option is breaking the invariant that at any time those iterator should point to correct values. 
• Also there can be a case where all values are same then there would be no point in doing anything. 
• This also means that we should skip the part that is correct and hence post skipping we could arrive at the correct iterator location. 
• So first iterate from both ends and get to a location for both iterators where they are in accordance with the arrangement that left iterator has values less than A[i] and the right one has values greater than A[i] 
• when this process ends we would reach the exact range we need to actually rearrange and bonus point if there is no range left to process. 
• Once we reach this range. We need to create another iterator that starts at begin + 1, to iterate till right iterator. 
• at every point we check if the iterator is less than A[i] then we swap it with left itr and increment left itr and similarly if it is greater than A[i] then we swap it with right itr.
• And yes that should do it. 
• It should also be able to handle cases where all values fall into one range, since that we would skip at the beginning only.
• I wrote it, it failed and corrected it and ran correctly then. 
• Find Code here.

Learning  

• Never doubt yourself In the first attempt the answer came out wrong and I immediately jumped to the conclusion that the comparison mechanism is incorrect since I have recalled it from past memory. 
• However it turns out that all that was missing was one more iteration that I did not perform. 
• This also makes me aware of the fact whenever we talk about iteration we need to be accurate about what are iteration limits. 
• The complexity for this solution straight forward is constant since we are only swapping elements by traversing the array once and no extra memory is required. 
• Also I learned the best way to swap elements of iterators are iter_swap a built in function in algorithms library. 
• Hmm.. simple one but panic caused a lot of time waste.   

Cops and the Thief Devu

Link here.

There are 100 houses located on a straight line. The first house is numbered 1 and the last one is numbered 100. Some M houses out of these 100 are occupied by cops.

Thief Devu has just stolen PeePee's bag and is looking for a house to hide in.

PeePee uses fast 4G Internet and sends the message to all the cops that a thief named Devu has just stolen her bag and ran into some house.

Devu knows that the cops run at a maximum speed of x houses per minute in a straight line and they will search for a maximum of y minutes. Devu wants to know how many houses are safe for him to escape from the cops. Help him in getting this information.

Input

First line contains T, the number of test cases to follow.

First line of each test case contains 3 space separated integers: M, x and y.

For each test case, the second line contains M space separated integers which represent the house numbers where the cops are residing.

Output

For each test case, output a single line containing the number of houses which are safe to hide from cops.

Constraints

• 1 ≤ T ≤ 10⁴
• 1 ≤ x, y, M ≤ 10

Example

Input:
3
4 7 8
12 52 56 8
2 10 2
21 75
2 5 8
10 51

Output:
0
18
9

Explanation

Example 1 : Cops in house 12 can cover houses 1 to 68, and cops in house 52 can cover the rest of the houses. So, there is no safe house.

Example 2 : Cops in house 21 can cover houses 1 to 41, and cops in house 75 can cover houses 55 to 95, leaving houses numbered 42 to 54, and 96 to 100 safe. So, in total 18 houses are safe.

Problem Solving

• First thing to notice is that it's a range problem. Given a range 1-100 we have to subtract ranges.
• Simple math tells us that for every Mi range for that cop is i +- x * y. Current position + (speed * time) (distance) the cop can cover.
• Now we have 1-100 range and have to subtract all Mi ranges and leftover will be our answer. 
• We need to calculate the total sum of ranges, excluding the overlaps and finally subtract the the total from 100, to get safe houses. 
• I mistakenly read the problem to output the indexes of houses, however now thinking about it that would have been a different problem.
• We can create a list of ranges and while adding a range to list merge the range if required to make a bigger range. Finally we can compute the total sum of the ranges in the list and subtract that from 100. 
• Here to make a list we can use std::vector, to represent a range we can use std::pair 
• Also while merging we need to search through all merges possible therefore if we can maintain a sorted list then the while merging we only have to check the last element. 
• Therefore we have to sort the houses list first and then give it to adding range. 
•  The submission went successful here.

Learning 

• I have a feeling that we can still improve this complexity of mlogm, if we would know how to store ranges properly. 
• May be in future we can study such  data structures. 
• We also used a built in sorting function which currently we have not implemented, so going forward we need to learn about sorting. 
• Since in the certification course all sample problems are done, I would pick up problems from "Elements of Programming Interview" to cover more array and vector problems. 

 

Chef and Rainbow Array

Link to problem here.

Chef likes all arrays equally. But he likes some arrays more equally than others. In particular, he loves Rainbow Arrays.

An array is Rainbow if it has the following structure:

• First a₁ elements equal 1.
• Next a₂ elements equal 2.
• Next a₃ elements equal 3.
• Next a₄ elements equal 4.
• Next a₅ elements equal 5.
• Next a₆ elements equal 6.
• Next a₇ elements equal 7.
• Next a₆ elements equal 6.
• Next a₅ elements equal 5.
• Next a₄ elements equal 4.
• Next a₃ elements equal 3.
• Next a₂ elements equal 2.
• Next a₁ elements equal 1.
• a_i can be any non-zero positive integer.
• There are no other elements in array.

Help Chef in finding out if the given array is a Rainbow Array or not.

Input

• The first line of the input contains an integer T denoting the number of test cases.
• The first line of each test case contains an integer N, denoting the number of elements in the given array.
• The second line contains N space-separated integers A₁, A₂, ..., A_N denoting the elements of array.

Output

• For each test case, output a line containing "yes" or "no" (without quotes) corresponding to the case if the array is rainbow array or not.

Constraints

• 1 ≤ T ≤ 100
• 7 ≤ N ≤ 100
• 1 ≤ A_i ≤ 10

Subtasks

• Subtask 1 (100 points) : Original constraints

Example

Input
3
19
1 2 3 4 4 5 6 6 6 7 6 6 6 5 4 4 3 2 1
14
1 2 3 4 5 6 7 6 5 4 3 2 1 1
13
1 2 3 4 5 6 8 6 5 4 3 2 1

Output
yes
no
no

Explanation

The first example satisfies all the conditions.

The second example has 1 element of value 1 at the beginning and 2 elements of value 1 at the end.

The third one has no elements with value 7 after elements with value 6.

Problem Solving 

• This seems to be a palindrome problem. 
• However this is incorrect, the input is mean to have increment by 1 at each step.
• Following from that one can clearly see that the N should be odd to satisfy these properties. 
• This gives us an early exit the range of values are small and we do not have to perform any operation other than comparison. So overflow is not possible.
• For space we need to store at least half of the array before we can start comparing the other half.
• A Stack looks to be more suitable for this problem. But we will implement an Stack later in syllabus under that section. 
• We can also carefully implement this recursively and use the native stack space instead of allocating memory ourselves. 
• One more issue here is that the size of the array should be decided at run time, which our array cannot do so we have to use a vector data structure, as discussed in previous post.
• Okay, So the submission went unsuccessful here. 
• It gives TLE, that means there is unseen problem that I have missed. 
• Okay so I found the glitch and solved it here, The problem was we were contructing the vector with N/2 capacity but then pushing back instead of using the allocated memory which for bigger inputs caused bad::alloc(). However it now says Wrong Answer. 
• Okay realized that we can ignore N < 3. checking for more ideas.
• Okay so misinterpreted the problem itself, the numbers appears to have meant that the numbers should grow up to 7 and come back to 1. In our case we just checked whether the numbers are increasing first and then decreasing to form a palindrome. 
• Okay so I submitted another solution which passed half of the task, one still remaining. I just capped my approach up to 7. Submission here. 
• Also that N < 3 should be changed to N < 13. Submission here
• After successive failures and beating up confidence to this "CAKEWALK" difficulty, I thought that I am just trying to fix my solution even after the original solution I wrote was thinking about misinterpreted problem. 
• So I wrote from scratch again, this time I created state machines, basically two functions one which validates increasing values till mid array and the other which validates decreasing through rest of the array. Through the traversal we keep the count of 1-7 numbers and while decreasing we keep decrement the count so that while changing the number or in the end the count should be 0. 
• Also learned, that std::array does not create zero initialized array - use array.fill to do that. here
• After few off by 1 errors and edge cases, this submission went through here. 
• Also learned that premature optimizations really bite in the ass if you are actively modifying the code. 
• This problem was easy to think, difficult to code and hard to interpret correctly. 
• In the end, this problem was easily solved by arrays only no vector required.

Vectors

Vectors

Just like arrays, vectors use contiguous storage locations for their elements, which means that their elements can also be accessed using offsets on regular pointers to its elements, and just as efficiently as in arrays. But unlike arrays, their size can change dynamically, with their storage being handled automatically by the container.

Usage 

• Store any type of data 
• Insert in amortized O(1)
• Remove in O(1) 
• Access in O(1)
• Size not known at compile time

Note

• Since vectors are more suitable to situations instead of arrays they are extensively used in all applications. 
• Vectors in java implements List interface and are synchronized.
• Vectors in C++ are sequence container. 

Vector Implementation

• The following implementation let's us create a vector with any int size.
• Default constructor creates a vector of size 2. 
• The container provides options to access and iterator to traverse the vector. 
• The container also provides push_back to add elements at the end of current last element. 
• The container also provide direct access to front and back elements 
• On Push back of the last element the container resizes to twice the capacity. It allocates new memory then copies original content swap unique pointers and reset the raw pointers. The local unique pointer variable goes out of scope and hence deletes the previous allocated memory. 
• The container also shrinks when the usage drops below half the current capacity.
• Since the vector internally allocates C array the memory allocated is contiguous.

Learning 

• C++ Vectors also have emplace_back function which leverages rvalue references to forward parameters to the container instead of creating temporaries like push_back. Read here
• Vector<bool> is a specialized version of vector and is not recommended to be used in Google Style guide. Read here
• std::swap is specialized for unique_ptr Read here. 
• std::vector also have overloaded operators  like equality and comparison. Read here
• One important question to answer is what's the complexity of inserting in a vector. 

Insert Complexity

• Now vectors have 2 main insert operations an inexpensive one and an expensive one. 
• If we always consider the worst case scenario as in terms of Big O, the expensive operation have order O(n) complexity and since we insert n5 elements the overall worst case analysis shows that complexity will be O (n^2). 
• However this is not true as the number of expensive operations does cannot occur on every insert. 
• Since the number of inexpensive operation increases and are often more than the number of expensive operation , we need to analyze this differently. 
• Amortized analysis is complexity analysis over a range of operations rather a single operation. 
• In this scenario, an amortized analysis means than while inserting n elements what is the overall cost of single insert operation. 
• Now if we see, there are two operations one inexpensive i.e O(1) when we  do not expand the vector, the other is expensive one where we allocate new memory and the copy the original elements to new memory taking O(2 ^ k) operations, where k is an intermediate value < n. 
• For reason that expand only happens on 2^k + 1 elements, 
• Therefore total number of operations = num of inexpensive operations * cost of light operations + num of expensive operations * cost of expensive operations. 
• Number of expensive operations = (2 + 4 + 8 + 16 ... + 2 ^ l) where l is the largest integer such that 2^l + 1 < n. 
• if we look at it the other way say n is the final size of the vector, therefore this expensive operations will occur n/2 + n /4 + n/ 8 + n/16 + ... + 1 which is almost equal to twice 2n. here
• Therefore the total operations will be somewhere n + 2n = 3n. 
• Dividing this by total number of inserts gives us a constant 3 .
• Therefore the amortized complexity  of inserting in a vector is O(1) .

The Minimum Number Of Moves

The Minimum Number Of Moves

Little chief has his own restaurant in the city. There are N workers there. Each worker has his own salary. The salary of the i-th worker equals to W_i (i = 1, 2, ..., N). Once, chief decided to equalize all workers, that is, he wants to make salaries of all workers to be equal. But for this goal he can use only one operation: choose some worker and increase by 1 salary of each worker, except the salary of the chosen worker. In other words, the chosen worker is the loser, who will be the only worker, whose salary will be not increased during this particular operation. But loser-worker can be different for different operations, of course. Chief can use this operation as many times as he wants. But he is a busy man. That's why he wants to minimize the total number of operations needed to equalize all workers. Your task is to find this number.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the number of workers. The second line contains N space-separated integers W₁, W₂, ..., W_N denoting the salaries of the workers.

Output

For each test case, output a single line containing the minimum number of operations needed to equalize all workers.

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 100
• 0 ≤ W_i ≤ 10000 (10⁴)

Example

Input:
2
3
1 2 3
2
42 42

Output:
3
0

Explanation

Example Case 1. Chief can equalize all salaries in 3 turns:

Turn ID	IDs of involved workers	Salaries after the move
1	1 2	2 3 3
2	1 2	3 4 3
3	1 3	4 4 4

Problem Solving

1. This problem took me some time to grasp. Do not think otherwise but the issue here is that I did jump on solving the solution, however first I wanted to formally convince myself that a solution to this problem exists.
2. Turns out that no one on the editorial or discussion have answered this issue. How do I know that in any configuration of W there will exist a solution where are salaries will be equal after performing the mentioned operation multiple times. 
3. So to do that I thought of using induction, Clearly if f -> true when the solution to problem exists then f(1) is always true, because for 1 worker all salaries are already equal & number of operations are also = 0. 
4. Thinking about f(2), if there are only 2 workers and since this operation always increases the value therefore the min moves would be to make the salary of the lesser worker equal to the worker whose salary is more i.e (Max(W[])-Min(W[])) number of moves. and also that the solution does exists. 
5. So lets assume that f(k) -> true. with some X operations. 
6. If we can argue that f(k + 1)  is also true then we would conclusively prove that a solution to this problem exists for every k >0.
7. Now for f(k+1) out of k + 1 lets partition them in 2 groups of k say G1 and  1 say G2, such that the group G2 has only one element which is the max element of all k + 1 elements, 
8. Now the group G1 is solvable by induction hypothesis - (5) by X operations. 
9. That means that the after performing X operations in all k+1 elements where we always choose candidate for operation from group G1, the final value of G2 would be value of G2 elements + X. (since each operation will expand the G2 group by 1. 
10. Now the final configuration after X operations would be that all salaries in G1 group would be equal say equal to E and G2 group salary would be increased by X. 
11. Finally we can perform X - E operations by always selecting G2 candidate and so that G2 candidate never increases and the rest in  G1 which were equal already would all increase to be equal to G2. 
12. Therefore all salaries can be made equal. QED 
13. So I convinced myself that a problem can be solved. 
14. Now for the number of operations, also took sometime to ponder, If the only operation is increase all but one, that means that the minimum number of the set should dictate the number of operations. 
15. Doing sample examples would show that keeping max as the candidate and pulling up all the rest will yield the min number of operations. 
16. Now this is tricky to imagine but if you pull up your min to the successor on the min value, then we have a case just like in the proof, where we try to make all other equal and then finally we can just move all except for the one that is max. So we can try pulling up min to the next min in every iteration. 
17. This operation sequence will give us the min operations required. 
18. However instead of modelling this behavior, one can calculate how many operations does that mean. 
19. That means that in each iteration I make min equal to a next element therefore for every element this happens equal to the difference to the min value. 
20. Therefore E (0,n) (Wi - min(w)) is the answer. 

• For implementation 
• we can see that most variables are in int range and the summation would max to 10^4 * 100 = 10 ^ 6 which is also integer range. so no overflow requirements. 
• Next we see that we can find the summation and min elements in one scan of the input and the compute the answer so time can be O(1) and space also O(1).  
• No extra edge cases here. 
• The submission went successful here . 

Learning 

• Proof by induction was the best thing about this problem solving. The ability to convince oneself that yes there is a solution is great, also it provides insights to solve the actual problem.
• The problem can seem much easier if one thinks in a relative aspect. Since the only thing that matters is that all salaries become equal so the operation can also be thought of pushing one salary down each time instead of pulling all salaries except for one. In relative terms these are the same thing. 
• The relative aspect is great but to get the final salary, it becomes is difficult. 
• The final salary in the above approach is easy to think as min + number of total operations. (since in each operation the min have always increased, and the min was never a candidate to not increase the salary, the final = min + num of operations) 
• This problem was of cake walk difficulty, however it took me some time to ponder on the details. A lot of time compared to time requirements  of competitive programming. 
• This however should not sadden me, as my goal here is to learn and solve everything instead solve it fast. 
• Let's see what other problems have to offer. :)