Please enable JavaScript.
Coggle requires JavaScript to display documents.
HACKER RANK PROBLEMS - Coggle Diagram
HACKER RANK PROBLEMS
beautiful array
minimal sum
is it possible to have more than one beautiful array
optimize the number of swaps to reach the beautiful array
what to if more than one possible beautiful array
like if we reverse one of the beautiful array we will still end up with a beautiful array
given array
distinct integers
does this imply that the beautiful array is the array which is sorted ascending or descending order
is this related to distinct integers ??
if we can show that the beautiful array is the sorted array
then the question changes to converted the given array to a sorted one with minimum number of swaps
how to solve this
will the number of swaps required for ascending and descending be different
NO NO
2 more items...
argue with the fact that if each of the terms in the sum is minimum then the total sum is also the minimum now each term will only be minimum if the array is sorted
two general optimization ideas
find all possible and then find the minimum by comparison
at each step insure iptimality and directly get the most optimal solution
steps involved(breaking the problem )
first approach
first find the beautiful array for the given array
how ?
then find all possible ways to convert from given array to the beautiful one
hint infinite possibility this method may not work needs something more
then find the minimum among them
second approach
convert the given array into the beautiful in the best possible way
simultaneously keep track of the number of swaps
given this is an optimization problem it may be solved efficiently by dynamic programming
separate the string into numbers
split the string into two or more positive number s
added condition the numbers should form an AP with common difference of 1
split numbers cannot be rearranged
split numbers should not have any leading zeroes
we must check all the possibly ways of splitting
then check which are feasible
if more than one then choose the one which starts with smaller number
lets say n digit number
1 digit numbers only
1 digit numbers and some 2 digits number s
all 2 digits
QUEENS
AIM
COUNT THE NUMBER OF SQUARES THE QUEEN CAN ATTACK ON OR REACH TO