CODEWITHSUNDEEP
javaarrays
Vaibhav Misra
Vaibhav Misra

Reputation: 11

Terminated due to timeout in hacker rank for large inputs

This code shows "Terminated due to timeout" error on some large inputs on Hackerrank but works fine for the rest of the cases. Help me improve this code please.

John Watson performs an operation called a right circular rotation on an array of integers, . After performing one right circular rotation operation, the array is transformed from to .

Watson performs this operation times. To test Sherlock's ability to identify the current element at a particular position in the rotated array, Watson asks queries, where each query consists of a single integer, , for which you must print the element at index in the rotated array (i.e., the value of ).

Input Format

The first line contains space-separated integers, , , and , respectively. The second line contains space-separated integers, where each integer describes array element (where ). Each of the subsequent lines contains a single integer denoting .

Constraints

Output Format

For each query, print the value of the element at index of the rotated array on a new line.

Sample Input

3 2 3 1 2 3 0 1 2 Sample Output

2 3 1

MY CODE

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

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. */
        int n,k,q,temp=0,c=0;
        Scanner sc=new Scanner(System.in);
        try{
        n=sc.nextInt();
        k=sc.nextInt();
        q=sc.nextInt();
        int[] arr=new int[n];
        int qrr[]=new int[q];
        for(int i=0;i<n;i++)
            arr[i]=sc.nextInt();
        while(sc.hasNext()){
            qrr[c++]=sc.nextInt();
        }
        for(int j=1;j<=k;j++){
        temp=arr[n-1];
        for(int i=n-2;i>=0;i--){
            arr[i+1]=arr[i];
        }
        arr[0]=temp;
        }
        for(int i=0;i<q;i++){
            System.out.println(arr[qrr[i]]);
        }
    }
    catch(Exception ae){
        System.out.println(ae.getMessage());
    }
}
}

Upvotes: 0

Views: 1804

Answers (1)

Abhikalp Unakal
Abhikalp Unakal

Reputation: 41

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

public class Solution {

    public static int m,n,k,q,i=0,c=0;
    public static int errorflag = 0;
    public static int array[];
    public static int rotated[];
    public static Scanner in = new Scanner(System.in);

    public static int[] getArray(int n){
        array = new int[n];
        for(i=0;i<n;i++){
            array[i] = in.nextInt();
        }       
        return(array);
    }

    public static int[] rotate(int[] original){
        int[] rotated = new int[original.length];
        for(i=0;i<original.length;i++){
            rotated[(i+k)%original.length] = original[i];
        }
        return(rotated);
    }

The above function works with a worst case O(n) complexity. Basically what you're doing is assigning a new index for the elements such that they are right rotated or incremented by an amount k and the overflow is taken care of by the modulus operation.

    public static void main(String[] args) {
        n = in.nextInt();
        k = in.nextInt();
        q = in.nextInt();
        array = getArray(n);

        int m[] = new int[q];
        for(i=0;i<m.length;i++){
            m[i] = in.nextInt();
        }
        rotated = rotate(array);
        for(i=0;i<m.length;i++){
            System.out.println(rotated[m[i]]);
        }


    }
}

Upvotes: 1

Related Questions