HackerRank Lena Sort Problem Solution

HackerRank Lena Sort Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank Lena Sort Problem Solution. Lena developed a sorting algorithm described by the following pseudocode:

lena_sort(array nums) {
    if (nums.size <= 1) {
        return nums;
    }
    pivot = nums[0];
    array less;
    array more;
    for (i = 1; i < nums.size; ++i) {
    	// Comparison
        if (nums[i] < pivot) {
            less.append(nums[i]);
        }
        else {
            more.append(nums[i]);
        }
    }
    sorted_less = lena_sort(less);
    sorted_more = lena_sort(more);
    ans = sorted_less + pivot + sorted_more;
    
    return ans;
}

We consider a comparison to be any time some nums[i] is compared with pivot.
You must solve a queries where each query & consists of some len, and c. For each query. construct an array of len, distinct elements in the inclusive range between 1 and 10° that will be sorted by lena_sort in exactly e; 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.
Input Format
The first line contains a single integer denoting q (the number of queries). Each line of the q subsequent lines contains two space-separated integers describing the respective values of len, (the length of the array) and c; (the number of comparisons) for query i.

Output Format

Print the answer to each query on a new line. For each query i, print lan[i] space-separated integers describing each respective element in an unsorted array that Lena’s algorithm will sort in exactly  comparisons; if no such array exists, print -1 instead.

Sample Input 0

2
5 6
5 100

Sample Output 0

4 2 1 3 5
-1

Explanation 0
We perform the following g = 2 queries:

  1. One array with len = 5 elements is [4, 2, 1, 3, 5]. The sequence of sorting operations looks like this:
  • Run lena_sort on [4, 2, 1, 3, 5]. Compare pivot = 4 with 2. 1. 3, and 5 for a total of 4 comparisons. We’re then left with less = [2, 1, 3] and more = [5]; we only need to continue sorting less, as more is sorted with respect to itself because it only contains one element.
  • Run lena_sort on less = [2, 1, 3]. Compare pivot = 2 with 1 and 3 for a total of 2 comparisons. We’re then left with less = [1] and more = [3], so we stop sorting. We sorted [4, 2, 1, 3, 5] in 4+2=6 comparisons and c = 6, so we print 4 2 1 3 5 on a new line.
  1. It’s not possible to construct an array with len = 5 elements that lena_sort will sort in exactly c = 100 comparisons, so we print -1 on a new line.

Sample Input 1

3
1 0
4 6
3 2

Sample Output 1

1
4 3 2 1
2 1 3
HackerRank Lena Sort Problem Solution
HackerRank Lena Sort Problem Solution

Lena Sort C++ Solution

#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define Endl endl

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> using vv=vector<vector<T>>;
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
#define out(args...){vector<string> a_r_g_s=s_p_l_i_t(#args, ','); e_r_r(a_r_g_s.begin(), args); }
vector<string> s_p_l_i_t(const string& s, char c) { vector<string> v; stringstream ss(s); string x; while(getline(ss,x,c)) v.emplace_back(x); return move(v);}
void e_r_r(vector<string>::iterator it) {}
template<typename T, typename... Args> void e_r_r(vector<string>::iterator it, T a, Args... args){ if(*it==" 1"||*it=="1") cerr<<endl; else cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << ", "; e_r_r(++it, args...);}
const ll MOD=1e9+7;

ll mn[112345],mx[112345];

vector<int> dfs(int n,int m){
  if(n==0) return {};
  if(n==1) return {1};
  m-=n-1;
  //out(n,m,1);
  rep(i,n){
    if(mn[i] + mn[n-1-i] <= m && m <= mx[i] + mx[n-1-i]){
      int t;
      if(mn[n-1-i] <= m-mn[i] && m-mn[i] <= mx[n-1-i]){
	t=mn[i];
      }else{
	t=m-mx[n-1-i];
      }
      vector<int> l=dfs(i,t);
      vector<int> r=dfs(n-1-i,m-t);
      if(l.size()!=i || r.size()!=n-1-i) for(;;);
      int p=i+1;
      //out(i,t,p,l,r,1);
      vector<int> re{p};
      for(int x:l) re.pb(x);
      for(int x:r) re.pb(x+p);
      return re;
    }
  }
  //out(mn[n],mx[n],1);
  //cout<<"!"<<endl;
  for(;;);
  return vector<int>(n,-1);
}

