SRM 367 250pt: ObtainingDigitK

TopCoder

問題概要

50桁以下の数字が与えられる。最小でいくつ加えたらある数字Kが出てくるか求める問題。

考えたこと

  • 1の位見るだけじゃないか。
  • 当然繰り上がりとか考慮してないから落ちる。
  • 多倍長の計算とかしたくないのでJavaで書く。通った。

practiceで通ったコード

計算量だいたい定数。(ホントは桁数分くらい)。

import java.math.BigInteger;

public class ObtainingDigitK{

    public int minNumberToAdd(String orig, int k){
        for(int i=0; i<10; i++){
            BigInteger a = new BigInteger(orig);
            a = a.add(BigInteger.valueOf(i));
            String str = a.toString();
            for(int j=0; j<str.length(); j++){
                if(str.charAt(j) == (char)(k + '0')) return i;
            }
        }
        return -1;
    }

}