Table of Contents
Modify The Sequence – 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++ replace HackerRank Solution
#include <iostream>
#include <ctime>
#include <fstream>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <utility>
#include <cctype>
#include <list>
using namespace std;
#define FORALL(i,a,b) for(int i=(a);i<=(b);++i)
#define FOR(i,n) for(int i=0;i<(n);++i)
#define FORB(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef long double ld;
typedef complex<ld> vec;
typedef pair<int,int> pii;
typedef map<int,int> mii;
#define pb push_back
#define mp make_pair
#define INF 2000000001
#define MAXN 1000100
int A[MAXN];
int dp[MAXN];
int main() {
int N;
cin >> N;
A[0] = 1;
FORALL(i,1,N) scanf("%d",A+i);
FORALL(i,1,N) A[i] -= i;
FORALL(i,0,N) dp[i] = INF;
//FORALL(i,1,N) cout << A[i] << " "; cout << endl;
dp[0] = 0;
FORALL(i,1,N) {
if (A[i] < 0) continue;
int idx = upper_bound(dp,dp+N,A[i]) - dp - 1;
//cout << i << " " << A[i] << " " << idx << endl;
assert(idx >= 0);
dp[idx+1] = A[i];
}
/*
FOR(i,N) cout << A[i] << endl;
*/
int ans = 0;
FORALL(i,0,N) if (dp[i] < INF) ans = max(ans,i);
/*
FORALL(i,0,N) {
cout << i << " " << dp[i] << endl;
}*/
cout << N-ans << endl;
}
Java rep HackerRank Solution
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Set;
import java.util.Stack;
import java.util.TreeMap;
import java.util.TreeSet;
public class Solution {
static final int mod = 1000000007;
final Random random = new Random(System.currentTimeMillis());
final IOFast io = new IOFast();
static int gcd(int n, int r) { return r == 0 ? n : gcd(r, n % r); }
public void run() throws IOException {
// int T = io.nextInt();
int T = 1;
while(T-- > 0) {
int n = io.nextInt();
int[] a = io.nextIntArray(n);
int[] b = new int[n];
int bn = 0;
for(int i = 0; i < a.length; i++) {
if(a[i] - i > 0) {
b[bn++] = a[i] - i;
}
}
io.out.println(n - LIS2(Arrays.copyOf(b, bn)));
}
}
static int LIS2(final int[] ys) {
final int n = ys.length;
final int[] res = new int[n];
Arrays.fill(res, Integer.MAX_VALUE);
for (int i = 0; i < n; i++) {
res[upperBound(res, ys[i])] = ys[i];
}
return lowerBound(res, Integer.MAX_VALUE);
}
static int upperBound(final int[] xs, final int x) {
int low = 0, high = xs.length;
while (low < high) {
final int mid = (low + high) / 2;
final int cmp = xs[mid] < x ? -1 : xs[mid] == x ? 0 : 1;
if (cmp > 0) high = mid;
else low = mid + 1;
}
return low;
}
private static int lowerBound(final int[] xs, final int x)
{
int low = 0, high = xs.length;
while (low < high) {
final int mid = (low + high) / 2;
final int cmp = xs[mid] < x ? -1 : xs[mid] == x ? 0 : 1;
if (cmp >= 0) high = mid;
else low = mid + 1;
}
return low;
}
void main() throws IOException {
// IOFast.setFileIO("rle-size.in", "rle-size.out");
try {
run();
}
catch (EndOfFileRuntimeException e) { }
io.out.flush();
}
public static void main(String[] args) throws IOException {
new Solution().main();
}
static class EndOfFileRuntimeException extends RuntimeException {
private static final long serialVersionUID = -8565341110209207657L; }
static
public class IOFast {
private BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
private PrintWriter out = new PrintWriter(System.out);
void setFileIO(String ins, String outs) throws IOException {
// in = new BufferedReader(new FileReader(ins));
out = new PrintWriter(new FileWriter(outs));
}
// private static final int BUFFER_SIZE = 50 * 200000;
private static int pos, readLen;
private static final char[] buffer = new char[1024 * 8];
private static final char[] str = new char[500000*8*2];
private static boolean[] isDigit = new boolean[256];
private static boolean[] isSpace = new boolean[256];
private static boolean[] isLineSep = new boolean[256];
static {
for(int i = 0; i < 10; i++) { isDigit['0' + i] = true; }
isDigit['-'] = true;
isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true;
isLineSep['\r'] = isLineSep['\n'] = true;
}
public int read() throws IOException {
if(pos >= readLen) {
pos = 0;
readLen = in.read(buffer);
if(readLen <= 0) { throw new EndOfFileRuntimeException(); }
}
return buffer[pos++];
}
public int nextInt() throws IOException {
return Integer.parseInt(nextString());
}
public long nextLong() throws IOException {
return Long.parseLong(nextString());
}
public char nextChar() throws IOException {
while(true) {
final int c = read();
if(!isSpace[c]) { return (char)c; }
}
}
int reads(char[] cs, int len, boolean[] accept) throws IOException {
try {
while(true) {
final int c = read();
if(c < accept.length && accept[c]) { break; }
cs[len++] = (char)c;
}
}
catch(EndOfFileRuntimeException e) { ; }
return len;
}
public char[] nextLine() throws IOException {
int len = 0;
str[len++] = nextChar();
len = reads(str, len, isLineSep);
try {
if(str[len-1] == '\r') { len--; read(); }
}
catch(EndOfFileRuntimeException e) { ; }
return Arrays.copyOf(str, len);
}
public String nextString() throws IOException {
return new String(next());
}
public char[] next() throws IOException {
int len = 0;
str[len++] = nextChar();
len = reads(str, len, isSpace);
return Arrays.copyOf(str, len);
}
public double nextDouble() throws IOException {
return Double.parseDouble(nextString());
}
public long[] nextLongArray(final int n) throws IOException {
final long[] res = new long[n];
for(int i = 0; i < n; i++) {
res[i] = nextLong();
}
return res;
}
public int[] nextIntArray(final int n) throws IOException {
final int[] res = new int[n];
for(int i = 0; i < n; i++) {
res[i] = nextInt();
}
return res;
}
public int[][] nextIntArray2D(final int n, final int k) throws IOException {
final int[][] res = new int[n][];
for(int i = 0; i < n; i++) {
res[i] = nextIntArray(k);
}
return res;
}
public double[] nextDubleArray(final int n) throws IOException {
final double[] res = new double[n];
for(int i = 0; i < n; i++) {
res[i] = nextDouble();
}
return res;
}
}
}
Python 3 rep HackerRank Solution
import bisect
def parse(seq):
for i in range(len(seq)):
seq[i] -= i
def patience_sort(array):
piles = [array[0]]
for x in range(1, len(array)):
i = bisect.bisect_right(piles, array[x])
if i != len(piles):
piles[i] = array[x]
else:
piles.append(array[x])
return len(piles)
def main():
n = int(input())
array = [i for i in range(-99, 1)] + list(map(int, input().split()))
parse(array)
#print(array)
print(n - patience_sort(array) + 100)
if __name__ == '__main__':
main()
Python 2 rep HackerRank Solution
import bisect
n = int(raw_input())
a = [-99]*100
c = 100
for i in map(lambda x: int(x), raw_input().split()):
a.append(i-c)
c += 1
l = a[:1]
for i in a[1:]:
j = bisect.bisect(l,i)
if j != len(l): l[j] = i
else: l.append(i)
print(100+n-len(l))
C rep HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
int get_i(int*a,int num,int size);
int med(int*a,int size);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size);
int u[1000000],v[1000000],a[1000000];
int main(){
int n,x,i,ans=1,size=0,*aa;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&x);
if(x>i){
u[size]=i-x;
v[size]=i;
size++;
}
}
sort_a2(u,v,size);
aa=a+999999;
aa[0]=v[0];
for(i=1;i<size;i++){
x=get_i(aa,v[i],ans);
if(aa[x]==v[i])
continue;
if(!x){
aa--;
aa[0]=v[i];
ans++;
}
else
aa[x-1]=v[i];
}
printf("%d",n-ans);
return 0;
}
int get_i(int*a,int num,int size){
if(size==0)
return 0;
if(num>med(a,size))
return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1);
else
return get_i(a,num,(size-1)>>1);
}
int med(int*a,int size){
return a[(size-1)>>1];
}
void sort_a2(int*a,int*b,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*right_a,*right_b;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
}
sort_a2(left_a,left_b,m);
sort_a2(right_a,right_b,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
}
else if (left_a[i] == right_a[j]) {
if(left_b[i] >= right_b[j]){
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
}
else{
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
}
else if (left_a[i] < right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
}
return;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
