• Post Reply Bookmark Topic Watch Topic
  • New Topic

How to Reduce Runtime in Java Code ?  RSS feed

 
Kislaya Pant
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How to Reduce Runtime of Java Code ?
Hi,
I have copied the complete question from a site.
Question is as :-


Akash and Akhil are playing a game. They have balls numbered from to . Akhil asks Akash to reverse the position of the balls, i.e., to change the order from say, 0,1,2,3 to 3,2,1,0. He further asks Akash to reverse the position of the balls times, each time starting from one position further to the right, till he reaches the last ball. So, Akash has to reverse the positions of the ball starting from position, then from position, then from position and so on. At the end of the game, Akhil will ask Akash the final position of any ball numbered . Akash will win the game, if he can answer. Help Akash.


Input Format
The first line contains an integer , i.e., the number of the test cases.
The next lines will contain two integers and .

Output Format
Print the final index in array.

Constraints
1<=T<=50
1<=N<=100000
0<=K<N



Sample Input :-

2
3 1
5 2

Output :-

2
4

Explanation :-
For first test case, The rotation will be like this:
0 1 2 -> 2 1 0 -> 2 0 1 -> 2 0 1
So, Index of 1 will be 2.


My quote has running time of 4 sec


I am getting Time Limit Exceeded....
Please Help me out ..

Here is my code :-

Whenever I run this code in that site, it says "Time Limit Exceeded". Is there is a way to reduce the performance time and get rid of that problem? Please help to reduce the time limit..
 
Campbell Ritchie
Marshal
Posts: 56527
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Does the question mean whether A wins or whether A wins?

Please always tell us where such questions come from.
Why have you got keyboard input inside the loop? That should guarantee the loop times out because keyboard input takes so long. If you are worried about the duration of the keyboard input, enter all the numbers as command‑line arguments.
 
Campbell Ritchie
Marshal
Posts: 56527
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And weelcome to the Ranch
 
Knute Snortum
Sheriff
Posts: 4274
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Looks like it comes from https://www.hackerrank.com.
 
Knute Snortum
Sheriff
Posts: 4274
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why have you got keyboard input inside the loop? That should guarantee the loop times out because keyboard input takes so long. If you are worried about the duration of the keyboard input, enter all the numbers as command‑line arguments.

That's just the way the site is setup. It sends all the input at one time so you don't wait on the keyboard.
 
Kislaya Pant
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Does the question mean whether A wins or whether A wins?

Please always tell us where such questions come from.
Why have you got keyboard input inside the loop? That should guarantee the loop times out because keyboard input takes so long. If you are worried about the duration of the keyboard input, enter all the numbers as command‑line arguments.


No, The question does not mean whether A wins or whether B wins...It is clear from Test cases..
Okay the question is from :-
Here is Question.
But as per question I have to get keyboard input inside the loop...
 
fred rosenberger
lowercase baba
Bartender
Posts: 12563
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't see where the pages says ANYTHING about a keyboard, let alone getting keyboard input inside your loop.
 
Knute Snortum
Sheriff
Posts: 4274
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is just the way this site gets the input values. Click here to see it explicitly.
 
Campbell Ritchie
Marshal
Posts: 56527
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Now I have had a look at the simple example they have given, I can see that lines 8 and 9 are red herrings. The input has to be ready before the program starts, so input time is ignored.

Back to the drawing board!
 
Carey Brown
Saloon Keeper
Posts: 3310
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There is some tightening up of the code that you could do but that would only shave a few nano seconds off. For a radical improvement in speed you need a radical approach to the problem. There is a distinct pattern to the final array after you've done all the swapping. So, instead of doing all the initializing of the array and physically swapping the elements you could just compute the index.
 
Carey Brown
Saloon Keeper
Posts: 3310
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The pattern becomes much more obvious with a greater number of samples. Here's the code that I used:


Here's my output:
 
Kislaya Pant
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:There is some tightening up of the code that you could do but that would only shave a few nano seconds off. For a radical improvement in speed you need a radical approach to the problem. There is a distinct pattern to the final array after you've done all the swapping. So, instead of doing all the initializing of the array and physically swapping the elements you could just compute the index.





Thanks For Suggestions
I am trying to figure out some pattern in question...
 
Kislaya Pant
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kislaya Pant wrote:
Carey Brown wrote:There is some tightening up of the code that you could do but that would only shave a few nano seconds off. For a radical improvement in speed you need a radical approach to the problem. There is a distinct pattern to the final array after you've done all the swapping. So, instead of doing all the initializing of the array and physically swapping the elements you could just compute the index.





Thanks For Suggestions
I am trying to figure out some pattern in question...



Please Tell Me......
I have tried several patterns..But They are not working .....
Please Can you figure out working pattern...
Waiting For Your Reply...
 
Tim Holloway
Saloon Keeper
Posts: 18789
74
Android Eclipse IDE Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
"Time limit exceeded" often means that actually it's in an infinite loop.



I hate those stupid sites. I spend half my time trying to figure out what they want, half of it reviewing algorithms. Then there's no time to code, especially at my typing speed. Last one I did didn't support cut-and-paste and I dont' code linearly, so I had to keep retyping large chunks of stuff as I refined the design.

I can deliver a complete industrial-scale data-validating, error-handling, message-passing, ORM-persisting system with high performance and NSA-level security, but I don't deliver stuff in 15 minutes or less. It takes me longer than that just to get the typos out of "Hello, World!".
 
fred rosenberger
lowercase baba
Bartender
Posts: 12563
49
Chrome Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kislaya Pant wrote:
Please Tell Me......
I have tried several patterns..But They are not working .....
Please Can you figure out working pattern...
Waiting For Your Reply...

What do you mean by you have "tried" several patterns? Are you trying them randomly? I'd advise you to work out - on paper - what the result would be for an array of length 3, then of length 4, then of length 5...maybe up to 7 or 8.

Then write them all together, each right above/below the next. Analyse them carefully. Look closely at the elements. If you still don't see something, then post those here and we'll help you some more.
 
Knute Snortum
Sheriff
Posts: 4274
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please EaseUp (← that's a link) a little. We are all trying to steer you in the right direction without giving you complete answers. That's how it's done here.

How about posting something you've tried or telling us about it?
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!