HackerRank Lena Sort Problem Solution

HackerRank Lena Sort Problem Solution

Posted on By Yashwant Parihar No Comments on HackerRank Lena Sort Problem Solution

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 Tags:, , ,

Related Posts

HackerRank Compare the Triplets Problem Solution HackerRank Compare the Triplets Problem Solution c
HackerRank Tara's Beautiful Permutations Problem Solution HackerRank Tara’s Beautiful Permutations Solution c
HackerRank Number Line Jumps Problem Solution HackerRank Number Line Jumps Problem Solution c
HackerRank Cards Permutation Problem Solution HackerRank Cards Permutation Problem Solution c
HackerRank Hacker Country Problem Solution HackerRank Hacker Country Problem Solution c
HackerRank Oil Well Problem Solution HackerRank Oil Well Problem Solution c

Leave a Reply

Your email address will not be published. Required fields are marked *