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