HackerRank Almost Sorted problem solution

YASH PAL,

In this HackerRank Almost Sorted problem, you have Given an array of integers, determine whether the array can be sorted in ascending order using either swap two elements or reverse one sub-segment.

HackerRank Almost Sorted problem solution

Problem solution in Python programming.

def getJumps(ar):
    jumps = []
    for i in range(len(ar)-1):
        if ar[i] > ar[i+1]:
            jumps.append(i)
    return jumps

def isSortedWithSwap(ar, i, j):
    ar[i], ar[j] = ar[j], ar[i]
    jumps = getJumps(ar)
    ar[i], ar[j] = ar[j], ar[i] # repair list
    return len(jumps) == 0

def isSortedWithReverse(ar, i, j):
    ar[i:j] = ar[j-1:i+1:-1]
    jumps = getJumps(ar)
    ar[i:j] = ar[j-1:i+1:-1] # repair list
    return len(jumps) == 0

def magic(ar):
    jumps = getJumps(ar)
    if len(jumps) == 0:
        print('yes')
    elif len(jumps) == 1:
        i = jumps[0]
        j = i+1
        while j+1 < len(ar) and ar[i+1] == ar[j+1]: #move point to last same element
            j+=1
        if isSortedWithSwap(ar, i, j):
            print('yes')
            print('swap', i+1, j+1)
        else:
            print('no')
    elif len(jumps) == 2:
        i = jumps[0]
        j = jumps[1] + 1
        if isSortedWithSwap(ar, i, j):
            print('yes')
            print('swap', i+1, j+1)
        else:
            print('no')
    else:
        i = jumps[0]
        j = jumps[-1] + 2
        if isSortedWithReverse(ar,i,j):
            print('yes')
            print('reverse', i+1, j)
        else:
            print('no')

n = int(input())
ar = list(map(int, input().split()))
magic(ar)

Problem solution in Java Programming.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        
        Scanner sc = new Scanner(System.in);
        int start = -1;int count = 0;int end = -1;
        int prev_i = -1;
        int size = sc.nextInt();
        int arr[] = new int [size];
        int i;
         for(int j = 0;j<size;j++){
            arr[j] = sc.nextInt();
         }
        if(findSwap(arr)==-1){
            findReverse(arr);
        }
    }
    
   static int findReverse(int [] arr){
      int start =-1;int end = -1;
       for(int i = 0;i<arr.length-1;i++){
          if(arr[i]>arr[i+1]){
               if(start==-1){
                      start = i;
                  }
                  else{
                      System.out.println("no");
                      return -1;
                  }
              while(arr[i]>arr[i+1]){                 
                  end = i+1;
                  i++;                  
              }
              if((start==0||arr[start-1]<arr[end])&&(end==arr.length-1||arr[start]<arr[end+1])){                
                      continue;
                  }
               else{
                   System.out.println("no");
                   return -1;
               }
              }
          }
        System.out.println("yes");
        System.out.println("reverse "+(start+1)+" "+(end+1));
       
       return 1;
      }
   
    
   static int findSwap(int [] arr){
        int count =0;int start = -1;int end =-1;
        for(int i = 0;i<arr.length-1;i++){
         
                   if(arr[i]>arr[i+1]){
                       count++;
                       if(count==1){
                           start = i;
                           end = i+1;
                       }
                       else{
                         if(count==2){
                             end=i+1;
                         }else{
                            return -1;
                         }
                       }
                   }                        
        }
       if((end!=arr.length-1)&&(arr[start]<arr[end+1]))
         {  
          System.out.println("yes");
          System.out.println("swap "+(start+1)+" "+(end+1));       
          return 1;
         }
       else{
           if((end==arr.length-1)&&(start==(end-1))){
                System.out.println("yes");
                System.out.println("swap "+(start+1)+" "+(end+1));       
                return 1;
           }
       }
        return -1;
    }
}


Problem solution in C++ programming.

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


int main() {
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    vector<int> B(A);
    sort(B.begin(), B.end());
    int start = -1, end = -1;
    int count = 0;
    for (int  i = 0; i < n; i++) {
        if (A[i] != B[i]) {
            count++;
            if (start == -1) {
                start = i;
            }
            end = i;            
        }
    }
    if (count == 2) {
        cout << "yes"<<endl;
        cout << "swap ";
        cout << start + 1<<" "<<end + 1<<endl;
        return 0;
    }
  
    for (int i = 0; i < count / 2; i++) {
        if (A[end - i] != B[start + i]) {
            cout << "no" <<endl;
            return 0;
        }
        
    }
    cout << "yes"<<endl;
    cout << "reverse "<<start + 1<<" "<<end + 1<<endl;
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    return 0;
}


