This problem was some how easy.

Using DFS and Set

I could solve it.

## Wednesday, March 30, 2016

## Tuesday, March 29, 2016

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

## Wednesday, March 23, 2016

### 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; import java.util.Arrays; import euler.util.EulerUtil; public class number491 { public static long totalCase = 0; public static int total = 0; public static int sum = 90; public static void main(String args[]){ long start = System.currentTimeMillis(); int numbers[] = new int[10]; searching(0, 0, numbers); System.out.println(totalCase); System.out.println(System.currentTimeMillis()-start); } public static void searching(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]; subsum += val; } } if((subsum -(sum - subsum))%11 ==0){ // System.out.println("this num is divisible"); // System.out.println(Arrays.toString(arr)); // System.out.println(Arrays.toString(reversse(arr)) + " re "); // 여기가 Divisible이 가능한 위치 int twocount = 0; for (int i = 0; i < arr.length; i++) { if(arr[i]== 2){ twocount ++; } } long leftCase = EulerUtil.getFactorial(10)/(long)Math.pow(2, twocount); if(arr[0] ==1 ){ leftCase = (leftCase - EulerUtil.getFactorial(9)/(long)Math.pow(2, twocount)); }else if (arr[0] ==2) { leftCase = (leftCase - EulerUtil.getFactorial(9)/(long)Math.pow(2, twocount-1)); } int[] reverse = reversse(arr); // right case twocount = 0; for (int i = 0; i < reverse.length; i++) { if(reverse[i]== 2){ twocount ++; } } long rightCase = EulerUtil.getFactorial(10)/(long)Math.pow(2, twocount); totalCase = totalCase + (leftCase * rightCase ); }else{ } total++; return; }else if(count > 5){ return; } return; } for (int i = 0; i < 3; i++) { arr[position] = i; searching(position+1, count+i, arr); arr[position] = 0; } } public static int[] reversse (int arr[]){ int reverse[]= new int[arr.length]; for (int i = 0; i < arr.length; i++) { reverse[i] = 2 - arr[i]; } return reverse; } }

### Combsort in python

this is combsort in python

if you want to see detail of combsort

refer this sites

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 =1 swapped = False for i in range(0, len(arr)-gap): if arr[i] > arr[i+gap]: swap(arr, i , i+gap) swapped = True print(arr) def swap(arr, i, j): temp = arr[i] arr[i] = arr[j] arr[j] = temp combsort(arr) print(arr)

## Sunday, March 20, 2016

### 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//=2 shellsort(arr) print(arr)

## Thursday, March 17, 2016

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

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

this is triangle numbers k(k+1)/2

and you will finally get X^2 - 8Y^ - 7 = 0

## Wednesday, March 16, 2016

### 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-1 print(arr) else : break print(bucketSort(arr, len(arr)))

## Sunday, March 13, 2016

### 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]] + 1 print(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]] -1 print(temp) print(output) countSort(arr)

## Friday, March 11, 2016

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

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.

Subscribe to:
Posts (Atom)