tag:blogger.com,1999:blog-14074542.post5806724495538973755..comments2023-09-15T14:12:23.832+05:30Comments on Gebo - Madhur Tanwani's blog: Find if number occurs exactly n/2 times in an arrayAnonymoushttp://www.blogger.com/profile/05009478527695401190noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-14074542.post-67229472155187600712009-08-28T13:24:42.884+05:302009-08-28T13:24:42.884+05:30@Bhavin
Solution will work for characters & di...@Bhavin<br />Solution will work for characters & digits - not for numbers / strings etc..Anonymoushttps://www.blogger.com/profile/05009478527695401190noreply@blogger.comtag:blogger.com,1999:blog-14074542.post-13679351831080647262009-08-15T23:12:41.431+05:302009-08-15T23:12:41.431+05:30I've another soln, I havnt thought it through ...I've another soln, I havnt thought it through but I think it meets req.<br /><br />1. Create an array of 10, its each index stores the count for number of times no from 0-9 appears.<br />2. Create a similar array to store character occurrences.<br />3. Now traverse the list zero to end and keep updating the counter corresponding to each character.<br />4. In the end you should have count for all, you can just traverse the list again to check if any of it is n/2.Bhavin Shahhttps://www.blogger.com/profile/16257384637763382553noreply@blogger.comtag:blogger.com,1999:blog-14074542.post-75300325885102106432009-08-12T00:14:16.281+05:302009-08-12T00:14:16.281+05:30Another interesting solution could also be (got th...Another interesting solution could also be (got this from an interview discussion) : <br /><br />1.> Make the input data circular (array / list - data storage / representation)<br /><br />2.> Do a adjacency check - two a's together<br /><br />3.> Do a distance = 1/2 check - two separated by one/two charAnonymoushttps://www.blogger.com/profile/05009478527695401190noreply@blogger.comtag:blogger.com,1999:blog-14074542.post-1600519238856792972009-08-05T19:41:47.608+05:302009-08-05T19:41:47.608+05:30We need 3 pointers :
ptr1 -> first element
ptr...We need 3 pointers : <br />ptr1 -> first element<br />ptr2 -> second element<br />ptr3 -> third element<br /><br />while(end of array is reached) {<br /> if(any one of ptr1/2/3's value is equal) {<br /> then return the match<br /> } <br /> else<br /> {<br /> ptr1<-ptr2<-ptr3<-next element<br /> }<br />}<br /><br />Time complexity : O(n)<br />Space : O(1)Anonymoushttps://www.blogger.com/profile/05009478527695401190noreply@blogger.com