Java Basics for Problem Solving

1.The shape of every solution

Coding problems ask you to write one method inside a class called Solution. The judge (or later, our code runner) creates the class, calls your method with test inputs and compares the return value with the expected answer.

To test on your own computer, add a main method that calls your solution and prints the result. Save the file as Main.java and run it with java Main.java.

class Solution {
    public int sum(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;   // "for each x in nums"
        return total;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.sum(new int[]{3, 1, 4, 1, 5}));
    }
}

14

2.Number types and their limits

int is 32 bits: from −2,147,483,648 to 2,147,483,647 (about ±2.1 × 10⁹). long is 64 bits: about ±9.2 × 10¹⁸. double holds decimals but isn't exact (0.1 + 0.2 isn't exactly 0.3).

When a problem says values go up to 10⁹ and you add two of them, the sum can reach 2 × 10⁹, which doesn't fit in an int. Java doesn't raise an error: the value silently wraps to a negative number. Use long for sums and products that might exceed about 2 × 10⁹.

Integer.MAX_VALUE and Integer.MIN_VALUE are handy starting values for "smallest so far" and "largest so far".

public class Main {
    public static void main(String[] args) {
        int a = 2_000_000_000, b = 2_000_000_000;
        System.out.println(a + b);            // wraps around
        System.out.println((long) a + b);     // cast first: correct
        System.out.println(Integer.MAX_VALUE + 1);
    }
}

-294967296
4000000000
-2147483648

3.Division and remainder

Dividing two integers drops the fraction: 7 / 2 is 3, and -7 / 2 is -3 (it rounds towards zero). To get a decimal, make one side a double: 7 / 2.0 is 3.5.

The remainder operator % keeps the sign of the left side: -7 % 3 is -1, not 2. When you need a result between 0 and k−1 (for example a circular index), use ((x % k) + k) % k or Math.floorMod(x, k).

public class Main {
    public static void main(String[] args) {
        System.out.println(7 / 2);                 // 3
        System.out.println(-7 / 2);                // -3
        System.out.println(7 / 2.0);               // 3.5
        System.out.println(-7 % 3);                // -1
        System.out.println(Math.floorMod(-7, 3));  // 2
    }
}

3
-3
3.5
-1
2

4.Loops you'll write a thousand times

Use an index loop when you need the position (for (int i = 0; i < n; i++)), and a for-each loop when you only need the values (for (int x : nums)). A while loop fits when the next step depends on a condition, as with two pointers moving towards each other.

Most bugs in this course are "off by one": a loop that runs one time too many or too few. Before running code, check the first and last iteration by hand: what are i and the indexes used when the loop starts and just before it stops?