Java: Summe der 2D-Anordnung, wobei M [i] [j] = (int) i/j

Question

T - Anzahl der Testfälle | 1 < = T < = 10 und n - Anzahl der Elemente | 1 = n < < = 1000000

Eg

if (T >= 1 && T <= 10) { 
    for (int i = 0; i < T; i++) { 
       int n = sc.nextInt(); 
       if (n > 0 && n <= 1000000) { 
        array = new int[n][n]; 
        System.out.print("\n" + sumOfArray(array, n)); 
       } 
      } 
      } 

benötigt die Summe von m [i] [j], wobei M [i] [j] = (int) i/j zu finden;

Ich habe den Code geschrieben, aber für n> 10000, bekomme ich OOM, (aus offensichtlichen Gründen).

Wenn mir jemand damit helfen kann, wird es großartig. Brauchen Sie einen ganz neuen Ansatz zur Lösung des Problems.

Eg.

Input Output 
2  
2  4 
4  17 

Answer 1

Hier Es ist offensichtlich, dass Sie die Werte in den Matrizen nicht speichern müssen, weil es nicht möglich ist, hat so vielen Platz (Array[10000][10000]) zur Verfügung zu vergeben. Also musst du irgendwie in einem mathematical Weg nachdenken.

Betrachten Sie eine 4x4 Matrix und repräsentieren jedes Element in der Laufzeit i,j.

1,1 1,2 1,3 1,4 
2,1 2,2 2,3 2,4 
3,1 3,2 3,3 3,4 
4,1 4,2 4,3 4,4 

Jetzt können wir hier darstellen, was in jedem dieser Elemente gespeichert ist.

1/1 1/2 1/3 1/4 (In Integers)  1 0 0 0 
2/1 2/2 2/3 2/4 ============>  2 1 0 0 
3/1 3/2 3/3 3/4      3 1 1 0 
4/1 4/2 4/3 4/4      4 2 1 1 

diese Matrix-Gerät, indem es in Spalten und lösen jede der columns dividiert wird. Für die erste Spalte Serie wäre 1+2+3+4. Dann für die Spalte Nummer two(2) wäre die Serie 0+1+1+2.

Hinweis hier, dass für ith Spalte firsti-1 Werte Nullen sind und dann i values sind in der Spalte gleich. Dann wird value erhöht. Wieder wird es für i Werte gleich sein. Erneut erhöht sich um 1 und so weiter.

So in ith Spaltenwert erhalten increased auf dem jth Element, in dem j%i==0.

So können Sie diese Logik in 1-D Array implementieren und die Komplexität dieses Ansatzes wird O(n logn) für jeden Testfall sein.

Code:

import java.util.Scanner; 

public class Main 
{ 
    public static void main(String args[]) 
    { 
     Scanner sc=new Scanner(System.in); 

     int testcases=sc.nextInt(); 

     while(testcases-- >0) 
     { 
      int n=sc.nextInt(); 

      long array[]=new long[n+1]; //Take long array to avoid overflow 

      for(int i=1;i<=n;i++) 
      { 
       for(int j=i;j<=n;j+=i) 
       { 
        array[j]++;   //This will store that which elements get increased 
             //from zero how many times 
       } 
      } 

      //Now we can do summation of all elements of array but we need to do prefix sum here 

      long sum=0; 
      for(int i=1;i<=n;i++) 
      { 
       array[i]+=array[i-1]; 
       sum+=array[i]; 
      } 

      System.out.println(sum); 
     } 
    } 
}