int main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  mn[0]=mn[1]=mx[0]=mx[1]=0;
  reps(i,2,102345){
    mn[i]=mn[i/2]+mn[(i-1)/2]+i-1;
    mx[i]=mx[i-1]+i-1;
  }
  //rep(i,10) cout<<pii(mn[i],mx[i]);cout<<Endl;
  int T;
  cin>>T;
  while(T--){
    int n,m;
    cin>>n>>m;
    if(m<mn[n] || mx[n]<m){
      cout<<-1<<endl;
      continue;
    }
    int mm=m,nn=n;
    vector<int> re;
    while(nn){
      if(mm-(nn-1)<mn[nn-1]) break;
      re.pb(nn);
      mm-=nn-1; --nn;
    }
    auto tmp=dfs(nn,mm);
    for(int x:tmp) re.pb(x);
    rep(i,n){
      if(i) cout<<" ";
      cout<<re[i];
    }
    cout<<endl;
    if(re.size()!=n) for(;;);
  }
  return 0;
}

Lena Sort Go Solution

package main
import ("bufio"; "fmt"; "io"; "os")
import "sort"

func min(l int) int {
	if l == 0 {
		return 0
	}
	sum := 0
	n := 1
	k := 1
	for 2 * n + 1 <= l {
		sum += (n + 1) * k
		k++
		n = 2 * n + 1
	}
	return sum + (l - n) * k
}

func show(l, c, start int) {
	Assert(c <= l * (l - 1) / 2)
	if c == l * (l - 1) / 2 {
		for i := 0; i < l; i++ {
			fmt.Print(" ", start + i)
		}
		return
	}
	k := sort.Search((l - 1) / 2, func (n int) bool {
		a := n + 1
		b := l - 1 - a
		return c - (l - 1) - min(a) > b * (b - 1) / 2
	})
	fmt.Print(" ", start + k)
	mink := min(k)
	show(k, mink, start)
	show(l - 1 - k, c - (l - 1) - mink, start + k + 1)
}

func main() {
	Q := ScanInt(1, 1e5)
	for q := 0; q < Q; q++ {
		NewLine()
		L := ScanInt(1, 1e5)
		C := ScanInt(0, 1e9)
		if C > L * (L - 1) / 2 || C < min(L) {
			fmt.Println(-1)
			continue
		}
		show(L, C, 1)
		fmt.Println()
	}
}

// Boilerplate

func Assert(condition bool, items... interface{}) {
	if !condition {
		panic("assertion failed: " + fmt.Sprint(items...))
	}
}

func Log(items... interface{}) {
	fmt.Println(items...)
}

var Input = bufio.NewReader(os.Stdin)

func ReadByte() byte {
	b, e := Input.ReadByte()
	if e != nil {
		panic(e)
	}
	return b
}

func MaybeReadByte() (byte, bool) {
	b, e := Input.ReadByte()
	if e != nil {
		if e == io.EOF {
			return 0, false
		}
		panic(e)
	}
	return b, true
}

func UnreadByte() {
	e := Input.UnreadByte()
	if e != nil {
		panic(e)
	}
}

func NewLine() {
	for {
		b := ReadByte()
		switch b {
		case ' ', '\t', '\r':
			// keep looking
		case '\n':
			return
		default:
			panic(fmt.Sprintf("expecting newline, but found character <%c>", b))
		}
	}
}

func ScanInt(low, high int) int {
	return int(ScanInt64(int64(low), int64(high)))
}

func ScanUint(low, high uint) uint {
	return uint(ScanUint64(uint64(low), uint64(high)))
}

func ScanInt64(low, high int64) int64 {
	Assert(low <= high)
	for {
		b := ReadByte()
		switch b {
		case ' ', '\t', '\r':
			// keep looking
		case '\n':
			panic(fmt.Sprintf(
				"unexpected newline; expecting range %d..%d", low, high))
		case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
			if high < 0 {
				panic(fmt.Sprintf(
					"found <%c> but expecting range %d..%d", b, low, high))
			}
			lw := low
			if lw < 0 {
				lw = 0
			}
			UnreadByte()
			x, e := _scanu64(uint64(lw), uint64(high))
			if e != "" {
				panic(fmt.Sprintf("%s %d..%d", e, low, high))
			}
			return int64(x)
		case '-':
			if low > 0 {
				panic(fmt.Sprintf(
					"found minus sign but expecting range %d..%d", low, high))
			}
			h := high
			if h > 0 {
				h = 0
			}
			x, e := _scanu64(uint64(-h), uint64(-low))
			if e != "" {
				panic(fmt.Sprintf( "-%s %d..%d", e, low, high))
			}
			return -int64(x)
		default:
			panic(fmt.Sprintf(
				"unexpected character <%c>; expecting range %d..%d", b, low, high))
		}
	}
}

