### problem 293

This problem was some how easy.

Using DFS and Set

I could solve it.

Using DFS and Set

I could solve it.

Showing posts from March, 2016

- Get link
- Google+
- Other Apps

# 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)

- Get link
- Google+
- Other Apps

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];…

- Get link
- Google+
- Other Apps

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)

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)

- Get link
- Google+
- Other Apps

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 …

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 …

- Get link
- Google+
- Other Apps

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)

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)

- Get link
- Google+
- Other Apps

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.

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.