Last active
December 14, 2017 18:25
-
-
Save Dogacel/9e4b298f3291a15ce382fae428c3f39c to your computer and use it in GitHub Desktop.
integer sums equal .... in linear time
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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