Problem solution in C programming.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
    int *a, ar;
    int pos1 = -1, pos2 = -1, reverse = 0, swap = 0;
    int reverse_possible = 1;
    
    // get size of array and add elements to array
    scanf("%d", &ar);
    a = (int*)malloc(sizeof(int) * ar);
    for (int i = 0; i < ar; i++) {
        scanf("%d", a + i);
    }
    
    // work goes here
    for (int i = 0; i < ar; i++) {
        // we note that all numbers in the array are distinct
        if (i < ar - 1) {
            if (a[i] > a[i + 1]) {
            	if (swap || reverse) {
            		swap = reverse = 0;
            		break;
            	}
            	
                if (pos1 == -1) {
                    pos1 = i;
                    pos2 = i;
                } else if (reverse_possible && !reverse) {
                    pos2++;
                }
            } else if (pos2 != -1 && !swap && !reverse) {
                // potentially a reverse operation
                if (pos2 - pos1 >= 2) {
                    reverse = 1;
                    continue;
                // continue finding reverse
                } else {
                    pos2 = -1;
                    reverse_possible = 0;
                }
            }
        }
        
        // note that a[pos1] >= a[i]
        if (pos1 != -1 && a[pos1] > a[i] &&  
            ((i+1<ar && a[pos1] <= a[i+1]) || i+1>=ar) &&
            ((i-1>=0 && a[i-1] <= a[pos1]) || i-1<0) &&
            ((pos1+1<ar && a[i] <= a[pos1+1]) || pos1+1>=ar) &&
            ((pos1-1>=0 && a[pos1-1] <= a[i]) || pos1-1<0)) {
            if (swap || reverse) {
                swap = 0;
                reverse = 0; 
                break;
            }
            
            pos2 = i;
            swap = 1;
        }
    }
    
    //printf("%d %dn", swap, reverse);
    
    if (reverse) {
        printf("yesn");
        printf("reverse %d %d", pos1 + 1, pos2 + 2);
    } else if (swap) {
        printf("yesn");
        printf("swap %d %d", pos1 + 1, pos2 + 1);
    } else {
        printf("non");
    }
    
    return 0;
}


Problem solution in JavaScript programming.

function processData(input) {
    var lines = input.split("n");
    lines.shift();
    var array = lines[0].split(" ").map(function (v) {
        return parseInt(v);
    });
    solve(array);
}

function countDownMarks(array) {
    var downMarks = [];

    for (var i = 0; i < array.length - 1; i++) {
        if (array[i + 1] < array[i]) {
            downMarks.push(i);
        }
    }

    return downMarks;
}

function solve(array) {
    var downMarks = countDownMarks(array);
    var newArray, newDownMarks, start, end;

    // try swap
    if (downMarks.length == 1 ||
        downMarks.length == 2) {

        newArray = array.slice(0);

        start = downMarks.shift();
        end = (downMarks.length) ? downMarks.shift() + 1 : start + 1;

        swap(newArray, start, end);
        newDownMarks = countDownMarks(newArray);
        if (!newDownMarks.length) {
            outputResult("yes");
            output("swap", start + 1, end + 1);
            return;
        }
    }

    // try reverse
    if (downMarks.length > 2 &&
        downMarks.length == downMarks[downMarks.length - 1] - downMarks[0] + 1) {

        start = downMarks.shift();
        end = downMarks.pop() + 1;
        newArray = reverse(array, start, end);
        newDownMarks = countDownMarks(newArray);
        if (!newDownMarks.length) {
            outputResult("yes");
            output("reverse", start + 1, end + 1);
            return;
        }
    }

    outputResult("no");
}

function swap(array, idx1, idx2) {
    var tmp = array[idx1];
    array[idx1] = array[idx2];
    array[idx2] = tmp;
}

function reverse(array, idx1, idx2) {
    return array.slice(0, idx1).concat(array.slice(idx1, idx2 + 1).reverse()).concat(array.slice(idx2 + 1));
}

function output(op, start, end) {
    process.stdout.write([op, start, end].join(" "));
}

function outputResult(str) {
    process.stdout.write(str+"n");
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Algorithms coding problems solutions