# HackerRank Lena Sort problem solution

In this HackerRank Lena Sort problem solution, You must solve Q queries where each query i consists of some len and c. For each query, construct an array of distinct elements in the inclusive range between 1 and 10 to power 9 that will be sorted by lena_sort in exactly c comparisons, then print each respective element of the unsorted array as a single line of len space-separated integers; if no such array exists, print -1 instead.

## Problem solution in Python.

```#!/bin/python3

import math
import os
import random
import re
import sys

sys.setrecursionlimit(100000)

def get_min_arr(length, start):
if length == 0:
return []
if length == 1:
return [0]

memo = [(0, length)]
while len(memo) < length:
new_memo = []
for m in memo:
if isinstance(m, int):
new_memo.append(m)
else:
s, l = m
middle = s + (l - 1) // 2
new_memo.append(middle)
s_less, l_less = s, (l - 1) // 2
s_more, l_more = middle + 1, l // 2
if l_less == 1:
new_memo.append(s_less)
elif l_less > 1:
new_memo.append((s_less, l_less))
if l_more == 1:
new_memo.append(s_more)
elif l_more > 1:
new_memo.append((s_more, l_more))
memo = new_memo

return [start + m for m in memo]

def rec(length, comparisons, first):

if length == 0:
return []
if length == 1:
return [first]

prefix_length = 0
remaining = length
while True:
tmp = remaining - 1
if comparisons - tmp >= smallest[tmp]:
prefix_length += 1
comparisons -= tmp
remaining = tmp
else:
break
prefix = [first + p for p in range(prefix_length)]
if prefix_length == length:
return prefix

length -= prefix_length
comparisons -= remaining - 1
first = first + prefix_length

for less in range((length + 1) // 2):
more = length - 1 - less
max_more, min_more = more * (more - 1) // 2, smallest[more]
max_less, min_less = less * (less - 1) // 2, smallest[less]
lower = max(min_less, comparisons - max_more)
upper = min(max_less, comparisons - min_more)
if upper >= lower:
break

pivot = first + less

if lower == comparisons - max_more:
comparisons_less = lower
A = rec(less, comparisons_less, first)
B = list(range(pivot + 1, pivot + 1 + more))
elif upper == comparisons - min_more:
comparisons_less = upper
A = rec(less, comparisons_less, first)
B = get_min_arr(more, pivot + 1)
else:
comparisons_less = upper
comparisons_more = comparisons - comparisons_less
A = list(range(first, first + less))
B = rec(more, comparisons_more, pivot + 1)

return prefix + [pivot] + A + B

if __name__ == '__main__':

sys.setrecursionlimit(100000)
smallest = [0, 0]
q = int(input())
for q_itr in range(q):
l, c = list(map(int, input().split()))

for length in range(len(smallest), l + 1):
if length % 2 == 0:
s = smallest[length // 2 - 1] + smallest[length // 2]
else:
s = 2 * smallest[length // 2]
smallest.append(s + length - 1)

largest = l * (l - 1) // 2
if c < smallest[l] or c > largest:
result = '-1'
else:
arr = rec(l, c, 1)
result = ' '.join(map(str, arr))

print(result)
```

{"mode":"full","isActive":false}

## Problem solution in Java.

