Here is my solution in java, C++, GO HackerRank Lena Sort Problem Solution

Here is the solution of Lena Sort Click Here

Here is problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-lena-sort-problem-solution.html

1. Here in the first step we have to genarate the max and min array define that as less and more.
2. to do that we have to first initialize the mins and max array's 1 number index as 1. and generate loop till 3 to 100001 as our maximum element's ranage is 100000.
3. to generate the element's of max we have to make addition of the previous index's element and the index of that element. to generate the mins element we have to add previous element's index and the middle element of 0 index to the (i-1)th element and the difference from the previous element's index to the middle

in the code this will be:

 mins[2]=1;
        max[2]=1;
        
        for(int i=3;i<100001;i++){
            
            mins[i]=i-1+mins[ (i-1)/2 ]+mins[ (i-1)-(i-1)/2 ];
            
            max[i]=max[i-1]+i-1;
            
        }

now our mins and max are as like as :

1. max: 0 0 1 3 6 10 15 21........
2. min: 0 0 1 2 4 6 8 10......

next step we have to check the max array's (len)th index element or the len length's max array's last element is greater than c or not and mins last element from 0 to len range. if not then we have to print -1, as this have no solution.in the code part as like as this:

if( max[len]<c || mins[len]>c ){
                
                System.out.println("-1");
                continue;
                
            }

in the main function of the solution first we have to check the best cases, that the len is 0 or not and the len is 1 or not, means this is last element or not.if this is last element then we add the last element's offset(which is initially set as 1) in the answer.in the code part:

if( len==0 ){
         
         return ans;
         
     }
     
     if( len==1 ){
         
        ans.append(offset).append(" ");
         
         return ans;
         
     }

inital pivot'e index we set as 0.and set the c as the c-=(len-1) the difference of the c and the last index of the len, th lenngth array.

now have to detect the final pivot's position.that the mins first index's to half part of the range till the middle and last index's to the middle, that the mins element is greater than c or not and max element is less than c or not to find the last position of the valid condition. in the code part as like as this is:

int pivot=0;
     
     c-=len-1;
     
     while( mins[pivot]+mins[len-pivot-1]>c || max[ pivot ]+max[len-pivot-1]<c ){
         
         pivot++;
         
     }

now we have to check the last element of max and min to comapre with the constraint c-newC. in every state the newC value will be increasing.And the initial newC value is first valid element of the mins which value is less than c.in the code part:

long newC=mins[pivot];
     
     while( mins[len-pivot-1]>c-newC || max[len-pivot-1]<c-newC ){
         
         newC++;
         
     }

then we add the summation of the pivot and the initial element of the list which we set as the offset:

ans.append( (pivot+offset)+" " );

now we make a recurssive call

1. solve(pivot,newC,offset,max,mins,ans);
2. solve(len-pivot-1,c-newC,offset+pivot+1,max,mins,ans);

in the in the first call we set the len as the pivot or first valid element's of th min or max array and set the c as the difference of initial c and the 2nd half's first non valid element's number.

and finally return the ans.

to explain more clarly if we see an example for len=5 and c or constraint as 6

first we have to set the initial max and min element array, this is:

1. max: 0 0 1 3 6 10 15 21........
2. min: 0 0 1 2 4 6 8 10......

initial len: 5 initial c: 6 initial offset: 1 ans:

and in the first state c value is: 2( 6-( 5-1 )=6-4=2 )

set the initial pivot as 0 and,

now have to visit from 0 to range 4

1. min[0]+min[len-0-1]=0+4=4, and 4>2, so pivot value is 1
2. now min[1]+min[5-1-1]=0+2 =2, and 2>2 so check the next condition for max
3. max[1]+max[5-1-1]=0+3=3 and 3<2 that is false

so in the first call our pivot value is 1

now have to detect the newC value, initially that is mins[1]=0

now mins[5-1-1]=2>2-0=2 it is false and also false for max, as max[5-1-1]=3<2 this is also false.

now our newC value is also 0.and append the summation of the pivot and offset in the ans, now the ans is: 2

now make's an another recurssive call, here the initial len: 1(pivot) initial c: 0(newC) initial offset: 1(offset) ans: 2(ans )

here the len is 1 so add 1 in the ans and return it.

now it make's the another recurrsive call here initial len: 3(len-pivot-1=5-1-1=3) initial c: 2(c-newC=2-0=2) initial offset: 3 ans: 2 1

now run till 0 to 2 the same process we done at the previous.

now pivot is: 1 and offset 3

as the same reason for the mins[len-pivot-1] and max[len-pivot-1]

newC=0

and ans: 2 1 4

and now pivot is: 1 and offset: 3, and make an another recurssive call:

now initial len: 1 initial c: 0 initial offset: 3 ans: 2 1 4

as len is 1: add 3 in the ans and return it:

now ans: 2 1 4 3

and make another recurssive call now:

initial len: 1 initial c: 0 initial offset: 5 ans: 2 1 4 3

as len==1 so answer will be 2 1 4 3 5

our final ans is: 2 1 4 3 5

this is the link of full solution:

https://github.com/AmitRoy3370/HackerRank/blob/master/Lena%20Sort

sorry for bad english and make the explanation so long

element's

5.

how can we generate the array any idea please