처음 9 자리 자르기

Question

좋아요. 제 친구 중 한 명이 저에게 준 도전 과제를 풀려고 노력하고 있습니다. 글쎄요, BigInteger에서 마지막 9 자리를 자르려고했습니다. 잘 렸습니다. 처음 9 개가 너무 느리고 너무 오래 걸렸습니다.

처음 9 개와 9 개가 필요한 이유는 BigInteger이고 처음과 마지막은 pandigital입니다.

당신은 우리가 n = new BigInteger("123456789987654321") 잘 나가 "123456789"와 별도로은 "987654321"를 얻을 필요가 있다고 말은, 나는 그것이 매우 때문에이 문자열로의 BigInteger를 변환 할 NOT 을 이해하지 않는 경우 느린 과정.

여기서는 속도를 높이려고합니다.이 솔루션에 난처한 점이 있습니다. 황금 비율을 사용하는 것에 대해 들었습니다. 관심이 있다면 여기에 내 코드가 있습니다.

import java.math.BigInteger; 

public class Main { 

    public static void main(String...strings) 
    {  
     long timeStart = System.currentTimeMillis(); 
     fib(350_000); 
     long timeEnd = System.currentTimeMillis(); 
     System.out.println("Finished processing, time: " + (timeEnd - timeStart) + " milliseconds."); 
    } 

    public static BigInteger fib(int n) 
    { 
     BigInteger prev1 = BigInteger.valueOf(0), prev2 = BigInteger.valueOf(1);   
     for (int i = 0; i < n; i++) 
     { 

      // TODO: Check if the head is pandigital as well. 
      BigInteger tailing9Digits = tailing9Digits(prev1); 
      boolean tailPandigital = isPanDigital(tailing9Digits); 

      if (tailPandigital) 
      {     
       System.out.println("Solved at index: " + i); 
       break; 
      } 
      BigInteger savePrev1 = prev1; 
      prev1 = prev2; 
      prev2 = savePrev1.add(prev2); 
     } 
     return prev1; 
    } 

    public static BigInteger leading9Digits(BigInteger x) 
    { 
     // STUCK HERE. 
     return null; 
    } 

    public static BigInteger tailing9Digits(BigInteger x) 
    { 
     return x.remainder(BigInteger.TEN.pow(9)); 
    } 

    static BigInteger[] pows = new BigInteger[16]; 

    static 
    { 
     for (int i = 0; i < 16; i++) 
     { 
      pows[i] = BigInteger.TEN.pow(i); 
     } 
    } 

    static boolean isPanDigital(BigInteger n) 
    { 
     if (!n.remainder(BigInteger.valueOf(9)).equals(BigInteger.ZERO)) 
     { 
      return false; 
     } 
     boolean[] foundDigits = new boolean[9]; 


     boolean isPanDigital = true; 
     for (int i = 1; i <= 9; i++) 
     { 
      BigInteger digit = n.remainder(pows[i]).divide(pows[i - 1]); 
      for (int j = 0; j < foundDigits.length; j++) { 
       if (digit.equals(BigInteger.valueOf(j + 1)) && !foundDigits[j]) 
       { 
        foundDigits[j] = true; 
       } 
      } 
     } 

     for (int i = 0; i < 9; i++) 
     { 
      isPanDigital = isPanDigital && foundDigits[i]; 
     } 

     return isPanDigital; 
    } 
} 

Answer 1

BigInteger 나는 속도에 대해 전혀 신경 쓰지 않는 것이 좋습니다. 대부분의 메서드는 제대로 구현되지 않았기 때문에 일반적으로 코드가 매우 느려집니다.

나누기 및 기수 변환에 도움이되는 분할 및 정복 트릭이 있습니다.

먼저, BigInteger의 multiply()은 2 차입니다. 이 문제를 해결해야합니다. 그렇지 않으면 이러한 분할 및 정복 트릭으로 인해 속도가 향상되지 않습니다. 고속 푸리에 변환을 통한 곱셈은 비교적 빠르고 빠릅니다.

