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;

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

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

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)

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

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)

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.