```import java.io.*;
import java.util.*;

public class lena_sort extends PrintWriter {
lena_sort() { super(System.out); }
Scanner sc = new Scanner(System.in);
public static void main(String[] \$) {
lena_sort o = new lena_sort(); o.main(); o.flush();
}

static final int N = 100000;
int[] kk = new int[N + 1];
int[] aa = new int[N];
void init() {
for (int n = 2; n <= N; n++) {
int p = (n - 1) / 2, q = n - 1 - p;
kk[n] = kk[p] + kk[q] + n - 1;
}
}
void solve(int l, int r, int a, int c) {
int n = r - l;
if (n == 0)
return;
c -= n - 1;
int lower = -1, upper = (n - 1) / 2, p, q;
while (upper - lower > 1) {
p = lower + upper >> 1;
q = n - 1 - p;
if (kk[p] + kk[q] <= c)
upper = p;
else
lower = p;
}
p = upper;
q = n - 1 - p;
aa[l] = a + p;
int cp = (int) Math.max(kk[p], c - (long) q * (q - 1) / 2), cq = c - cp;
solve(l + 1, l + 1 + p, a, cp);
solve(l + 1 + p, r, a + p + 1, cq);
}
void main() {
init();
int q = sc.nextInt();
while (q-- > 0) {
int n = sc.nextInt();
int c = sc.nextInt();
if (c < kk[n] || (long) n * (n - 1) / 2 < c) {
println(-1);
continue;
}
solve(0, n, 1, c);
for (int i = 0; i < n; i++)
print(aa[i] + " ");
println();
}
}
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

vector<long long int> mx;
vector<long long int> mn;

long long int mincomp(int n);
long long int maxcomp(int n);

long long int mnc (int n) {
//cout<<"mnc "<<n<<endl;
if (n==1||n==0) return 0;
if (n==2) return 1;
int one, two;
one=(n-1)/2;
two=n-1-one;
return (long long int)n-1+mincomp(one)+mincomp(two);
}
long long int mxc (int n) {
//cout<<"mxc "<<n<<endl;
if (n==1||n==0) return 0;
if (n==2) return 1;
return (long long int)n-1+maxcomp(n-1);
}
long long int mincomp(int n) {
//cout<<"mincomp "<<n<<endl;
if (mn.size()<=n) {
for (int i=mn.size();i<=n;i++) mn.push_back(mnc(i));
}
return mn[n];
}
long long int maxcomp(int n) {
//cout<<"maxcomp "<<n<<" "<<mx.size()<<endl;
if (mx.size()<=n) {
//cout<<"maxcomp expanding mx"<<endl;
for (int i=mx.size();i<=n;i++) mx.push_back(mxc(i));
}
//cout<<"maxcomp returning "<<endl;//<<mn[n]<<endl;
return mx[n];
}

void reverselena(int l,int c,int add, int *arr) {
if (c==maxcomp(l)) {
//cout<<"rl max"<<endl;
return;
}
if (c==mincomp(l)) {
//cout<<"rl min"<<endl;
return;
}
int newc=c-(l-1);
//cout<<"rl here"<<endl;
for (int i=0;i<l;i++){
//cout<<"add up to "<<newc<<" "<<maxcomp(l-i-1)<<" + "<<mincomp(i)<<" or "<<maxcomp(i)<<endl;
if (newc>=mincomp(i)+maxcomp(l-1-i)&&newc<=maxcomp(i)+maxcomp(l-1-i)){
//if (one[0]==0) break;
//if (two[0]==0) break;
return;
}
}
for (int i=0;i<l;i++){
if (newc>=mincomp(i)+mincomp(l-1-i)&&newc<=maxcomp(i)+mincomp(l-1-i)){
//if (one[0]==0) break;
//if (two[0]==0) break;
return;
}
}

return;
}

int main()
{
int q;
cin >> q;
cin.ignore(numeric_limits<streamsize>::max(), '\n');

for (int q_itr = 0; q_itr < q; q_itr++) {
string lc_temp;
getline(cin, lc_temp);

vector<string> lc = split_string(lc_temp);

int l = stoi(lc[0]);

int c = stoi(lc[1]);

long long int maxcomparisons=maxcomp(l);
long long int mincomparisons=mincomp(l);
//cout<<mincomparisons<<" "<<maxcomparisons<<endl;
if (c>maxcomparisons||c<mincomparisons) cout<<-1<<endl;
else {
//cout<<"here 1"<<endl;
//cout<<"here 2"<<endl;
else {
cout<<endl;
}
}

}

return 0;
}

vector<string> split_string(string input_string) {
string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
return x == y and x == ' ';
});

input_string.erase(new_end, input_string.end());

while (input_string[input_string.length() - 1] == ' ') {
input_string.pop_back();
}

vector<string> splits;
char delimiter = ' ';

size_t i = 0;
size_t pos = input_string.find(delimiter);

while (pos != string::npos) {
splits.push_back(input_string.substr(i, pos - i));

i = pos + 1;
pos = input_string.find(delimiter, i);
}

splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

return splits;
}
```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_L 100000

long *g, *h;

void init() {
g = malloc((MAX_L+1) * sizeof(long));
h = malloc((MAX_L+1) * sizeof(long));

g[0] = 0; h[0] = 0;
for (int i=1; i<MAX_L+1; i++) {
int l = (i - 1)/2, r = i - 1 - l;
g[i] = i - 1 + g[l] + g[r];
h[i] = h[i-1] + i - 1;
}
}

int search(int n, int c) {
int l = 1, r = (n+1)/2;
while (l+1<r) {
int m = (l+r) / 2;
if (g[m-1] + g[n-m] + n - 1 > c) {
l = m;
continue;
}
if (h[m-1] + h[n-m] + n - 1 < c) {
r = m;
continue;
}
return m;
}
if (g[l-1] + g[n-l] + n - 1 <= c && c <= h[l-1] + h[n-l] + n - 1) return l;
if (g[r-1] + g[n-r] + n - 1 <= c && c <= h[r-1] + h[n-r] + n - 1) return r;
return -1;
}

int pointer;
void fill(int* arr, int n, int c, int offset) {
if (n == 0) return;
int m = search(n, c);
if (m == -1) {
return;
}
arr[pointer++] = m + offset;
int c1, c2;
if (g[m-1] + h[n-m] + n - 1 < c) {
c2 = h[n-m];
c1 = c - (n - 1) - c2;
} else {
c1 = g[m-1];
c2 = c - (n - 1) - c1;
}
fill(arr, m-1, c1, offset);
fill(arr, n-m, c2, m + offset);
}

int main()
{
init();
int q; scanf("%d", &q);
for (int q_itr = 0; q_itr < q; q_itr++) {
int l, c; scanf("%d%d", &l, &c);
if (search(l, c) == -1) {
printf("-1\n");
} else {
int *arr = malloc(l * sizeof(int));
pointer = 0;
fill(arr, l, c, 0);
for (int i=0; i<l-1; i++) printf("%d ", arr[i]);
printf("%d\n", arr[l-1]);
}
}
return 0;
}
```

{"mode":"full","isActive":false}