Python - Solutions

sum = 0
for i in range(1,100):
  sum += i
print sum

from functools import reduce
print reduce((lambda x, y: x+y), range(1,100))

Find a perfect number which is greater than the input integer.

1+2+3=6, 1+2+4+7+14=28. So, 6 and 28 are perfect number because the numbers are equal to the sum of divisors.

class MyTest:
    def __init__(self):
        pass

    def PerfectNumber(self,n):
        upper = n
        while True:
           sum = 1
           for i in range(2, upper):
               if upper % i == 0:
                   sum += i
               if sum == upper:
                   return upper
           upper += 1

if __name__== '__main__':
     t = MyTest()
     input = 27
     ans = t.PerfectNumber(input)
     print "Perfect number greater than ", input, " is ", ans

Output is:

Perfect number greater than  27  is  28

class MyTest:
    def __init__(self):
        pass

    def Palindrome(self, s):python_solutions.phppython_solutions.php
        left = 0;
        right = len(s)-1
        for i in range(0, right/2+1):
            if s[left] == ' ':
                left += 1
            if s[right] == ' ':
                right -= 1
            if s[left].lower() == s[right].lower():
                left += 1
                right -= 1
            if left >= right:
                return True
        return False
python_solutions.php
if __name__== '__main__':
     t = MyTest()
     input = ["I prefer pi", "I love python"]
     for s in input:
        ans = t.Palindrome(s)
        if ans == True:
            print s, " is a palindrome"
        else:
            print s, " is not a palindrome"python_solutions.phppython_solutions.php

Output is:

I prefer pi  is a palindrome
I love python  is not a palindrome

class MyTest:
    def __init__(self):
        pass

    def Permutations(self, input):
        length = len(input)
        level = 0
        out = []python_solutions.phppython_solutions.phppython_solutions.php
        used = []
        for i in range(length):
            used.append(False)
            out.append("")

        self.DoPermutations(input, out, length, used, level)

    def DoPermutations(self, input, out, length, used, level):
        if level == length:
            result = ''.join(out[:length])
            print result
            return
        for i in range(length):
            if used[i] == True:
                continue
            out[level] = input[i]
            used[i] = True
            self.DoPermutations(input, out, length, used, level+1)
            used[i] = False

if __name__ == '__main__':
    s = "1234"
    t = MyTest()python_solutions.php
    t.Permutations(s);

Output:

1234
1243
1324
1342python_solutions.phppython_solutions.phppython_solutions.phppython_solutions.php
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321

import math

def isPrime(n):
    count = 0;
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            count += 1
            if count > 1:
                return False
    return True
    
def PrintPrimes(upper):
    for i in range(2, upper+1):python_solutions.php
        if isPrime(i):
            print(i)
            
PrintPrimes(10)

def BinarySearch(a, low, high, n):
    if(low > high):python_solutions.php
        return -1
    mid = int((low+high)/2)
    if n < a[mid]:
        return BinarySearch(a, low, mid-1, n)
    elif n > a[mid]:
        return BinarySearch(a, mid+1, high, n)
    elif n == a[mid]:
        return mid 


arr = [1, 3, 5, 7, 9, 11, 13, 15]
ans = BinarySearch(arr, 0, len(arr)-1, 13)python_solutions.php
print("ans=", ans) // ans = 6

Q: Given a string, find the longest substring that contains at most 2 distinct characters.

Samples: 'ababcbcbaaabbdef', 'ababcbcbaaabbdefggggg'

def lsub(input):
     substring = []
     longest = 0
     for i in range(len(input)):
         c_set = set()
         for j in range(i,len(input)):
             c_set.add(input[j])
             if len(c_set) > 2:
                break
             if j+1-i == longest:
                substring.append(input[i:j+1])
             if j+1-i > longest:
                longest = j+1-i
                substring = []
                substring.append(input[i:j+1])
     return substring

print 'test:  ababcbcbaaabbdef =>'
s = 'ababcbcbaaabbdef'
print lsub(s)

print 'test:  ababcbcbaaabbdefggggg =>'
s = 'ababcbcbaaabbdefggggg'
print lsub(s)

Output:

test:  ababcbcbaaabbdef =>
['baaabb']
test:  ababcbcbaaabbdefggggg =>
['baaabb', 'fggggg']

How it works?

I'll take the first sample: 'ababcbcbaaabbdef'.

We'll loop through len(input) times, and each time we will deal with one character shorter string. For each loop we put all the characters we've seen until we see more than two unique characters.

We start to traverse entire string 'ababcbcbaaabbdef' as a first step, then as a next step, we start from the second character to the end of the string: 'babcbcbaaabbdef'. Then, we start to traverse from the 3rd character to the end of the string ('abcbcbaaabbdef'), and so on.

For each of the step, as we move on, we put each character into a set to filter out duplicate characters. For instance, the first case, when we're at the 5th character('c'), the set has ['a,'b'] and about to add 'c' to it. But because of the length of the set > 2, we stop there (break inner loop) and take the next case where we take a string from the 2nd character:'babcbcbaaabbdef'.

During the first step, we have 'abab' as an element of substring list: substring = ['abab'], longest=4.

When we are at the point of getting the answer ('baaabbdef' case), we manage to go at 'd' in 'baaabbdef', we'll have to stop there at 'd' because the set already has two unique characters ['b','a']. So, we get 'baaabb' in a substring list which will be returned from the function eventually.

For the second string sample, we have two substring with the same length: 'baaabb' and 'fggggg' will be in a substring list.