HackerRank Almost Sorted problem solution

In this HackerRank Almost Sorted problem solution, given an array of integers, determine whether the array can be sorted in ascending order using only one of the following operations once.

1. Swap two elements.
2. Reverse one sub-segment.

Determine whether one, both or neither of the operations will complete the task. Output is as follows.

1. If the array is already sorted, output yes on the first line. You do not need to output anything else.
2. If you can sort this array using one single operation (from the two permitted operations), then output yes on the first line and then:
   • If elements can only be swapped, d[l] and d[r], output swap l r in the second line. l and r are the indices of the elements to be swapped, assuming that the array is indexed from 1 to n.
   • If elements can only be reversed, for the segment d[l…..r], output reverse l r in the second line. l and r are the indices of the first and last elements of the subarray to be reversed, assuming that the array is indexed from 1 to n. Here, d[l…r] represents the subarray that begins at index l and ends at index r, both inclusive.

If an array can be sorted both ways, by using either swap or reverse, choose swap 3. If the array cannot be sorted either way, output no on the first line.

HackerRank Almost sorted 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)

Almost Sorted 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);
});