Repository navigation
Expand file tree
/
Copy pathIceCreamParlor.java
More file actions
123 lines (94 loc) · 1.92 KB
/
Copy pathIceCreamParlor.java
File metadata and controls
123 lines (94 loc) · 1.92 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
import java.util.Scanner;
public class IceCreamParlor
{
public static void main(String[] args)
{
// Scanner in = new Scanner(System.in);
// int tests = in.nextInt();
//
// for(int i = 0 ; i < tests; i++)
// {
// int target = in.nextInt();
// int size = in.nextInt();
//
// int[] x = new int[size];
//
// for(int j = 0; j < size; j++)
// {
// x[j] = in.nextInt();
// }
//
// solve(x, target);
// }
// int[] x = {1,2,3,4,5,6,7,8,9,10};
int[] x = {1,3,3,4,7,8};
int target = 7;
solve3(x, target);
}
// subset sum
private static void solve3(int[] x, int target)
{
}
// n^2
private static void solve2(int[] x, int target) {
for(int i = 0; i < x.length; i++)
for(int j = 0; j < x.length; j++)
if(x[i] + x[j] == target && i != j)
System.out.println((i+1) + " " + (j+1));
}
private static void solve(int[] c, int t)
{
int[] o = new int[c.length + 1];
for(int i = 0; i < c.length; i++)
{
o[i] = c[i];
}
for(int i = 0; i < c.length; i++)
{
int j = i;
while( j > 0 && c[j-1] > c[j])
{
int temp = c[j];
c[j] = c[j-1];
c[j-1]= temp;
j--;
}
}
int pt1 = 0;
int pt2 = c.length - 1;
while(pt1 < pt2)
{
int sum = c[pt1] + c[pt2];
if(sum == t)
{
int x = find(c[pt1], o) + 1;
int y = find2(c[pt2], o) + 1;
if(x < y)
System.out.println(x + " " + y);
else
System.out.println(y + " " + x);
return;
}else if(sum > t)
{
pt2--;
}
else if(sum < t)
{
pt1++;
pt2 = c.length - 1; // better way than this?
}
}
}
private static int find2(int t, int[] c) {
for(int i = c.length-1; i >= 0 ; i--)
if(c[i] == t)
return i;
return -1;
}
private static int find(int t, int[] c) {
for(int i = 0; i < c.length; i++)
if(c[i] == t)
return i;
return -1;
}
}