-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathelectionsWinners.R
executable file
·115 lines (107 loc) · 3.1 KB
/
electionsWinners.R
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
# Elections are in progress!
#
# Given an array of the numbers of votes given to each of the candidates so far,
# and an integer k equal to the number of voters who haven't cast their vote
# yet, find the number of candidates who still have a chance to win the
# election.
#
# The winner of the election must secure strictly more votes than any other
# candidate. If two or more candidates receive the same (maximum) number of
# votes, assume there is no winner at all.
#
# Example
#
# For votes = [2, 3, 5, 2] and k = 3, the output should be
# electionsWinners(votes, k) = 2.
#
# The first candidate got 2 votes. Even if all of the remaining 3 candidates
# vote for him, he will still have only 5 votes, i.e. the same number as the
# third candidate, so there will be no winner. The second candidate can win if
# all the remaining candidates vote for him (3 + 3 = 6 > 5). The third candidate
# can win even if none of the remaining candidates vote for him. For example, if
# each of the remaining voters cast their votes for each of his opponents, he
# will still be the winner (the votes array will thus be [3, 4, 5, 3]). The last
# candidate can't win no matter what (for the same reason as the first
# candidate).
#
# Thus, only 2 candidates can win (the second and the third), which is the
# answer.
#
# Input/Output
#
# [execution time limit] 5 seconds (r)
#
# [input] array.integer votes
#
# A non-empty array of non-negative integers. Its ith element denotes the number
# of votes cast for the ith candidate.
#
# Guaranteed constraints: 4 ≤ votes.length ≤ 105, 0 ≤ votes[i] ≤ 104.
#
# [input] integer k
#
# The number of voters who haven't cast their vote yet.
#
# Guaranteed constraints: 0 ≤ k ≤ 105.
#
# [output] integer
# votes <- list(2,3,5,2)
# k = 3
#
# votes <- list(1, 3, 3, 1, 1)
# k = 0
#
# votes <- list(5, 1, 3, 4, 1)
# k = 0
#
# votes <- list(1,1,1,1)
# k = 1
#Attempt for speed2: gauge based on initial condition + vectorize.
#Loop was slowing things.
library(data.table)
electionsWinners <- function(votes, k) {
votes <- unlist(votes)
if (k == 0) {
if (length(which(votes == max(votes))) == 1) {
return(1)
} else {
return(0)
}
}
diffFromMax <- votes - max(votes)
return(sum((diffFromMax + k) > 0))
}
#Attempt for speed1: Changed from lapply to for, & Added k = 0 case.
#Still test 12 failing.
# library(data.table)
# electionsWinners <- function(votes, k) {
# votes <- unlist(votes)
#
# if (k == 0) {
# if (length(which(votes == max(votes))) == 1) {
# return(1)
# } else {
# return(0)
# }
# }
# PotentialWinners = 0;
# for (x in seq(1:length(votes))) {
# if (all(votes[-x] < (votes[x] + k))) {
# PotentialWinners <- PotentialWinners + 1;
# }
# }
# return(PotentialWinners)
# }
# #failing last test for execution time
# library(data.table)
# electionsWinners <- function(votes, k) {
# votes <- unlist(votes)
# PotentialWinners <- lapply(seq(1:length(votes)), function(x) {
# if (all(votes[-x] < (votes[x] + k))) {
# return(1)
# } else {
# return(0)
# }
# })
# return(sum(unlist(PotentialWinners)))
# }