In this post, we will solve HackerRank Modify The Sequence Problem Solution.
You are given a sequence of integers a1,a2,a3…..an. You are free to replace any integer with any other positive integer. How many integers must be replaced to make the resulting sequence strictly increasing?
Input Format
The first line of the test case contains an integer N – the number of entries in the sequence.
The next line contains N space separated integers where the ith integer is ai.
Output Format
Output the minimal number of integers that should be replaced to make the sequence strictly increasing.
Sample Input #00
3
4 10 20
Sample Output #00
0
Sample Input #01
6
1 7 10 2 20 22
Sample Output #01
1
Sample Input #02
5
1 2 2 3 4
Sample Output #02
3
Explanation
In the first sample input, we need not replace anything, hence the output is 0.
In the second sample input, we can replace 2 with any integer between 11 and 19 to make the sequence strictly increasing, hence the output is 1.
In the third sample input, we can obtain 1, 2, 3, 4, 5 by changing the last three elements of the sequence.
Modify The Sequence C Solution
#include <stdio.h>
#include <string.h>
const int inf = 2000000000;
int a[1000005];
int longest;
void find(int x) {
int left = 1, right = longest;
while (left <= right) {
int mid = (left + right) >> 1;
if (a[mid] <= x) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
a[++right] = x;
if (right > longest) {
longest = right;
}
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i <= n; ++i) {
a[i] = inf;
}
longest = 0;
for (int i = 1; i <= n; ++i) {
int x;
scanf("%d", &x);
if ((x -= i) >= 0) {
find(x);
}
}
printf("%d\n", n - longest);
return 0;
}Modify The Sequence C++ Solution
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize(3)
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC target("sse3","sse2","sse")
//#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
//#pragma GCC target("f16c")
//#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
//#pragma GCC diagnostic error "-fwhole-program"
//#pragma GCC diagnostic error "-fcse-skip-blocks"
//#pragma GCC diagnostic error "-funsafe-loop-optimizations"
//#pragma GCC diagnostic error "-std=c++14"
#include "bits/stdc++.h"
#include "ext/pb_ds/tree_policy.hpp"
#include "ext/pb_ds/assoc_container.hpp"
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x, l, u) for(ll x = l;x<u;x++)
#define RREP(x, l, u) for(ll x = l;x>=u;x--)
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define mst(x, a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define lowbit(x) ((x)&(-(x)))
#define lson (ind<<1)
#define rson (ind<<1|1)
#define se second
#define fi first
#define sz(x) ((int)x.size())
#define EX0 exit(0);
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace __gnu_pbds; //required
using namespace std;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef vector<ll> VLL;
typedef vector<int> VI;
const int block_size = 320;
typedef complex<ll> point;
const ll mod = 1e9 + 7;
const ll inf = 1e9 + 7;
const ld eps = 1e-9;
const db PI = atan(1) * 4;
template<typename T>
inline int sign(const T &a) {
if (a < 0)return -1;
if (a > 0)return 1;
return 0;
}
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string) s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template<typename A, typename B>
string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template<typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) { res += ", "; }
first = false;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifndef ONLINE_JUDGE
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define dbg(...) {}
#endif
template<typename T, typename S>
inline bool upmin(T &a, const S &b) { return a > b ? a = b, 1 : 0; }
template<typename T, typename S>
inline bool upmax(T &a, const S &b) { return a < b ? a = b, 1 : 0; }
template<typename T>
inline void in(T &x) {
x = 0;
T f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
}
ll twop(int x) { return 1LL << x; }
template<typename T>
T MOD(T a, T m) {
a %= m;
if (a < 0)a += m;
return a;
}
template<typename T>
T inverse(T a, T m) {
a = MOD(a, m);
if (a <= 1)return a;
return MOD((1 - inverse(m, a) * m) / a, m);
}
template<typename A, typename B>
inline void in(A &x, B &y) {
in(x);
in(y);
}
template<typename A, typename B, typename C>
inline void in(A &x, B &y, C &z) {
in(x);
in(y);
in(z);
}
template<typename A, typename B, typename C, typename D>
inline void in(A &x, B &y, C &z, D &d) {
in(x);
in(y);
in(z);
in(d);
}
template<typename T>
T sqr(T x) { return x * x; }
ll gcd(ll a, ll b) {
while (b != 0) {
a %= b;
swap(a, b);
}
return abs(a);
}
ll fast(ll a, ll b, ll mod) {
ll ans = 1;
while (b) {
if (b & 1) {
b--;
ans = ans * a % mod;
}
else {
a = a * a % mod;
b /= 2;
}
}
return ans % mod;
}
namespace SOLVE {
void main() {
int n;in(n);
VI v(n);
REP(i,0,n)in(v[i]);
REP(i,0,n)v[i]-=i+1;
VI lis;
dbg(v);
for(auto i:v){
if(i<0)continue;
auto ptr = UB(all(lis),i);
if(ptr == lis.end())lis.PB(i);
else *ptr = i;
}
cout<<n-sz(lis)<<endl;
}
}
signed main() {
#ifndef ONLINE_JUDGE
#endif
int t = 1;
// in(t);
for (int i = 1; i <= t; i++) {
// cout<<"Case #"<<i<<":";
SOLVE::main();
}
// clock_t st = clock();
// while(clock() - st < 3.0 * CLOCKS_PER_SEC){
//
// }
return 0;
}Modify The Sequence C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
static void Main(String[] args) {
int N = Convert.ToInt32(Console.ReadLine());
List<long> line = Console.ReadLine().Split(' ').Select(t => Convert.ToInt64(t)).ToList(); //
N = line.Count;
for (int j = 0; j < line.Count; j++)
{
line[j] = line[j] - j;
}
List<long> LIS = new List<long>();
LIS.Add(line[0]);
for (int j = 1; j < line.Count; j++)
{
if (line[j] <= 0)
continue;
else if (line[j] < LIS[0])
{
LIS[0] = line[j];
}
else if (line[j] >= LIS[LIS.Count - 1])
{
LIS.Add(line[j]);
}
else
{
// find proper place too add number
int mid = LIS.Count / 2 ;
int start = 0;
int end = LIS.Count - 1;
while (line[j] >= LIS[start] && line[j] < LIS[end])
{
mid = start + ((end - start + 1) / 2);
if (LIS[mid - 1] <= line[j] && LIS[mid] > line[j])
{
end = mid;
break;
}
else if (line[j] < LIS[mid])
{
end = mid;
}
else
{
start = mid;
}
}
LIS[end] = line[j];
}
}
Console.WriteLine(line.Count - LIS.Count);
}
}Modify The Sequence Java Solution
import java.io.*;
import java.util.*;
public class Solution {
static int ceilIndex(int tailTable[], int r, int key) {
int l = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (tailTable[mid] <= key) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return l;
}
static int modifySequence(int arr[]) {
int[] tailTable = new int[arr.length];
int len = 0;
for (int i = 0; i < arr.length; i++) {
int val = arr[i];
if (val < 0) {
continue;
}
int l = ceilIndex(tailTable, len - 1, arr[i]);
if (len <= l) {
tailTable[len++] = val;
}
else {
tailTable[l] = val;
}
}
return arr.length - len;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer st = new StringTokenizer(br.readLine());
int arrCount = Integer.parseInt(st.nextToken());
int[] arr = new int[arrCount];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < arrCount; i++) {
int item = Integer.parseInt(st.nextToken());
arr[i] = item - (i+1);
}
int result = modifySequence(arr);
bw.write(String.valueOf(result));
bw.newLine();
bw.close();
br.close();
}
}Modify The Sequence JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', function(inputStdin) {
inputString += inputStdin;
});
process.stdin.on('end', function() {
inputString = inputString.split('\n');
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the 'modifySequence' function below.
*
* The function is expected to return an INTEGER.
* The function accepts INTEGER_ARRAY arr as parameter.
*/
function modifySequence(arr) {
let len = arr.length;
let tail = Array(len + 1).fill(0);
let l = 0;
let j = 0;
let lower = 0;
let upper = 0;
for (let i in arr) {
i = Number.parseInt(i);
if (arr[i] < i + 1) continue;
if (arr[i] >= arr[tail[l]] + i - tail[l]) {
j = l + 1;
} else {
lower = 1;
upper = l;
while (lower <= upper) {
let mid = Number.parseInt((lower + upper) / 2);
if (arr[tail[mid]] <= arr[i] - i + tail[mid]) {
lower = mid + 1;
} else {
upper = mid - 1;
}
}
j = lower;
}
tail[j] = i;
if (j > l) l = j;
}
return arr.length - l;
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const arrCount = parseInt(readLine().trim(), 10);
const arr = readLine().replace(/\s+$/g, '').split(' ').map(arrTemp => parseInt(arrTemp, 10));
const result = modifySequence(arr);
ws.write(result + '\n');
ws.end();
}Modify The Sequence Python Solution
N_0 = int(input())
number_string = input().split()
def longest_propper_subsequence(arr):
N = len(arr)
M = (N+1)*[0]
L = 0
for i in range(0,N):
if arr[i] < i + 1:
continue
if arr[i] >= arr[M[L]] + i - M[L] :
j = L+1
else:
lower = 1
upper = L
while lower <= upper:
mid = int((upper+lower)/2)
if arr[M[mid]] <= arr[i] - i + M[mid]:
lower = mid + 1
else:
upper = mid - 1
j = lower
M[j] = i
if j > L:
L = j
return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0-L)
