423,850 Members | 1,661 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 423,850 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.

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..
4 Weeks Ago #1
Share this Question
Share on Google+
1 Reply


Rabbit
Expert Mod 10K+
P: 12,279
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.
4 Weeks Ago #2

Post your reply

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