HackerRank Modify The Sequence problem solution

In this HackerRank Modify The Sequence problem solution we have 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?

Problem solution in Python.

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)

Problem solution in Java.

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();
  }
}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int N;
    scanf("%d", &N);
    vector<int> V(N), PD;
    PD.reserve(N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &V[i]);
        V[i] -= i;
    }
    for (int i = 0; i < N; i++) if (V[i] > 0) {
        int pos = upper_bound(PD.begin(), PD.end(), V[i]) - PD.begin();
        if (pos == PD.size()) PD.push_back(V[i]);
        else PD[pos] = V[i];
    }
    printf("%dn", N - PD.size());
    return 0;
}

Problem solution in C.

#include<stdio.h>
#include<string.h>
int a[1000005], 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, i;
    scanf("%d", &n);
    for( i = 0 ; i <= n ; ++i )
    {
        a[i] = 2000000000;
    }
    longest = 0;
    for( i = 1 ; i <= n ; ++i )
    {      
        int x;  
        scanf("%d", &x);
        if( ( x -= i ) >= 0 )
        {
            find(x);
        }
    }
    printf("%dn", n - longest);
    return 0;
}