func ScanUint64(low, high uint64) uint64 {
	Assert(low <= high)
	for {
		b := ReadByte()
		switch b {
		case ' ', '\t', '\r':
			// keep looking
		case '\n':
			panic(fmt.Sprintf(
				"unexpected newline; expecting range %d..%d", low, high))
		case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
			UnreadByte()
			x, e := _scanu64(low, high)
			if e != "" {
				panic(fmt.Sprintf("%s %d..%d", e, low, high))
			}
			return x
		default:
			panic(fmt.Sprintf(
				"unexpected character <%c>; expecting range %d..%d", b, low, high))
		}
	}
}

func _scanu64(low, high uint64) (result uint64, err string) {
	x := uint64(0)
	buildnumber: for {
		b, ok := MaybeReadByte()
		if !ok {
			break buildnumber
		}
		switch b {
		case ' ', '\t', '\r':
			break buildnumber
		case '\n':
			UnreadByte()
			break buildnumber
		case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
			d := uint64(b - '0')
			if (high - d) / 10 < x {
				return x, fmt.Sprintf("%d%c... not in range", x, b)
			}
			x = x * 10 + d
		default:
			return x, fmt.Sprintf("%d%c found; expecting range", x, b)
		}
	}
	if x < low || x > high {
		return x, fmt.Sprintf("%d not in range", x)
	}
	return x, ""
}

func ScanBytes(short, long int) []byte {
	Assert(1 <= short && short <= long)
	var b byte
	buf := make([]byte, long)
	skipws: for {
		b = ReadByte()
		switch b {
		case ' ', '\t', '\r':
			// keep looking
		case '\n':
			panic(fmt.Sprintf("unexpected newline; expecting string"))
		default:
			break skipws
		}
	}
	buf[0] = b
	length := 1
	buildstring: for {
		var ok bool
		b, ok = MaybeReadByte()
		if !ok {
			break buildstring
		}
		switch b {
		case ' ', '\t', '\r':
			break buildstring
		case '\n':
			UnreadByte()
			break buildstring
		default:
			if length >= long {
				panic(fmt.Sprintf("string length not in range %d..%d", short, long))
			}
			buf[length] = b
			length++
		}
	}
	if length < short {
		panic(fmt.Sprintf("string length not in range %d..%d", short, long))
	}
	return buf[:length]
}

func ScanString(short, long int) string {
	return string(ScanBytes(short, long))
}

Lena Sort Java Solution

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        long[] mins = new long[100001];
        long[] maxes = new long[100001];
        mins[2] = 1;
        maxes[2] = 1;
        for (int i = 3; i <= 100000; i++) {
            mins[i] = i-1+mins[(i-1)/2]+mins[(i-1)-(i-1)/2];
            maxes[i] = maxes[i-1]+i-1;
        }
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();
        for(int a0 = 0; a0 < q; a0++){
            int len = in.nextInt();
            int c = in.nextInt();
            if (maxes[len]<c||mins[len]>c) {
                System.out.println(-1);
                continue;
            }
            System.out.println(portion(len, c, 1, mins, maxes, new StringBuilder()));
        }
    }
    
    public static StringBuilder portion(int len, long c, int offset, long[] mins, long[] maxes, StringBuilder ans) {
        if (len==0) {
            return ans;
        }
        if (len==1) {
            ans.append(offset+" ");
            return ans;
        }
        int pivot = 0;
        c -= len-1;
        while (mins[pivot]+mins[len-pivot-1]>c||maxes[pivot]+maxes[len-pivot-1]<c)
            pivot++;
        long newc = mins[pivot];
        while (mins[len-pivot-1]>c-newc||maxes[len-pivot-1]<c-newc)
            newc++;
        ans.append((pivot+offset)+" ");
        portion(pivot, newc, offset, mins, maxes, ans);
        portion(len-pivot-1, c-newc, offset+pivot+1, mins, maxes, ans);
        return ans;
    }
}
C++ Go HackerRank Solutions java