Skip to content

Instantly share code, notes, and snippets.

@Dogacel
Last active December 14, 2017 18:25
Show Gist options
  • Save Dogacel/9e4b298f3291a15ce382fae428c3f39c to your computer and use it in GitHub Desktop.
Save Dogacel/9e4b298f3291a15ce382fae428c3f39c to your computer and use it in GitHub Desktop.
integer sums equal .... in linear time
import java.util.Random;
public class LinearSums {
public static void print(int i) {System.out.println(i);}
public static void print(String s) {System.out.println(s);}
public static void main(String[] args) {
Random rn = new Random();
final int ARR_SIZE = 30;
final int NUM_MAX = 20;
final int DESIRED_NUM = 10;
// Randomly generates an array with possible numbers 0 to NUM_MAX with the size of ARR_SIZE
int[] arr = new int[ARR_SIZE];
for (int i = 0 ; i < ARR_SIZE ; i++) {
arr[i] = rn.nextInt(NUM_MAX);
}
//If DESIRED_NUM is less than ARR_SIZE code won't work.
if (DESIRED_NUM < ARR_SIZE) {
for (int i = 0; i < ARR_SIZE; i++) {
// For every number less than DESIRED_NUM, we add that number NUM_MAX.
// So if arr[i] / NUM_MAX > 0 this means number i exists.
// When we access the arr[i] we mod it in NUM_MAX because the value will be allways less than NUM_MAX
if (DESIRED_NUM - arr[i] % NUM_MAX >= 0)
arr[arr[i] % NUM_MAX] += NUM_MAX;
}
for (int i = 0; i <= DESIRED_NUM; i++) {
// Checks if we have number i and desired_num - i
if (arr[i] / NUM_MAX > 0 && arr[DESIRED_NUM - i] / NUM_MAX > 0)
System.out.println(i + ", " + (DESIRED_NUM - i));
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment