Cloudster
BAN USERIf additional space is allowed,
Assume input array is arr[]
1) Build a hashmap H of all elements in arr[] and their count .. O(N).
2) keep i=0, j=keys().length (number of keys).
3) Sort the keys() in the map and loop through all keys.
4) arr[i] = key; i++
4) for j=1 to H[key]: arr[j]=key; j++
O(N) solution in Python
'''
Created on Aug 14, 2013
@author: maheedhar
'''
def largestsetofonesandzeroes(arr):
count_ones = count_zeroes = 0
for item in arr:
if item == 1:
count_ones += 1
else:
count_zeroes += 1
i = 0
j = len(arr) - 1
while i < j:
diff = count_ones - count_zeroes
if diff == 0:
break
elif diff > 0:
if arr[i] == 1:
i += 1
count_ones -= 1
elif arr[j] == 1:
j -= 1
count_ones -= 1
else:#Both ends have zero
i += 1
count_zeroes -= 1
elif arr[i] == 0:
i += 1
count_zeroes -= 1
elif arr[j] == 0:
j -= 1
count_zeroes -= 1
else:#Both ends have Ones
j -= 1
count_ones -= 1
return j - i + 1, arr[i:j + 1]
print largestsetofonesandzeroes([0, 0, 1, 0, 1, 0, 1, 0])
How about this?
You can prepare a Known list till the max range,
1-10 has 1 occurrence
10-100 has (1*10 + 9) 19
100-1000 has (19*10 + 99) 289
1000-10000 (289*10 + 999) 3889 and so on
n=43
#Will have a limitation of n upto 99999
known_range={1:0,10:1,100:19,1000:289,10000:3889}
base=1
numoftwos=0
while(n>1):
val=n%10
for i in range(0,val):
numoftwos += known_range[base]
if i==2:
numoftwos += base
base *= 10
n = n/10
print "n has %d of 2's"%numoftwos
def longest_2char_seq(str):
start_pos = end_pos = 0
charmap = {}
maxstr = ''
strlen = len(str)
while end_pos < strlen - 1:
while len(charmap) < 3 and end_pos < strlen:
if not charmap.get(str[end_pos]):
charmap[str[end_pos]] = 0
end_pos += 1
end_pos -= 1
if len(maxstr) < len(str[start_pos:end_pos ]):
maxstr = str[start_pos:end_pos]
charmap = {}
start_pos = end_pos - 1
while start_pos > 0 and str[start_pos] != str[end_pos - 1]:
start_pos -= 1
return maxstr
Repmerrillagreerm, Android Engineer at Abs india pvt. ltd.
I am patient, compassionate, and caring when treating and counseling patients in practice, making them feel like they’re in ...
Repjanistbennett, Blockchain Developer at AMD
I am JanisBennett working as a journalist, having years of experience in my career. I have covered various stories.Great ...
Repfriedcopeland, AOL tech support at 247quickbookshelp
My name is Frieda . I am a loan officer for a small real estate lender in Wahpeton, Texas. I specialize ...
Not needed. That why I have a pointer at j to add duplicate sorted numbers.
- Cloudster August 17, 2013