Skip to main content

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;
 }
 
}

Comments

Popular posts from this blog

codefights smooth sailing ( CommonCharacterCount)

https://codefights.com/arcade/intro/level-3/JKKuHJknZNj4YGL32publicstaticintcommonCharacterCount(String s1, String s2) { int sum = 0; char[] as= s1.toCharArray(); char[] bs= s2.toCharArray(); int[] ias = newint[126]; int[] ibs = newint[126]; for (int i = 0; i < as.length; i++) { ias[(int)as[i]]++; } for (int i = 0; i < bs.length; i++) { ibs[(int)bs[i]]++; } for (int i = 0; i < ibs.length; i++) { sum += Math.min(ias[i], ibs[i]); } return sum; }

Given two strings, find the number of common characters between them. Example For s1 = "aabcc" and s2 = "adcaa", the output should be
commonCharacterCount(s1, s2) = 3. Strings have 3 common characters - 2 "a"s and 1 "c". Input/Output [time limit] 3000ms (java)[input] string s1 A string consisting of lowercase latin letters a-z. Guaranteed constraints:
1 ≤ s1.length ≤ 15. [input] string s2 A string consisting of lowercase latin letters a-z. Guaranteed constr…

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 …