Java: Somme du tableau 2D où M [i] [j] = (int) i/j

Question

T - nombre de tests élémentaires | 1 < = T < = 10 et n - nombre d'éléments | 1 < = n < = 1000000

Exemples

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

besoin de trouver la somme de M [i] [j], où M [i] [j] = (int) i/j;

J'ai écrit le code, mais pour n> 10000, je commence à obtenir OOM, (pour une raison évidente).

Si quelqu'un peut m'aider, ça va être génial. Besoin d'une toute nouvelle approche pour résoudre le problème.

Par exemple.

Input Output 
2  
2  4 
4  17 

Answer 1

Ici, il est évident que vous n'avez pas besoin de stocker les valeurs dans les matrices, car il est impossible d'avoir beaucoup d'espace (Array[10000][10000]) disponible à allouer. Donc, vous devez penser d'une façon ou d'une autre d'une manière mathematical. Envisager une matrice 4x4 et représenter chaque élément au terme de 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 

Maintenant, nous pouvons représenter ici ce qui est stocké dans chacun de ces éléments.

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 

Tackle cette matrice en le divisant en colonnes et résoudre chacun des columns. Pour la première série de colonnes serait 1+2+3+4. Ensuite, pour le numéro de colonne two(2) la série serait 0+1+1+2.

Avis ici que pour ith colonne firsti-1 valeurs sont des zéros et i values sont identiques dans la colonne. Puis value est augmenté. Encore une fois, il en sera de même pour les valeurs i. Encore une fois augmente de 1 et ainsi de suite.

Donc, dans ith valeur de la colonne obtenir increased sur l'élément jth où .

Vous pouvez donc implémenter cette logique dans le tableau 1-D et la complexité de cette approche sera O(n logn) pour chaque boîtier de test.

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