Discussion :

[misterJay973]

Bonsoir à la communauté,

J'ai débuté un autre exercice sur codefight (addTwoHugesNumbers).

en input j'ai donc deux ListNode d'Integer et je dois retourner la somme de ces deux "huges integer" sous le même format comme dans l'exemple ci dessous:

a = [9876, 5432, 1999] ; b = [1, 8001],
addTwoHugeNumbers(a, b) = [9876, 5434, 0].

Voici mon code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
ListNode<Integer> addTwoHugeNumbers(ListNode<Integer> a, ListNode<Integer> b) {
 
  ListNode <Integer> NodeA = a;
  ListNode <Integer> NodeB = b;
  ListNode <Integer> myNodeA = null;
  ListNode <Integer> myNodeB = null;
  ListNode <Integer> resultNode = null;
  long number1= 0;
  long number2= 0;
  long sum=0;
 
  while (a != null){
    ListNode <Integer> temp1 = new ListNode (a.value);
      temp1.next = myNodeA;
      myNodeA=temp1;
      if (number1 ==0){
        number1 = myNodeA.value.intValue();
      }
    else{
      number1 = Long.parseLong(String.valueOf(number1) + String.valueOf(myNodeA.value.intValue()));
      }
      a = a.next;
  }
 
  while (b != null){
    ListNode <Integer> temp2 = new ListNode (b.value);
      temp2.next = myNodeB;
      myNodeB=temp2;
    if (number2 ==0){
      number2 = myNodeB.value.intValue();
      }
    else{
      number2 = Long.parseLong(String.valueOf(number2) + String.valueOf((myNodeB).value.intValue()));
      }
      b = b.next;
  }
 
  sum = number1 + number2;
 
  return resultNode;
}

mon problème se situe au niveau de la conversion en long que je cherche à effectuer au niveau du number2 qui se trouve dans le else. Je bloque à ce niveau la pour le moment, sachant que dans la console de codefight j'ai:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Exception in thread "main" java.lang.AssertionError: java.lang.reflect.InvocationTargetException
	at myCode._invoke(file.java on line ?)
	at myCode.main(file.java on line ?)
Caused by: java.lang.reflect.InvocationTargetException
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:498)
	at myCode._invoke(file.java on line ?)
	... 1 more
Caused by: java.lang.NumberFormatException: For input string: "99989999999999999999"
	at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
	at java.lang.Long.parseLong(Long.java:592)
	at java.lang.Long.parseLong(Long.java:631)
	at _runpftgi.addTwoHugeNumbers(file.java on line 42)
	... 6 more

Pour la suite:
Après la conversion en long, j'avais dans l'idée de réaliser la somme de number1 et de number2, ensuite je compte travailler sur cette variable sum qui stockera le resultat pour ensuite venir parser 4 par 4 le chiffre et l'intégrer dans un listNode, pour présenter le résultat dans une forme identique aux deux ListNode fourni en input.

Je vous remercie d'avance pour l'aide que vous pourrez m'apporter aussi bien au niveau de mon blocage que de mon raisonnement pour la suite.

Cdlt,
misterJay973.

[misterJay973]

Bonjour,

Peut etre que l'utilisation de BigInteger règlerait mon problème mais je me permet de vous demander un peu d'aide car j'ai du mal à m'en sortir avec la synthaxe:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
ListNode<Integer> addTwoHugeNumbers(ListNode<Integer> a, ListNode<Integer> b) {
 
  ListNode <Integer> NodeA = a;
  ListNode <Integer> NodeB = b;
  ListNode <Integer> myNodeA = null;
  ListNode <Integer> myNodeB = null;
  ListNode <Integer> resultNode = null;
  BigInteger [] number1= new BigInteger[0];
  BigInteger [] number2= new BigInteger[0];
  BigInteger [] sum=new BigInteger[0];
 
  while (a != null){
    ListNode <Integer> temp1 = new ListNode (a.value);
      temp1.next = myNodeA;
      myNodeA=temp1;
      if (number1 ==0){
        number1 = myNodeA.value.intValue();
      }
    else{
      number1 = Integer.BigInteger(String.valueOf(number1) + String.valueOf(myNodeA.value.intValue()));
      }
      a = a.next;
  }
  //for (Integer nA : myNodeA){
 
  //}
  while (b != null){
    ListNode <Integer> temp2 = new ListNode (b.value);
      temp2.next = myNodeB;
      myNodeB=temp2;
    if (number2 ==0){
      number2 = myNodeB.value.intValue();
      }
    else{
      number2 = Integer.BigInteger(String.valueOf(number2) + String.valueOf((myNodeB).value.intValue()));
      }
      b = b.next;
  }
  //for (Integer nB : myNodeB){
 
  //}
 
  sum = number1 + number2;
 
 
 
 
  return resultNode;
}

console:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
file.java on line 25: error: incomparable types: BigInteger[] and int
      if (number1 ==0){
                  ^
file.java on line 26: error: incompatible types: int cannot be converted to BigInteger[]
        number1 = myNodeA.value.intValue();
                                        ^
file.java on line 29: error: cannot find symbol
      number1 = Integer.BigInteger(String.valueOf(number1) + String.valueOf(myNodeA.value.intValue()));
                       ^
  symbol:   method BigInteger(String)
  location: class Integer
file.java on line 40: error: incomparable types: BigInteger[] and int
    if (number2 ==0){
                ^
file.java on line 41: error: incompatible types: int cannot be converted to BigInteger[]
      number2 = myNodeB.value.intValue();
                                      ^
file.java on line 44: error: cannot find symbol
      number2 = Integer.BigInteger(String.valueOf(number2) + String.valueOf((myNodeB).value.intValue()));
                       ^
  symbol:   method BigInteger(String)
  location: class Integer
file.java on line 52: error: bad operand types for binary operator '+'
  sum = number1 + number2;
                ^
  first type:  BigInteger[]
  second type: BigInteger[]
Note: /usercode/file.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
7 errors

Voila, je regarde également la javadoc concernant le BigInteger mais un peu de mal a retranscrire ça ^^

[joel.drigo]

Salut,

Le souci c'est que tu cherches à passer par un parsing qui est censé convertir un String en long, nombre qui est limité en taille (64bits, donc compris entre -2⁶³ et 2⁶³-1, inclus). Donc si le String est un nombre en dehors de l'intervalle, tu auras une erreur, parce que la méthode ne peut stocker le résultat dans un long.

En dehors de l'utilisation d'une classe permettant de représenter les grands nombres (java.math.BigInteger), le principe est plutôt de se reposer sur la méthode arithmétique de base, sur la définition de l'addition, c'est-à-dire sur le report de retenue. Quand tu additions 12 et 29 par exemple, tu fais 2+9=11, donc 11 étant supérieur à 9, tu retires la base, 10, ça te donne 1 et une retenue de 1, et donc ensuite, tu fais 1+2+la retenue, ce qui donne 4, est donc le résultat est 41. Applique ce même principe, en additionnant 2 int, et en déduisant du résultat la partie à reprendre dans un int, et la partie à additionner au prochain int à gauche, un int aussi. Au final, on va avoir à additionner au maximum 3 int, ce qui ne tient pas sur un int bien sûr, mais qui ne pas non plus sur un long (parce qu'un int c'est 32 bits, donc le plus grand long = 2 fois le plus grand int. Cependant, somme = a+b+c peut se transformer en somme=a+b puis somme=somme+c, un long plus un int, tenant sur un int. Enfin, attention éventuellement au signe, le plus grand int plus le plus grand int dans le plus grand long, plus la retenue, on passe en overflow, donc en négatif. Solution simple, faire l'extraction de retenue non pas à la fin, mais pour chacune des deux "sous-additions".

[EDIT]
java.lang.Integer.BigInteger n'existe pas, parce que la classe c'est java.math.BigInteger.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
import java.math.BigInteger;
public class Exemple {
  	public static void main(String[] args) {
 
		BigInteger bigInteger = new BigInteger("123456789");
 
	}
 
}

[misterJay973]

Je vois l'idée, merci pour l'explication.

Je vais voir ce que j'arrive a faire. Autre question, la solution qui est proposée avec les retenu ne pose pas de probleme avec les ListNode ? je pose la question parce que pour le moment j'ai pas une visibilité parfaite de la chose

misterJay973

[joel.drigo]

Autre question, la solution qui est proposée avec les retenu ne pose pas de probleme avec les ListNode

Non, à priori. Seulement, je ne vois pas trop pourquoi tu passes par cette classe, au lieu de traiter des tableaux d'int.

NB. En jetant un coup d'œil au résultat escompté, j'ai l'impression qu'il ne s'agit ni de Integer ni de BigInteger, mais simplement de nombres compris entre 0 et 10000 exclu, donc beaucoup plus simple (pas d'overflow, pas besoin de long, etc.). A noter que ça voudrait dire que [1,0,9999] représente 100009999 et non pas 109999 !

[misterJay973]

J'aurais effectivement du donner l'ennoncé:


[1,0,9999] représente bien 100009999

Ensuite je travaille avec ListNode dont la définition est la suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
// Definition for singly-linked list:
// class ListNode<T> {
//   ListNode(T x) {
//     value = x;
//   }
//   T value;
//   ListNode<T> next;
// }
//

la classe ListNode m'est "imposé" dans le cadre des exercices sur les linkedList. je n'ai pas vu d'autre façon de parcourir un ListNode. Ca n'a pas été facile pour moi mais j'arrive quand mm a comprendre et a trouver des solutions même si la je suis encore un peu bloqué par des problèmes de synthaxe

Je ne peux pas parcourir un ListNode de la même façon qu'avec un tableau ^^.

[joel.drigo]

Ok, donc on est bien face à des nombres de 0 à 10000 exclu. Pas d'overflow sur un int possible donc (9999+9999 tient sur un int, 9999+9999+9999 tient aussi).
Le souci avec ListNode est qu'il est bien plus naturel est facile de partir de la fin. Cependant, avec de la récursivité, ou une pile, on peut s'en sortir facilement. Et ça facilite le résultat final, en fonction de l'existence ou non d'une retenue finale.