## Wednesday, March 30, 2016

### problem 293

This problem was some how easy.

Using DFS and Set

I could solve it.

## 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;
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 ==1  ){
leftCase = (leftCase - EulerUtil.getFactorial(9)/(long)Math.pow(2, twocount));
}else if (arr ==2) {
leftCase = (leftCase - EulerUtil.getFactorial(9)/(long)Math.pow(2, twocount-1));
}

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

## 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 = *(mval+1)
output = *(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.