## Posts

Showing posts from March, 2016

### problem 293

This problem was some how easy.

Using DFS and Set

I could solve it.

### python disjoint set (union find)

# make setdef MakeSet(number): return node().set(number) # find rootdef find(x): if x.parent.number == x.number: return x else: return find(x.parent) # merge two setsdef union(x, y): xRoot = find(x) yRoot = find(y) xRoot.parent = yRoot class node(): def set(self, number): self.parent = self self.number = number return self# make setsets = list(map(lambda x:MakeSet(x), range(10))) for i in range(len(sets)): print(sets[i].number, sets[i].parent) # one set is 0-4 super root is 4for i in range(0, 4): union(sets[i], sets[i+1]) # the otehr set is 5~9 super root is 9for i in range(5, len(sets)-1): union(sets[i], sets[i+1]) # test for all nodes finding root nodefor i in range(len(sets)): print(i ," parent -> ", find(sets[i]).number)

### Problem 491

Examples: Is the number 2547039 divisible by 11? First find the difference between sum of its digits at odd and even places. (Sum of digits at odd places) - (Sum of digits at even places) = (9 + 0 + 4 + 2) - (3 + 7 + 5) = 15 - 15 = 0 The number is 0, so the number 2547039 is divisible by 11
I approach this problem by using above condition.
1. recursive function 2. combination

my java code is below

package numberFrom400;importjava.util.Arrays;importeuler.util.EulerUtil;publicclassnumber491{publicstaticlong totalCase =0;publicstaticint total =0;publicstaticint sum =90;publicstaticvoidmain(String args[]){long start = System.currentTimeMillis();int numbers[]=newint[10]; searching(0,0, numbers); System.out.println(totalCase); System.out.println(System.currentTimeMillis()-start);}publicstaticvoidsearching(int position,int count,int[]arr ){if(position>=arr.length){if(count ==10){// 여기서 시작한다. 왼쪽 섬int subsum =0;for(int i =0; i < arr.length; i++){if(arr[i]!=0){int val = i *arr[i];…

### Combsort in python

this is combsort in python
if you want to see detail of combsort  refer this sites
https://en.wikipedia.org/wiki/Comb_sort http://www.geeksforgeeks.org/comb-sort/

below is my python code
arr = [8, 4, 1, 56, 3, -44, 23, -6, 28, 0] def combsort(arr): gap = len(arr) swapped = True while gap !=1 or swapped: gap= int(gap//1.3) if gap==0: gap =1swapped = False for i in range(0, len(arr)-gap): if arr[i] > arr[i+gap]: swap(arr, i , i+gap) swapped = Trueprint(arr) def swap(arr, i, j): temp = arr[i] arr[i] = arr[j] arr[j] = temp combsort(arr) print(arr)

### shell sort in python

arr = [12, 34, 54, 2, 3] def shellsort(arr): n = len(arr) gap = int(n/2) while gap > 0 : for i in range(gap, n): temp = arr[i] j = i while j>=gap and arr[j-gap] >temp: arr[j] = arr[j-gap] j-= gap arr[j] = temp gap//=2shellsort(arr) print(arr)

### Problem 321

You can get hint from this image

M(n) = k(k+1)/2

this is triangle numbers k(k+1)/2
and you will finally get X^2 - 8Y^ - 7 = 0

### Bucket Sort in python

I make buckets as many as size of arr
and put data.

arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434] def bucketSort(arr, size): buckets = [[] for i in range(size)] # put arr in bucket for i in range(len(arr)): num = size*arr[i] buckets[int(num)].append(arr[i]) output = [] # use insertion sort for i in range(len(buckets)): insertionSort(buckets[i]) # concat all data for i in range(len(buckets)): while len(buckets[i]) > 0: output.append(buckets[i].pop(0)) return output def swap(arr, i, j): temp = arr[i] arr[i] = arr[j] arr[j] = temp def insertionSort(arr): for i in range(1, len(arr)): index= i print("index : " + str(i)) while index!=0: if arr[index] < arr[index-1]: temp = arr[index] arr[index]= arr[index-1] arr[index-1] = temp index = index-1print(arr) else …

### Count sort in Python

this is my python code for count sort
you can run

arr = [1, 4, 1, 2, 9, 5, 2] def countSort(arr): #find max range mval =0; for i in range(len(arr)): mval = max(mval, arr[i]) # 배열 초기화 temp = [0]*(mval+1) output = [0]*(len(arr)) # counting for i in range(len(arr)): temp[arr[i]] =temp[arr[i]] + 1print(temp)   # recounting for i in range(1, len(temp)): temp[i]= temp[i-1] + temp[i] # counting sort for i in range(len(arr)): output[temp[arr[i]] -1] = arr[i] temp[arr[i]] = temp[arr[i]] -1print(temp) print(output) countSort(arr)

### Problem 346 in project euler

This problem was easy to me that make my brain to take a rest.

the steps to solve
1. I had to find range of base that number can cover 10^2
It was sqrt of 10^2 include itself.
2. generater all possible base numbers
ex) in 2 base
11, 111, 1111 ...
3    7     15
3. exclude 2 digit number.
4. put set to real number
5. sum of set

this is my solution.