Table of Contents
Insertion Sort Advanced Analysis – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Insertion Sort Advanced Analysis HackerRank Solution
#include<iostream>
#include<string.h>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<list>
#include<stack>
#include<sstream>
#include<fstream>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cassert>
#define CLRM(x) memset(x,-1,sizeof(x))
#define CLR(x) memset(x,0,sizeof(x))
#define ALL(x) x.begin(),x.end()
#define GI(x) scanf("%d", &x);
#define FORN(i, n) for(int i = 0; i < n; i++)
#define FOR(i, start, end) for(int i = start; i < end; i++)
#define PB push_back
#define MP make_pair
#define VI vector<int>
#define VVI vector<vector<int> >
#define PII pair<int,int>
#define SZ(x) (int)x.size()
#define LL long long
#define MIN(a,b) (a)<(b)?(a):(b)
#define MAX(a,b) (a)>(b)?(a):(b)
#define LMAX 1000000000000000000LL
#define IMAX 1000000000
using namespace std;
#define MAXN 110000
int N;
int d[MAXN];
LL mergesort(int low, int high)
{
if(low >= high)
return 0;
int mid = (low+high)/2;
LL ret = 0;
ret = mergesort(low, mid) + mergesort(mid+1, high);
vector<int> v;
int i, j, k;
i = low; j = mid + 1;
while(i <= mid && j <= high)
{
if(d[i] > d[j])
{
v.PB(d[j]);
ret+=(LL)(mid-i+1);
j++;
}
else
{
v.PB(d[i]);
i++;
}
}
while(i <= mid)
{
v.PB(d[i]);
i++;
}
while(j <= high)
{
v.PB(d[j]);
j++;
}
for(i = 0; i < v.size(); i++)
{
d[i + low] = v[i];
}
return ret;
}
LL solve()
{
LL ret = mergesort(0, N-1);
return ret;
}
int main()
{
int tes;
GI(tes);
while(tes--)
{
int i;
GI(N);
FORN(i, N)
{
GI(d[i]);
}
LL ans = solve();
printf("%lld\n", ans);
}
return 0;
}
Java Insertion Sort Advanced Analysis HackerRank Solution
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.StringTokenizer;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
* @author lwc626
*/
public class Solution {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
MyInputReader in = new MyInputReader(inputStream);
MyOutputWriter out = new MyOutputWriter(outputStream);
Insertion_Sort solver = new Insertion_Sort();
int testCount = Integer.parseInt(in.next());
for (int i = 1; i <= testCount; i++)
solver.solve(i, in, out);
out.close();
}
}
class Insertion_Sort {
public void solve(int testNumber, MyInputReader in, MyOutputWriter out) {
int n = in.nextInt() ;
int[] A = new int[ n ] ;
IOUtils.readIntArrays(in, A);
out.printLine( reverse_pair(out,A, 0 , n-1) );
}
private long reverse_pair(MyOutputWriter out,int[] a , int l , int r) {
if( l == r ) return 0 ;
int m = ( l + r ) / 2 ;
long ret = reverse_pair( out,a , l , m ) ;
ret += reverse_pair( out,a , m+1 , r ) ;
//out.printLine( l , r );
//IOUtils.printIntArrays(out , a );
int [] tmp = new int[ r - l + 1];
int nl = l , nr = m+1 , n = 0;
while ( nl <= m && nr <= r ){
if( a[nl] <= a[nr] ){
tmp[n++] = a[nl++] ;
ret += nr - m -1 ;
}else{
tmp[n++] = a[nr++] ;
}
}
while ( nl <= m ) { tmp[ n ++ ] = a[ nl ++ ]; ret += nr-m-1;}
while ( nr <= r ) tmp[ n ++ ] = a[ nr ++ ];
System.arraycopy( tmp , 0 , a , l, n );
return ret;
}
}
class MyInputReader {
private BufferedReader reader;
private StringTokenizer tokenizer;
public MyInputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream));
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
class MyOutputWriter {
private final PrintWriter writer;
public MyOutputWriter(OutputStream outputStream) {
writer = new PrintWriter(outputStream);
}
public MyOutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void print(Object...objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0)
writer.print(' ');
writer.print(objects[i]);
}
}
public void printLine(Object...objects) {
print(objects);
writer.println();
}
public void close() {
writer.close();
}
}
class IOUtils {
public static void readIntArrays( MyInputReader in,int[]... arrays ){
for(int i = 0 ; i < arrays[0].length; i++ )
for( int j = 0 ; j < arrays.length ; j ++ )
arrays[j][i] = in.nextInt();
}
}
Python 3 Insertion Sort Advanced Analysis HackerRank Solution
#!/bin/python3
import math
import os
import random
import re
import sys
from bisect import bisect_left as lower_bound
# Complete the insertionSort function below.
def insertionSort(arr):
n=len(arr)
def BIT_update(BITTree,n,i,v):
while i<=n:
BITTree[i]+=v
i+=i&(-i)
def BIT_getSum(BITTree,i):
s=0
while i>0:
s+=BITTree[i]
i-=i&(-i)
return s
def convert(arr, n):
temp = [0]*(n)
for i in range(n):
temp[i] = arr[i]
temp = sorted(temp)
for i in range(n):
arr[i] = lower_bound(temp, arr[i]) + 1
def getInvCount(arr, n):
invcount = 0
convert(arr,n)
BIT = [0] * (n + 1)
for i in range(n - 1, -1, -1):
invcount += BIT_getSum(BIT, arr[i] - 1)
BIT_update(BIT, n, arr[i], 1)
return invcount
return getInvCount(arr,n)
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
t = int(input())
for t_itr in range(t):
n = int(input())
arr = list(map(int, input().rstrip().split()))
result = insertionSort(arr)
fptr.write(str(result) + '\n')
fptr.close()
Python 2 Insertion Sort Advanced Analysis HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
T = int(raw_input())
for t in range(0, T):
N = int(raw_input())
a = [0] * 1000001
res = 0
line = raw_input()
for item in line.split(' '):
x = int(item)
while x > 0:
res += a[x]
x -= x & -x
x = int(item)
while x <= 1000000:
a[x] = a[x] + 1
x += x & -x
res = N * (N - 1) / 2 - res
print res
C Insertion Sort Advanced Analysis HackerRank Solution
#include<stdio.h>
int d[100001],n;
int temp[100001];
long long ans;
void merge(int L1,int U1,int L2,int U2)
{
int p,q,j,i;
p=L1;q=L2;i=0;
while(p<=U1 && q<=U2)
{
if(d[p]<=d[q])
{
temp[i++]=d[p++];
}
else
{
ans=(long long)ans+U1-p+1;
temp[i++]=d[q++];
}
}
for(;p<=U1;)
{
temp[i++]=d[p++];
}
for(;q<=U2;)
{
temp[i++]=d[q++];
}
for(q=L1,i=0;q<=U1;q++,i++)
{
d[q]=temp[i];
}
for(q=L2,j=i;q<=U2;q++,j++)
{
d[q]=temp[j];
}
}
void process(int LB, int UB)
{
int m;
if(UB>LB)
{
m=(LB+UB)/2;
process(LB,m);
process(m+1,UB);
merge(LB,m,m+1,UB);
}
}
int getnum()
{
int tmp=0;
char ch;
while(1)
{
ch=getchar();
if(ch>='0'&&ch<='9')
{
tmp*=10;
tmp+=ch-48;
}
else break;
}
return tmp;
}
int main()
{
int t,i,j;
//scanf("%d",&t);
t=getnum();
while(t--)
{
//scanf("%d",&n);
n=getnum();
for(i=1;i<=n;i++)
d[i]=getnum();
ans=0;
process(1,n);
printf("%lld\n",ans);
}
return 0;
}
Comments 1