PREREQUISITES:
BRUTE FORCE IMPLEMENTATION
PROBLEM:
Explanation:
As we scan array only one time complexity is O(N).
SOLUTION:Solution
DIFFICULTY: EASY
PREREQUISITES:
BRUTE FORCE IMPLEMENTATION
PROBLEM:
Two friends toss the coin and play k moves of a game. Let's denote two friends as X and Y.Given an array A of length N: N<=100. Player who wins toss can choose any Ai for each valid i, then players can move this index by 1 to left or right.Find the value of element at end of game if both players play optimally.
Explanation:
If K is odd then play who wins the toss will move at last. So if X wins then answer will be maximum element of Array and if Y wins then answer will be minimum element of Array. If X wins the toss and K is even then he knows that Y is going to make the last move so he choose such index so that min(A[i+1],A[i-1]) is maximum possible because Y will move this index to minimum of neighbour and X will undo it until last move when element will be min(A[i+1],A[i-1]). Same can be computed if Y wins the toss and K is even.
Please left comment if you have any other approach or doubt.
TIME COMPLEXITY:
Solution
PREREQUISITES:
BRUTE FORCE IMPLEMENTATION
PROBLEM:
Explanation:
Solution
1 Like