Solution28.java

public class Solution28{
   
    static int square(int n){
        if(n == 0||n == 1){
            return n;
        }
        if(n < 0){
            n -= n; 
        }
        if(n % 2 != 0){
            return ((square(n>>1)<<2) + ((n>>1)<<2)+1);
        }
        else{
            return square(n >> 1)<< 2;
        }
    }
    public static void main(String[] args) {
        // For each new spiral layer, I found that the difference between corner values increases by a factor of two.
        // Initially, we can see that 3 - 1 = 2, 5 - 3 = 2, 7 - 5 = 2, 9 - 7 = 2.
        // Then, for the second spiral layer, we have these corner values: {9,13,17,21,25}, where 9 is the end of the previous layer and the start of this new layer.
        // Now, we can see that 13 - 9 = 4, 17 - 13 = 4, 21 - 17 = 4, 25 - 21 = 4. This difference increases by a factor of 2 for each successive spiral layer.
        // Also, we can express successive corner values in a given spiral layer in terms of the starting value of the spiral layer, as shown: 
        // for some 0 <= j < spiralSequence.length, with j representing a specific corner of the new spiral: 
        //      j = 0 -> start
        //      j = 1 -> upper right corner.
        //      j = 2 -> upper left corner.
        //      j = 3 -> lower left corner. 
        //      j = 4 -> lower right corner (end of a single spiral.), 
        // we have that (new corner) = starting value + ((2 * step variable for increasing differences between corner values by factor of 2) * position of new corner 
        // Code Translation -> spiralSequence[j] = spiralSequence[0] + ((2 * step) * j).
        
        // At each iteration, we just have to keep track of the new corner values generated by the method described above and since these values are corners of each successive spiral layer. 
        // This implies that they must also be part of the diagonals of the entire spiral itself.
        // So, we must simply sum up these values to obtain the desired solution.
    
        int diagSum = 1;
        int[] spiralSequence = {1,3,5,7,9};
        //This step variable keeps track of the current factor of 2 for the differences in corner values of successive spiral layers.
        int step = 2;
        while(spiralSequence[4] <= square(1001)){
            //i = 0 -> initially it is the center of the entire spiral, but at each step this value is the start of a new spiral layer.
            //i = 1 -> upper right corner.
            //i = 2 -> upper left corner.
            //i = 3 -> lower left corner. 
            //i = 4 -> lower right corner (end of a single spiral.)  
            for(int i = 1;i < spiralSequence.length;i++){
                diagSum += spiralSequence[i];
            }
            //Set start of new spiral layer to be the end of the previous spiral layer.  
            spiralSequence[0] = spiralSequence[4];

            for(int j = 0; j < spiralSequence.length;j++){
                //Computing new corner values.
                spiralSequence[j] = spiralSequence[0] + ((2 * step) * j);
            }

            //At next iteration, differences between corner values will have increased by factor of 2.
            step++;
        }
        System.out.println(diagSum);
    }
}