468,146 Members | 1,431 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,146 developers. It's quick & easy.

Longest sub array in rotating array

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

example

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
1 2438
Rabbit
12,511 Expert Mod 8TB
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.

Similar topics

8 posts views Thread by Bob Bedford | last post: by
1 post views Thread by Bob Bedford | last post: by
20 posts views Thread by Geoff Cox | last post: by
8 posts views Thread by kings_oz | last post: by
10 posts views Thread by Steve | last post: by
2 posts views Thread by Kenneth Brody | last post: by
8 posts views Thread by =?big5?B?r0W84Q==?= | last post: by
4 posts views Thread by Bob Bedford | last post: by
30 posts views Thread by didacticone | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.