### Ticker

6/recent/ticker-posts

# Python Programming

Problem 1 : Addition without arithmetic operator

while(b!=0):

carry=a&b

a=a^b

b=carry>>1

return a

def main():

a=int(input("enter first number"))

b=int(input("enter second number"))

main()

Problem 2 : Given a string, find the length of the longest substring in it with no more than K distinct characters.

Code (python)

def longest_substring_with_k_distinct(str, k):

window_start = 0

max_length = 0

char_frequency = {}

# in the following loop we'll try to extend the range [window_start, window_end]

for window_end in range(len(str)):

right_char = str[window_end]

if right_char not in char_frequency:

char_frequency[right_char] = 0

char_frequency[right_char] += 1

# shrink the sliding window, until we are left with 'k' distinct characters in the char_frequency

while len(char_frequency) > k:

left_char = str[window_start]

char_frequency[left_char] -= 1

if char_frequency[left_char] == 0:

del char_frequency[left_char]

window_start += 1  # shrink the window

# remember the maximum length so far

max_length = max(max_length, window_end-window_start + 1)

return max_length

def main():

print("Length of the longest substring: " + str(longest_substring_with_k_distinct("araaci", 2)))

print("Length of the longest substring: " + str(longest_substring_with_k_distinct("araaci", 1)))

print("Length of the longest substring: " + str(longest_substring_with_k_distinct("cbbebi", 3)))

main()

### Problem 3

Given an array of characters where each character represents a fruit tree, you are given two baskets and your goal is to put maximum number of fruits in each basket. The only restriction is that each basket can have only one type of fruit. (Concept)

Code #

Here is what our algorithm will look like,

window_start = 0

max_length = 0

fruit_frequency = {}

# try to extend the range [window_start, window_end]

for window_end in range(len(fruits)):

right_fruit = fruits[window_end]

if right_fruit not in fruit_frequency:

fruit_frequency[right_fruit] = 0

fruit_frequency[right_fruit] += 1

# shrink the sliding window, until we are left with '2' fruits in the fruit frequency dictionary

while len(fruit_frequency) > 2:

left_fruit = fruits[window_start]

fruit_frequency[left_fruit] -= 1

if fruit_frequency[left_fruit] == 0:

del fruit_frequency[left_fruit]

window_start += 1  # shrink the window

max_length = max(max_length, window_end-window_start + 1)

return max_length

def main():

print("Maximum number of fruits: " + str(fruits_into_baskets(['A', 'B', 'C', 'A', 'C'])))

print("Maximum number of fruits: " + str(fruits_into_baskets(['A', 'B', 'C', 'B', 'B', 'C'])))

main()

Problem 4

# Cyclic Sort (easy)

### Problem Statement

We are given an array containing ‘n’ objects. Each object, when created, was assigned a unique number from 1 to ‘n’ based on their creation sequence. This means that the object with sequence number ‘3’ was created just before the object with sequence number ‘4’. (Concept)

Python Code

def cyclic_sort(nums):

i = 0

while i < len(nums):

j = nums[i] - 1

if nums[i] != nums[j]:

nums[i], nums[j] = nums[j], nums[i]  # swap

else:

i += 1

return nums

def main():

print(cyclic_sort([3, 1, 5, 4, 2]))

print(cyclic_sort([2, 6, 4, 3, 1, 5]))

print(cyclic_sort([1, 5, 6, 4, 3, 2]))

main()