By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,640 Members | 2,355 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,640 IT Pros & Developers. It's quick & easy.

Longest sub array in rotating array

P: 1
Guys is there any way to find the longest subarray of 1's in log(n) time.


1- 110011111000 then the output is 5 from pos 5 to 10

2- 1110011101 the output here is 3 but after rotation 1 the array becomes

111100111 and the output is now 4.

3 - 001111 the output here is 4 from pos 3 to 6 but after rotation it becomes 3 from pos 4 to 6

Note: i found the longest subarray length in O(n) before rotation ... how can i improve the solution after rotation if i have the past results..
Nov 11 '18 #1
Share this Question
Share on Google+
1 Reply

Expert Mod 10K+
P: 12,366
This is a weird question. Is this homework?

You can still do this in O(n). Just need a few extra variables. One for the length of the starting block. And one for the ending block that updates for each found block until you reach the end. Then you just need to check the last character to see if you need to subtract one from the end and add one to the start.
Nov 13 '18 #2

Post your reply

Sign in to post your reply or Sign up for a free account.