당신은 10을 기반으로 반복하여 진수하는 256^k을 한 후, 재귀-10을 기반으로 변환 할 a * 256^k + b. 하나는 a 변환됩니다 할 수있는 일이하고 b로 절반 (비트)에서 휴식하고 작성하는 BigInteger을 변환하려면 제곱 한 다음 기수 10에 a을 곱한 후 256^k을 곱한 다음 결과에 b을 더합니다. 또한 처음 몇 자리에만 관심이 있기 때문에 b의 작은 숫자를 추가하면 a * 256^k의 처음 몇 자리가 영향을받지 않을 수도 있습니다. b으로 변환 할 필요조차 없습니다.

비슷한 트릭이 나눗셈에 사용됩니다.

toByteArray() 방법을 사용하여 비트 이동 및 추출을 수행 할 수 있습니다.

Answer 2

어쩌면이 너무 빨리가 아니라 적어도 그것은 간단

BigInteger n = new BigInteger("123456789987654321"); 
    BigInteger n2 = n.divide(BigInteger.TEN.pow(new BigDecimal(n).precision() - 9)); 
    BigInteger n1 = n.remainder(new BigInteger("1000000000")); 
    System.out.println(n1); 
    System.out.println(n2); 

출력

987654321 
123456789 

Answer 3

그런데 나는 이것이 당신이 필요 믿습니다 :

이

import java.math.BigInteger; 

public class PandigitalCheck { 

    public static void main(String[] args) { 

     BigInteger num = new BigInteger("12345678907438297438924239987654321"); 
     long timeStart = System.currentTimeMillis(); 
     System.out.println("Is Pandigital: " + isPandigital(num)); 
     long timeEnd = System.currentTimeMillis(); 
     System.out.println("Time Taken: " + (timeEnd - timeStart) + " ms"); 
    } 

    private static boolean isPandigital(BigInteger num) { 
     if (getTrailing9Digits(num).compareTo(getLeading9Digits(num)) == 0) { 
      return true; 
     } 

     return false; 
    } 

    private static BigInteger getLeading9Digits(BigInteger num) { 
     int length = getBigIntLength(num); 
     BigInteger leading9 = BigInteger.ZERO; 
     for (int i = 0; i < 9; i++) { 
      BigInteger remainder = num.divide(BigInteger.TEN.pow(length - 1 - i)); 
      leading9 = leading9.add(remainder.multiply(BigInteger.TEN.pow(i))); 
      num = num.remainder(BigInteger.TEN.pow(length - 1 - i)); 
     } 

     return leading9; 
    } 

    private static int getBigIntLength(BigInteger num) { 
     for (int i = 1; ; i++) { 
      if (num.divide(BigInteger.TEN.pow(i)) == BigInteger.ZERO) { 
       return i; 
      } 
     } 
    } 

    private static BigInteger getTrailing9Digits(BigInteger num) { 
     return num.remainder(BigInteger.TEN.pow(9)); 
    } 

} 

출력은 :

Is Pandigital: true 
Time Taken: 0 ms 

청구서에 부합합니까?

Answer 4

나는 자바에 대한 초보자 해요, 내가 문자열을 BigInteger를 변환하고 있습니다 만 그러나 그것은 조금 당신이 달성 한 가장 빠르고 무엇을 입력 무엇 코드

import java.math.BigInteger; 
public class Main { 
    public static void main(String args[]) 
    {  
     long timeStart = System.currentTimeMillis(); 
     String biStr = new BigInteger("123456789987654321").toString(); 
     int length=(biStr.length())/2; 
     String[] ints = new String[length]; 
     String[] ints2 = new String[length]; 
     for(int i=0; i<length; i++) { 
      int j=i+length; 
      ints[i] = String.valueOf(biStr.charAt(i)); 
      ints2[i] = String.valueOf(biStr.charAt(j)); 
      System.out.println(ints[i] +" | "+ints2[i]); 
     } 
     long timeEnd = System.currentTimeMillis(); 
     System.out.println("Finished processing, time: " + (timeEnd - timeStart) + " milliseconds."); 
    } 
}