与えられた整数に対して最も小さい反復反復を見つけるためのより良いアルゴリズム

Question

この質問はHackerRank上で見つけられました。ここでは、最小反復回数を見つけるはずでした（正の整数は、他の正の整数よりも約数が少ないそれ自身よりも）。 5.

するよう

、ユーザ入力5あれば6は、任意の数のB/W 1よりも多くの約数を有するように、次に最小antiprime数は、6であろう

私のアプローチ： - 各々に対して除数の数を格納ハッシュセット内の1からnまで、次にn + 1からは、ハッシュセット内の除数よりも多くの除数を持つ整数をチェックします。

public static int send(int n) 
    { 
     HashSet hs = new HashSet() ; 
     for(int i=1 ; i<=n ; i++) 
     { 
      hs.add(div(i)) ; 
     }  
     for(int i= n+1 ; ; i++) 
     { 
      if(Collections.max(hs).compareTo(div(i)) < 0) 
      { 
       return i ; 
      }  
     }  
    }  
    public static int div(int n) 
    { 
     int ctr = 0 ; 
     for(int i=1 ; i<=n ; i++) 
     { 
      if(n % i == 0) 
       ctr++ ; 
     }  
     return ctr ; 
    } 

ロジックは完璧に動作しますが、私はそれはO（N^2）で見るように、すべてのテストケースでは、それは複雑以来、タイムアウトを返しました。

だから、私は比較的小さい時によく行うことができ、より良いアルゴリズムを、提案してください。

Answer 1

あなたは、あなたは除数の数がピーク（Antiprime番号）ヒット毎回保存することができ、Set<>データ構造を使用することができます。それはO(logn)時間に6を返します5のためのように、あなたはその後、数から次の最大のものを得るためにceiling()のようなものを呼び出すことができます。また、出力の場合はStringBuilderを使用し、結果を作成して出力してください。私にとっては、最初はSystem.out.println()で動作しませんでしたが、結果はStringBuilderとなり、その後append()となりました。最後にStringBuilderの.toString()を実行してください。参考までに、私はコンテストで全体的に（2000年以上で）8位になったので、それは私のために働いて完璧になった。私はここのコメントで述べた修正組み込ま

Answer 2

：質問をdownvoting人々のため

public static int send(int n) 
    { 
     HashSet hs = new HashSet() ; 
     for(int i=int(n/2)+1 ; i<=n ; i++) 
     { 
      hs.add(div(i)) ; 
     } 
     int markToBeat = Collections.max(hs); 
     for(int i=n+1 ; ; i++) 
     { 
      if(div(i) > markToBeat) 
      { 
       return i ; 
      } 
     }  
    }  
    public static int div(int n) 
    { 
     int ctr = 0 ; 
     for(int i=1 ; i<=sqrt(n) ; i++) 
     { 
      if(n % i == 0) 
       ctr++ ; 
     }  
     return ctr ; 
    }