Java hashmap

phew, so glad it did not throw TLE; thought it might though, for N = 30000.

This link was quite helpful in understanding how the conversions are to be done. https://math.stackexchange.com/questions/265690/continued-fraction-of-a-square-root

Okay, so we already know the answer before N=14, so start with odd period count = 4. For every number, find it's nearest square root. That's the number you'll subtract (and add) in the first conversion (as shown in the problem statement). Also, if the number is a perfect square, we'll skip that.

Now, we pass the number, and it's nearest square root to the function: convert. I'll first explain what are the variables; a is the natural number in the series expansion (i.e., in the example of sqrt(23), 'a' would be 4, 1, 3, 1, 8). And how do we calculate that? for instance, let's take the 2nd expansion of sqrt(23).

1 + 1/(7/(sqrt(23)-3))

If you calculate (int) 7/(sqrt(23)-3), it'll be 3, which is 'a' for the next expansion.

right is the number which you see as the right number in the numerator in every expansion. This can be calculated by first calculating 'a', multiplying 'a' with 'den' and subtracting the previous right value. and num and den are the numerator and denominator respectively.

Now as we can see 1 comes two times, so we cannot just call off the series when a number comes again. we need a more concrete way, to figure out when the series repeat. So we'll try to form a unique signature for every expansion in the series. this can be done by storing all => a, right and den as a string along with the index at which they occured, so that we can calculate the period with that. This is done using a HashMap unique At any iteration, if the unique signature repeats, that means our search is ended. We find the period, and check if that's odd or not, and then continue for the next number.

Also, after every iteration the rationalised fraction needs to be in its simplest form, i.e., 7/14 -> 1/2. for, that, i take the Greatest Common Divisor and divide the denominator with it. Source for the gcd function: https://www.baeldung.com/java-greatest-common-divisor

import java.util.*;

public class Solution {
    Map<String, Integer> unique;
    int odds = 4;
    private void driver(int num){
        for(int i=14; i<num; i++){
            unique = new HashMap<>();
            double sq = Math.sqrt(i);
            if(sq == (int) sq) continue;
            convert(i, (int) sq);
        }
        System.out.println(odds);
    }

    private void convert(int n, int right){
        int den = 1, a = right, index = 0, num = 1;
        String uniq = a + " " + right + " " + den;
        unique.put(uniq, index++);
        while(true) {
            den = n - right*right;
            int gcd = gcd(num, den);
            den /= gcd;
            a = (int) (num / (Math.sqrt(n) - right));
            right = den * a - right;
            uniq = a + " " + right + " " + den;
            if(unique.containsKey(uniq)){
                if((index - unique.get(uniq)) % 2 == 1) odds++;
                return;
            }
            else unique.put(uniq, index++);
            num = den;
        }
    }

    private int gcd(int a, int b) {
        if (a == 0) return b;
        if (b == 0) return a;
        int n;
        for (n = 0; ((a | b) & 1) == 0; n++) {
            a >>= 1;
            b >>= 1;
        }
        while ((a & 1) == 0)
            a >>= 1;
        do {
            while ((b & 1) == 0)
                b >>= 1;
            if (a > b) {
                int temp = a;
                a = b;
                b = temp;
            }
            b = (b - a);
        } while (b != 0);
        return a << n;
    }
    
    public static void main(String[] args) {
        new Solution().driver(new Scanner(System.in).nextInt());
    }
}