FilesExpand file tree

 master

/

CollatzConjecture.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

56 lines (50 loc) · 1.16 KB

 master

/

CollatzConjecture.java

Copy path

Top

File metadata and controls

• Code
• Blame

56 lines (50 loc) · 1.16 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

50

51

52

53

54

55

56

/**

*

*/

public class CollatzConjecture {

// public int maxSteps(int n) {

// if (n < 1) return -1;

// int res = -1;

// for (int i=1; i<=n; i++) {

// res = Math.max(res, steps(i));

// }

// return res;

// }

// public int steps(int i) {

// int res = 0;

// while (i != 1) {

// if (i % 2 == 0) {

// i = i / 2;

// } else {

// i = i * 3 + 1;

// }

// }

// return res;

// }

public int maxSteps(int n) {

if (n < 1) return -1;

int res = -1;

int[] memo = new int[n+1];

for (int i=1; i<=n; i++) {

res = Math.max(res, steps(i, memo));

}

return res;

}

public int steps(int i, int[] memo) {

int res = 0;

int p = i;

while (p != 1) {

if (memo[p] > 0) {

memo[i] = res = memo[p];

return memo[i];

}

if (p % 2 == 0) {

p = p / 2;

} else {

p = p * 3 + 1;

}

}

memo[i] = res;

return res;

}

}