The continuing efforts of cities to eradicate what they perceive to be a visual blight and safety hazard has resulted in billboard litigation raising complicated constitutional and statutory claims. This case is no exception. Hoping to obviate the need for constitutional adjudication, we certified a question to the Supreme Court of Arizona, which accepted the task of determining whether the sign codes before us violate relevant Arizona statutes. The Arizona Supreme Court held they do not, see Outdoor Systems, Inc. v. City of Mesa, 169 Ariz. 301, 819 P.2d 44 (Ariz.1991) (Outdoor Systems), and we therefore return to our constitutional adjudication.
This case came to us in a not surprising fashion. Outdoor Systems, Inc. (Outdoor Systems), and Whiteco Metrocom, Inc. (Whiteco), lessors of advertising space on billboards, respectively challenge the validity of sign codes enacted by the cities of Mesa and Tucson, Arizona. We must determine in these consolidated appeals whether these codes contravene the guarantees of free speech and the protections of property from confiscation without compensation embodied in the United States and Arizona Constitutions. The district judge in the Outdoor Systems litigation, Nos. 88-15804 and 88-15838, while denying Outdoor Systems’s other claims, held that Mesa’s sign code effected an unconstitutional taking. A different district judge in the Whiteco litigation, No. 89-15568, held that Tucson’s sign code was valid in all respects.
The district court had jurisdiction pursuant to 28 U.S.C. §§ 1331 and 1343(a)(3), and pendent jurisdiction over the state law claims. We have jurisdiction over these timely appeals pursuant to 28 U.S.C. § 1291. We affirm in part and reverse in part in the Outdoor Systems litigation, and we affirm in the Whiteco litigation. In a separate appeal, No. 90-15208, which we consolidate for purposes of decision, we affirm the district court’s limited award of attorneys’ fees to Whiteco.
I
Although this litigation arose in the Arizona district court, it involves separate cases, separate cities, and separate judgments.
A
Whiteco is an Indiana corporation which leases small areas of land in the City of Tucson from property owners, constructs billboards on them, and leases advertising space. The messages on Whiteco’s billboards include commercial advertising, noncommercial (including political) advertising, and public service messages.
In 1985, Tucson enacted a sign code regulating the size, location, and height of signs. The code classifies signs as either “onsite” or “offsite.” As the names suggest, an onsite sign is defined as one “located on the same premises as the use that sign identifies or advertises.” Tucson City Code § 8-15(u) (as amended 1987). An offsite sign is one not located on the same premises as the use *608advertised or identified by the sign. All billboards are considered offsite signs. On-site signs are limited in size and number according to the location of the property on which they are located. Offsite signs are permitted only in certain designated parts of the City (primarily industrial or commercial areas) and are prohibited -within certain zoning classifications. Even within the areas open to offsite signs, the code restricts the size, location, and density of these signs.
The sign code originally did not specifically protect noncommercial speech. In 1987, however, the City amended the code to include a “substitution provision,” which provides, “Any sign authorized in this chapter is allowed to contain noncommercial copy in lieu of any other copy.” Tucson City Code § 3-2. The code also requires a permit from the City before a sign can be erected and before the message on an existing sign can be changed. Although the code does not prescribe any time limit for the review of permit applications, it states that “a permit shall be issued to the applicant” if the proposed sign conforms to the requirements of the code and any other relevant laws and ordinances. Tucson City Code § 3-22(a)(l).
The code also requires nonconforming billboards — billboards erected prior to the enactment of the code and which violate the provisions of the code — to be removed under a variety of circumstances. The provision pertinent to this appeal is the “vacant-lot” provision, which prohibits billboards on any developed property and requires that “[a]ny existing billboard must be removed before a certificate of occupancy will be issued for a development on any undeveloped parcel.” Tucson City Code § 3-59(a)(5)b.
Allegedly forced to remove, without compensation from the City, more than 20 billboards because of the vacant-lot provision, and seeking to prevent further removals, Whiteeo filed its action under 42 U.S.C. § 1983 on October 17, 1986. Whiteeo sought damages and declaratory and injunctive relief, alleging that Tucson’s sign code violated Arizona statutory law, article II of the Arizona Constitution, and the First, Fifth, and Fourteenth Amendments to the United States Constitution. Both Whiteeo and Tucson. moved for summary judgment.
The district court initially held that the code violated the First Amendment by favoring commercial over noncommercial speech, but the court denied all of Whiteco’s other claims. Following the 1987 amendment to the code allowing noncommercial speech to be substituted for commercial speech, the district court reconsidered its initial ruling and held that the code as amended did not violate the First Amendment. Before issuing this ruling, the district court denied Whi-teco’s request to file an amended complaint challenging the amended sign code. Whiteeo appealed and has renewed each of its challenges to the sign code.
B.
Outdoor Systems is an Arizona corporation, which, like Whiteeo, leases small areas of land, constructs billboards on them, and then leases advertising space on the billboards. Outdoor Systems leases billboards throughout the Phoenix metropolitan area, including the City of Mesa. Like Whiteeo’s billboards, Outdoor Systems’s billboards carry commercial, noncommercial, and public service messages. Joining in Outdoor Systems’s challenge is Milton Lee, as trustee for the Danny 0. Lee Trust (Trust). The Trust owns a parcel of undeveloped land in Mesa upon which one of Outdoor Systems’s billboards is located.
Mesa’s sign code is similar in some respects to Tucson’s and different in others. Like Tucson’s, Mesa’s sign code distinguishes between onsite and offsite signs, and defines offsite signs in a similar manner. Mesa City Code § 4-4-S. Mesa’s code originally restricted and regulated offsite signs. In 1986, however, Mesa amended its code to prohibit them entirely. Mesa City Code § 4-4-4(B)(1)(d) (as amended 1988). Billboards are included within the definition of offsite signs.
Mesa’s code contains a substitution provision nearly identical to that in Tucson’s: “any non-commercial message may be substituted for the copy on any commercial sign allowed by the Sign Code.” Mesa City Code § 4-4-6(S). It also contains a provision that *609excepts all noncommercial signs from the Code’s definition of offsite signs. Mesa City Code § 4-4-5. Like Tucson’s code, Mesa’s requires obtaining a permit before any sign may be erected, altered, or relocated. Permit applications require submission of the content of the sign, and an application is to be approved if the appropriate city official determines that it “has been properly made and the sign complies with all appropriate laws and regulations of the City.” Mesa City Code § 4-4-12(d)(l). There is no time limit for action upon applications.
Mesa’s code also contains provisions governing nonconforming signs. These signs may not be altered, relocated, or replaced unless they are brought into compliance with the Code. Mesa City Code § 4-4-10(0(3). In addition, section 4-4-10(0(4) of the code, similar to Tucson’s vacant-lot provision, provides, “Any construction permit which invokes Certficiate of Occupancy requirements shall specify and require that any nonconforming sign located within the boundaries of the development site authorized by said permit shall be brought into conformance with the provisions of this Code.”
Subsequent to the 1986 amendment banning all offsite commercial signs,_ the Trust applied to the City for a building permit to construct a sports complex, replete with batting cages, trampolines, and a video arcade, on the property which supported Outdoor Systems’s billboard. The City refused to issue the permit until the billboard was removed; the City also refused to pay any compensation for the removal. Outdoor Systems and the Trust (collectively, Outdoor Systems) then filed this action under 42 U.S.C. § 1983.
They challenged Mesa’s code on grounds identical to those utilized by Whiteco. The district court in this ease, however, held that the City could not constitutionally require the removal of Outdoor Systems’s nonconforming sign as a condition for granting the building permit. The court did not explain the basis for its holding, and it rejected Outdoor Systems’s other claims. The City and Outdoor Systems cross-appealed. We consolidated their appeals with Whiteeo’s.
II
There remain essentially two issues for us to decide: (1) whether the sign codes facially violate the guarantees of free speech embodied in the United States and Arizona Constitutions; and (2) whether the codes effect an impermissible taking of property in violation of the relevant prohibitions contained in the United States and Arizona Constitutions. Whiteco additionally challenges the district court’s allowance of only a portion of the attorneys’ fees it requested.
We review a summary judgment, the manner by which both cases come to us, de novo. Federal Deposit Ins. Corp. v. O’Melveny & Meyers, 969 F.2d 744, 747 (9th Cir.1992). Like the district court, we must determine, viewing the evidence in the light most favorable to the nonmoving party, “whether there are any genuine ■ issues of material fact for trial, and whether the district court correctly applied the relevant substantive law.” Id.
III
We address first the challenges based on the First Amendment to the federal Constitution, made applicable to the states through the Fourteenth Amendment. Both Whiteco and Outdoor Systems mount two distinct First Amendment challenges to the codes. First, they argue that the sign codes are unconstitutional because they favor commercial speech over noncommercial speech. Second, they argue that the sign codes vest an impermissible amount of discretion in city officials and thereby create a dangerous potential that protected speech will be suppressed. Whiteco additionally challenges the district court’s .refusal to allow it leave to amend its complaint in order to challenge, on First Amendment grounds, Tucson’s amended sign code. Whiteco and Outdoor Systems, finally, also argue that the sign codes contravene the free speech provision in article 2, section 6 of the Arizona Constitution. We address each chállenge in turn.
A
The sign codes here burden both commercial and noncommercial speech. When we *610first heard this appeal, we were cognizant of the traditional distinction between commercial and noncommercial speech for purposes of First Amendment analysis. See Central Hudson Gas & Elec. Corp. v. Public Serv. Comm’n, 447 U.S. 557, 564, 100 S.Ct. 2343, 2350, 65 L.Ed.2d 341 (1980) (Central Hudson ). No holding by the Supreme Court has changed our analysis. Nevertheless, we are somewhat uneasy because of a recent footnote comment by the Court. City of Cincinnati v. Discovery Network, Inc., — U.S. -, - n. 11, 113 S.Ct. 1505, 1510 n. 11, 123 L.Ed.2d 99 (1993) (Discovery Network). As the comment is not a holding, gives us no specific direction, and is apparently of insufficient importance to be in the text of the opinion, we have no choice but to conclude that this commercial-noncommercial analytical distinction still exists. Furthermore, the Court’s most recent pronouncement reaffirms the differences between commercial speech and “other forms of protected expression,” confirming that burdens on commercial speech are scrutinized under an “intermediate standard of review.” Edenfield v. Fane, — U.S. -, -, 113 S.Ct. 1792, 1798, 123 L.Ed.2d 543 (1993) (Edenfield). Therefore, we will follow the Supreme Court’s example in Metromedia, Inc. v. San Diego, 453 U.S. 490, 504-05, 101 S.Ct. 2882, 2890-91, 69 L.Ed.2d 800 (1981) (plurality opinion) (Metromedia); id. at 541, 101 S.Ct. at 2910 (Stevens, J., joining parts I through IV of plurality opinion), and consider separately the effect of the codes on commercial and noncommercial speech, beginning with the former. In conducting both inquiries, we will pay particular attention to the body of case law involving billboard regulations. For as the Supreme Court often has recognized, “[e]ach method of communicating ideas is ‘a law unto itself and that law must reflect the ‘differing natures, values, abuses and dangers’ of each method.” Id. at 501, 101 S.Ct. at 2889, quoting Kovacs v. Cooper, 336 U.S. 77, 97, 69 S.Ct. 448, 459, 93 L.Ed. 513 (1949).
1.
In Central Hudson, the Supreme Court provided us our analytical framework for determining the validity of restrictions on commercial speech which, as here, concerns lawful activity and is not misleading: the regulation must (1) seek to implement a substantial governmental interest, (2) directly advance that interest, and (3) reach no further than necessary to accomplish the given objective. 447 U.S. at 563-66, 100 S.Ct. at 2350-51; see also Edenfield, — U.S. at -, 113 S.Ct. at 1798.
The Court in two subsequent opinions has discussed the meaning and scope of the last criterion. In Board of Trustees of State University v. Fox, 492 U.S. 469, 109 S.Ct. 3028, 106 L.Ed.2d 388 (1989), the Court explained that the last element of the analysis does not require that the regulation be the least-restrictive means to accomplish the government’s goal. Rather, what is required is a reasonable fit between the ends and the means, a fit “that employs not necessarily the least restrictive means, but ... a means narrowly tailored to achieve the desired objective.” Id. at 480, 109 S.Ct. at 3035. Applying this “reasonable fit” element in the context of reviewing a municipal ordinance which banned only commercial newsracks, the Supreme Court recently established that a city may not, in the interests of esthetics and safety, discriminate against commercial speech solely on the ground that it deserves less protection than noncommercial speech. Discovery Network, — U.S. at -, 113 S.Ct. at 1516.
Applying the Central Hudson test in the context of billboard regulations is not new for the Supreme Court or us. Metromedia remains the leading decision in the field, holding that a city, consistent with the Central Hudson test, may ban all offsite commercial signs, even if the city simultaneously allows onsite commercial signs. See 453 U.S. at 507-12, 101 S.Ct. at 2892-94 (plurality opinion); id. at 541, 101 S.Ct. at 2910 (Stevens, J., joining plurality in this holding); see also National Advertising Co. v. City of Orange, 861 F.2d 246, 248 (9th Cir.1988) (National Advertising) (under standards established in Metromedia and Members of the City Council v. Taxpayers for Vincent, 466 U.S. 789, 104 S.Ct. 2118, 80 L.Ed.2d 772 (1984) (Vincent), city may prohibit commercial billboards in entirety “and may also prohibit *611them except where they relate to activity on the premises on which they are located”).
Having in mind our duty to interpret a statute, if fairly possible, in a manner that renders it constitutionally valid, see Gray v. First Winthrop Corp., 989 F.2d 1564, 1567-68 (9th Cir.1993), we turn to the sign codes at issue. Both codes regulate the size and location of all signs, regardless of their messages, and both codes rely on a distinction between onsite and offsite signs. In Mesa, only onsite signs are allowed; in Tucson, both onsite and offsite signs are allowed, but offsite signs are subject to stricter restrictions.
Both codes also contain substitution clauses, allowing any sign authorized under the respective code to contain noncommercial messages in lieu of any other message. See Tucson City Code § 3-2; Mesa City Code § 4 4—6(S). Mesa’s code also contains a provision clarifying that noncommercial signs are not considered offsite signs. Mesa City Code § 4-4-5. We read these clauses as merely allowing noncommercial messages to be placed on any signs that the sign code would already allow. Thus, a business owner in Tucson or Mesa, for example, who would be allowed under the codes to erect or maintain an onsite commercial sign could instead erect or maintain a sign that contains a noncommercial message.
These codes, by including substitution clauses, fit within the increasingly exacting parameters of our free speech jurisprudence. It is obvious that the first criterion of the Central Hudson test is met: the goals of the ordinance—esthetics and safety—represent substantial governmental interests. See Vincent, 466 U.S. at 806-07, 104 S.Ct. at 2130 (“seven Justices [in Metromedia ] explicitly concluded that [city’s interest in avoiding visual clutter] was sufficient to justify a prohibition of billboards”); National Advertising, 861 F.2d at 248 (“The City may prohibit [commercial] billboards entirely in the interest of traffic safety and aesthetics.”); see also Outdoor Systems, 819 P.2d at 49 (“We do not doubt that off-site billboards pose a significant threat to public safety and the general welfare”).
As for the second criterion, a majority of Justices in Metromedia held that an ordinance banning all offsite commercial signs while allowing onsite commercial signs nonetheless directly advances the government’s interests in safety and esthetics. 453 U.S. at 508-12, 101 S.Ct. at 2893-95 (plurality opinion); id. at 541, 101 S.Ct. at 2910 (Stevens, J., joining this holding). Both sign codes at issue here regulate the noncommunicative aspects of all signs to some degree, by imposing size and location restrictions, and both codes prohibit offsite signs in certain locations. These regulations and prohibitions advance the cities’ twin goals of esthetics and safety. The exemptions that exist for onsite signs in Mesa and Tucson, and some offsite signs in Tucson, do not invalidate the codes, for it “does not follow from the fact that the [cities have] concluded that some commercial interests outweigh [their] municipal interests ... that [they] must give similar weight to all other commercial advertising.” Id. at 512, 101 S.Ct. at 2895 (plurality opinion); id. at 541, 101 S.Ct. at 2910 (Stevens, J., joining plurality on this point).
As for the last criterion, we hold that there is a reasonable fit between the sign codes and the interests they seek to achieve. Like the ordinance in Metromedia, which a majority of Justices concluded easily met this criterion, the sign codes here go “no further than necessary” in seeking to accomplish the cities’ goals. See id. at 508, 101 S.Ct. at 2893 (plurality); id. at 541, 101 S.Ct. at 2909 (Stevens, J., joining plurality on this point). Indeed, the cities have stopped short of achieving their goals because they have not banned outdoor signs entirely. See id. at 508, 101 S.Ct. at 2893.
The codes do not discriminate between commercial and noncommercial speech and thus do not run afoul of the principle enunciated in Discovery Network, — U.S. at -, 113 S.Ct. at 1516. The codes distinguish among types of commercial speech— onsite and offsite—but as between commercial and noncommercial speech the codes are neutral. Aside from onsite signs at noncommercial establishments, every sign in Mesa and Tucson can carry either a commercial or a noncommercial message. All signs, more*612over, are regulated regardless of the content of their messages. Cf. id. (no reasonable fit where city, in interest of esthetics, regulates only commercial newsracks and leaves noncommercial newsracks unchecked).
We therefore hold that the restrictions the sign codes impose on commercial speech are valid under the Central Hudson test. We turn now to the burdens imposed on noncommercial speech.
2.
The constitutional gauge for restrictions on noncommercial speech is the time, place, or manner test: the government may impose reasonable time, place, or manner restrictions that incidentally burden speech if they are (1) content neutral, (2) narrowly tailored to serve a significant governmental interest, and (3) leave open “ample alternative channels for communication of the information.” Ward v. Rock Against Racism, 491 U.S. 781, 791, 109 S.Ct. 2746, 2753, 105 L.Ed.2d 661 (1989) (Ward), quoting Clark v. Community for Creative Non-Violence, 468 U.S. 288, 293, 104 S.Ct. 3065, 3069, 82 L.Ed.2d 221 (1984); National Advertising, 861 F.2d at 248 (applying test to billboard regulations).
The sign codes are content neutral. They do not regulate noncommercial signs based on their content. Any sign that may be erected under the provisions of the code may carry any noncommercial message. Although Whiteco and Tucson argue that the codes will have the “effect of preferring” commercial speech, their arguments rest entirely on speculation. Even were the number of noncommercial signs to decrease disproportionately, the statute would not be invalid on that basis because the decrease would be the result of decisions made by individual sign owners. See Major Media of the Southeast, Inc. v. City of Raleigh, 792 F.2d 1269, 1273 (4th Cir.1986) (Major Media) (rejecting similar argument), cert. denied, 479 U.S. 1102, 107 S.Ct. 1334, 94 L.Ed.2d 185 (1987). A sign code could no more require that noncommercial messages be placed on signs than it could prohibit such messages while allowing commercial ones. The code’s constitutionality, therefore, cannot hinge on leaving unaltered the pre-code ratio of commercial to noncommercial signs. The possibility that the codes may result in an incidental decrease in noncommercial signs does not alter our conclusion that these sign codes operate with no heed for the content of noncommercial speech.
The second and third criteria warrant only brief attention. We have already held in this opinion, in the context of applying the Central Hudson test, that the sign codes are narrowly tailored to serve a significant governmental interest. Because the codes restrict noncommercial speech no more than they do commercial, that holding applies equally in this context. Lastly, neither Whiteco nor Outdoor Systems has identified any factual basis to indicate alternative means of communication will be unavailable. See Rzadkowolski v. Village of Lake Orion, 845 F.2d 653, 655 (6th Cir.1988) (rejecting argument that alternative channels of communication unavailable absent factual basis for argument); cf. Metromedia, 453 U.S. at 516, 101 S.Ct. at 2897 (parties stipulated that alternative channels not readily available). Not only are alternative channels for communication unimpaired, but the channel at issue here — outdoor signs — remains available, albeit in a regulated form. See Wheeler v. Commissioner of Highways, 822 F.2d 586, 596 (6th Cir.1987) (rejecting finding that alternative channels unavailable where signs not banned but regulated), cert. denied, 484 U.S. 1007, 108 S.Ct. 702, 98 L.Ed.2d 653 (1988); see also Frisby v. Schultz, 487 U.S. 474, 483, 108 S.Ct. 2495, 2501, 101 L.Ed.2d 420 (1988) (“limited nature of the prohibition [against picketing a residence] makes it virtually self-evident that ample alternatives remain”).
Thus, Whiteco and Outdoor Systems wrongly assert that the codes impermissibly prefer commercial over noncommercial speech. The codes do not discriminate against either category; they merely distinguish between onsite and offsite commercial speech. As such, they constitute permissible restrictions on commercial speech. Similarly the place and manner restrictions imposed on noncommercial speech are permissible.
*613B.
Whiteco and Outdoor Systems also challenge the permit application processes under both codes. They argue that these mandatory processes, which require submission of the sign’s content, vest too much discretion in city officials to determine which signs will be allowed.
As an application of the time, place, and manner restriction requirement that ordinances be narrowly tailored, “a law cannot condition the free exercise of First Amendment rights on the unbridled discretion of government officials.” Gaudiya Vaishnava Soc’y v. City and County of San Francisco, 952 F.2d 1059, 1065 (9th Cir.1990) (internal quotation omitted), cert. denied, - U.S. -, 112 S.Ct. 1951, 118 L.Ed.2d 555 (1992). In Shuttlesworth v. City of Birmingham, 394 U.S. 147, 89 S.Ct. 935, 22 L.Ed.2d 162 (1969) (Shuttlesworth), the Supreme Court reaffirmed that “a law subjecting the exercise of First Amendment freedoms to the prior restraint of a license, without narrow, objective, and definite standards to guide the licensing authority, is unconstitutional.” Id. at 150-51, 89 S.Ct. at 938. Whiteco and Outdoor Systems focus on the discretion city officials have in categorizing messages as either commercial or noncommercial. They argue that this discretion is unfettered and unguided by meaningful definitions of commercial and noncommercial speech. They also attack the codes for failing to specify a time limit within which permit applications must be processed.
Because our First Amendment jurisprudence recognizes a distinction between commercial and noncommercial speech, government officials have to place a particular message into one or the other category for purposes of regulation. The potential difficulty of that categorization in itself does not render the regulations unconstitutional. See Major Media, 792 F.2d at 1272-73 (fact that some cases might present difficult question regarding whether certain speech is commercial does not alone justify invalidating the statute).
We also disagree with the contention that the city officials’ discretion is unfettered. On the contrary, the city officials can and must rely on judicial precedent to determine what is commercial speech. See National Advertising Co. v. City and County of Denver, 912 F.2d 405, 410-11 (10th Cir.1990) (rejecting argument that city officials have unfettered discretion on grounds that officials are “bound by judicial precedent in determining what is commercial speech”). As the Fourth Circuit pointed out in a similar case, sufficient guidance in categorizing speech as commercial or noncommercial is provided by various decisions of the Supreme Court. Major Media, 792 F.2d at 1272 (citing Central Hudson, 447 U.S. at 561, 100 S.Ct. at 2348); see also Discovery Network, - U.S. at -, 113 S.Ct. at 1513 (discussing definitions of commercial speech). If the Supreme Court’s definitions of commercial and noncommercial speech do not constitute “narrow, objective, and definite standards,” Shuttlesworth, 394 U.S. at 150-51, 89 S.Ct. at 938, it is hard to imagine what would. The codes thus do not vest an impermissible amount of discretion in the city officials by allowing them to determine whether signs contain commercial or noncommercial messages.
That the codes lack a time limit for the processing of applications is not fatal. Whi-teeo and Outdoor Systems have not cited one case, nor have we found any, which suggests that the failure to specify the time period for processing permit applications renders a statute or ordinance invalid.
C.
Whiteco also challenges the district court’s refusal to allow it leave to amend its complaint to challenge Tucson’s sign code as amended. The amendment added the substitution clause discussed above, and Whiteco sought leave to challenge that clause, ostensibly, as failing to provide enough protection to noncommercial speech. Whiteco argued that even with the substitution clause, the ordinance would still have the effect of favoring commercial speech.
Whiteco sought leave to amend its complaint after Tucson had filed its answer. A plaintiff like Whiteco has the right to amend its complaint once as a matter of course before a responsive pleading is served and filed. Fed.R.Civ.P. 15(a). After that, *614however, a district court has the discretion to deny a motion to amend. Thomas-Lazear v. FBI, 851 F.2d 1202, 1206 (9th Cir.1988). We review the denial for abuse of discretion and in light of the strong public policy permitting amendment. Id.
The district court refused leave to amend because no discovery sought by Whiteco could undermine the patent facial validity of the ordinance. The court reasoned that any effect on noncommercial speech would be the result of choices of private individuals, not the code. The alternative to allowing people to choose what messages to place on billboards on their property, moreover, would surely be unconstitutional. Thus, allowing Whiteco to challenge the amended sign code on the ground urged, the court concluded, would have been futile.
The district court’s assessment follows logically from our discussion in part IIA.2., and we hold that the court acted within its discretion in denying Whiteco leave to amend. City of Los Angeles v. Preferred Communications, Inc., 476 U.S. 488, 106 S.Ct. 2034, 90 L.Ed.2d 480 (1986), relied upon by Whiteco, is not to the contrary. There the Court held that a complaint alleging a colorable First Amendment challenge should not be dismissed, where material factual disputes exist. Id. at 495-96, 106 S.Ct. at 2038-39. Here, the district court correctly concluded that the proposed attack on the amended sign code was not colorable and therefore denied Whi-teco leave to amend.
D.
Whiteco and Outdoor Systems contend finally that the ordinances must fail under article 2, section 6 of the Arizona Constitution, which they assert offers broader free speech protection than does the federal constitution. Although Whiteco and Outdoor Systems are correct in their assertion that Arizona’s free speech provision has been given greater scope than the First Amendment, see Mountain States Tel. & Tel. Co. v. Arizona Corp. Comm’n, 773 P.2d 455, 459 (Ariz.1989) (Mountain States), they are incorrect in their assertion that the sign codes violate that provision.
Article 2, section 6 of the Arizona Constitution provides: “Every person may freely speak, write, and publish on all subjects, being responsible for the abuse of that right.” Like the First Amendment, Arizona’s free speech provision allows for reasonable time, place, and manner restrictions. Mountain States, 773 P.2d at 462-63. These restrictions must be content neutral and drawn with “narrow specificity.” Id.
The Arizona courts have yet to determine whether their state constitution’s free speech provision allows a distinction between commercial and noncommercial speech. See State ex rel. Corbin v. Tolleson, 160 Ariz. 385, 389 n. 3, 773 P.2d 490, 494 n. 3 (Ariz.Ct.App.1989). But that issue is irrelevant because we will consider the sign codes as a whole, without separating for purposes of analysis the restrictions they place on commercial and those they place on noncommercial speech.
Arizona’s requirement that time, place, and manner restrictions be drawn with “narrow specificity” appears identical to the requirement under federal law that such restrictions be narrowly tailored. See Mountain States, 773 P.2d at 463. We have already concluded, in analyzing the sign codes’ effect on commercial speech, that the codes are narrowly tailored. We have also reached the same conclusion in analyzing the codes’ effect on noncommercial speech. It follows that the codes, when viewed in their entirety, are narrowly tailored, or, to use Arizona’s phrase, drawn with narrow specificity.
Whether either sign code, when viewed as a whole, is content neutral is a more difficult question. In Ward, the Supreme Court held that:
The principal inquiry in determining content neutrality ... is whether the government has adopted a regulation of speech because of disagreement with the message it conveys. The government’s purpose is the controlling consideration. A regulation that serves purposes unrelated to the content of expression is deemed neutral, even if it has an incidental effect on some speakers or messages but not others. Government regulation of expressive activity is content neutral so long as it is justified *615without reference to the content of the regulated speech.
491 U.S. at 791, 109 S.Ct. at 2753 (internal quotation and citations omitted) (emphasis in original). In Discovery Network, - U.S. at -, 113 S.Ct. at 1517, the Court emphasized that it is “the absence [or presence] of a neutral justification” that is critical to determining whether a regulation is content neutral.
The ordinances distinguish between offsite and onsite commercial speech. The ordinances also distinguish between commercial speech and noncommercial speech, insofar as the latter does not have to relate to the activities conducted on the premises supporting noncommercial signs. It is equally clear, however, that the sign codes regulate all signs and thereby burden both commercial and noncommercial speech. Cf. id. (Cincinnati’s ordinance not content neutral in part because it did not limit number of newsracks, but instead completely banned only commercial newsracks). In contrast to Cincinnati’s newsrack ordinance, whether any particular sign falls within the provisions of the- sign code is not determined by the content of the message on the sign. See id.
There are also neutral justifications for the disparate treatment of the different categories of speech. Both cities seek to ameliorate the visual blight of outdoor signs while preserving the fullest opportunity for their citizens to communicate freely. Allowing only onsite signs, or allowing them in addition to a limited number of offsite signs, serves the first goal because the overall number of signs will be limited by virtue of the limited number of properties within the cities. At the same time, allowing any noncommercial message to be substituted on an authorized sign increases the opportunity for the free expression of ideas, thus serving the second goal.
The difficult question is whether there is a neutral justification for not allowing commercial messages on any sign while allowing noncommercial messages on any sign. We believe there is. Any commercial enterprise that would be advertised offsite presumably will have its own place of operation,' where it conducts its business. Under both sign codes, that enterprise would be allowed to erect an onsite commercial sign. The same is not true regarding noncomiiiercial messages; there will not always and necessarily be a place where a sign bearing that message will be allowed. The disparate treatment is thus a permissible place restriction which helps equalize the opportunities for commercial and- noncommercial speech. .
Considered in their entirety, therefore, we hold that the sign codes are content-neutral restrictions on the place and manner of speech. As such, the codes no more violate the Arizona Constitution than they do the United States Constitution.
IV
We turn now to the arguments that the sign codes, both facially and as applied, effect an impermissible taking of private property in violation of the state and federal constitutions. Whiteco and Outdoor Systems both seek declaratory and injunctive relief, and damages for the alleged inverse condemnation of their property. They focus their challenges on those provisions in both sign codes that require nonconforming billboards on undeveloped land to be removed when the land upon which they stand is developed (collectively, the vacant-lot provisions). See Mesa City Code § 4-4-10(0(4); Tucson City Code § 3-59(a)(5)b. We begin with the chai-, lenge based on the federal constitution.
A.
The Takings Clause of the Fifth Amendment, as applied against the States via the Fourteenth Amendment, see Webb’s Fabulous Pharmacies, Inc. v. Beckwith, 449 U.S. 155, 160, 101 S.Ct. 446, 450, 66 L.Ed.2d 358 (1980), prohibits private property from being “taken for public use, without just compensation.” U.S. Const. amend. V. A zoning law effects a taking if (1) it does not substantially advance a legitimate governmental interest; or (2) it denies an owner economically viable use of his land. Agins v. City of Tiburon, 447 U.S. 255, 260, 100 S.Ct. 2138, 2141, 65 L.Ed.2d 106 (1980) (Agins) (citing Penn Cent. Transport. Co. v. New York, 438 U.S. 104, 138 n. 36, 98 S.Ct. 2646, 2666 n. 36, 57 *616L.Ed.2d 631 (1978) (Penn Central)). While no precise formula reveals when property has been taken, the determination “necessarily requires a weighing of private and public interests.” Id. 447 U.S. at 261, 100 S.Ct. at 2141.
Whiteco and Outdoor Systems concede that the cities’'interests behind the zoning regulations are legitimate. The cities certainly have a legitimate interest in eliminating nonconforming uses. See League to Save Lake Tahoe v. Crystal Enters., 685 F.2d 1142, 1145 (9th Cir.1982) (Lake Tahoe) (“Nonconforming uses represent conditions which should be reduced to conformity as quickly as is compatible with justice.”); Outdoor Systems, 819 P.2d at 51 (“elimination of nonconforming uses ... clearly effectuates a legitimate state interest” (internal quotation omitted)). The cities, as already discussed, also have a legitimate interest in eliminating or restricting billboards. See National Advertising, 861 F.2d at 248.
Whiteco and Outdoor Systems focus on the so-called “nexus requirement” enunciated in Nollan v. California Coastal Comm’n, 483 U.S. 825, 107 S.Ct. 3141, 97 L.Ed.2d 677 (1987) (Nollan). The necessity for a nexus is a subpart of the requirement that a regulation “substantially advance” a legitimate state interest. See id. at 834, 837, 841, 107 S.Ct. at 3147, 3148, 3150. The Court held in Nollan that if there is no nexus or connection between the effect of the regulation and the governmental interest sought to be achieved, the regulation does not advance the state’s interest. Id. at 837, 107 S.Ct. at 3148.
In Nollan, the state’s asserted interest was maintaining visual access to the beach for those on the street. Id. at 836, 107 S.Ct. at 3148. The regulation required the Nollans to grant a lateral easement across the beachfront behind their house. Id. at 838, 107 S.Ct. at 3149. As the Court observed, that easement obviously would not help those on the street see the beach. Id. There thus was no “nexus” between the regulation and the goals sought to be achieved by the city. Id. at 838-39, 107 S.Ct. at 3149-50.
Despite Whiteco and Outdoor Systems’s strenuous arguments to the contrary, here there is a simple and clear nexus between the vacant-lot provisions of the sign codes and the cities’ interests. The vacant-lot provisions require the removal of nonconforming billboards whenever the land on which they stand is developed. The cities’ interests, in restricting billboards and eliminating nonconforming billboards, are advanced directly by these provisions, as the number of billboards in general and nonconforming billboards in particular will be reduced by their operation.
Outdoor Systems and Whiteco err by insisting that there must be a nexus between the purposes behind the building and occupancy permits and the state interest in removing nonconforming billboards. Nollan does not require this particular nexus. All Nollan requires is that there be a nexus between the regulation — the vacant-lot provisions — and the cities’ interest. There is. The vacant-lot provisions achieve the cities’ interests by conditioning the development of land that supports a nonconforming billboard on the removal of the billboard. The building and occupancy permits, which issue when nonconforming billboards are removed, are merely the mechanisms by which the cities can achieve their legitimate purposes. These mechanisms ensure that whenever land use is changed, any nonconforming billboards on that land will be removed. We thus conclude that the sign codes, including the vacant-lot provisions, substantially advance the cities’ legitimate interests.
As for the question whether the sign codes deprive an owner of the economically viable use of his land, we recognize at the outset that the term “economically viable use” has yet to be defined with much precision. Lake Nacimiento Ranch Co. v. San Luis Obispo, 841 F.2d 872, 877 (9th Cir.1987), cert. denied, 488 U.S. 827, 109 S.Ct. 79, 102 L.Ed.2d 55 (1988). We have held, however, that “the existence of permissible uses [generally] determines whether a development restriction denies a property holder the economically viable use of its property.” Id.; see also Penn Central, 438 U.S. at 124, 98 S.Ct. at 2659 (economic impact of regulations and extent to which regulations interfere with investment-backed expectations are relevant to inquiry).
*617There are two distinct property interests involved in these appeals: a landowner’s (the Trust), and the billboard owners’ (Whiteco and Outdoor Systems). For purposes of analysis we will consider these interests separately.
The Trust, by definition, will still have an economically viable use of its land if the billboard is removed, because Mesa’s vacant-lot provision, like Tucson’s, does not apply unless the land is developed. The Trust argues that it will lose some economic value in its land because it will not be able to develop the land and keep the nonconforming billboard. However, this diminution in value, as the Trust concedes at another point in its argument, is “de minimis” and is insufficient to constitute a taking where the land may still be put to an economically viable use. See Agins, 447 U.S. at 262, 100 S.Ct. at 2142 (owners not denied economically viable use of land where ordinances limit development but neither prevent best use of land nor eliminate “fundamental attribute of ownership”); see also Penn Central, 438 U.S. at 124, 98 S.Ct. at 2659 (“economic impact of the regulation” is a relevant consideration). That the Trust exercises a choice to develop its land, moreover, indicates that the land, absent the billboard, may still be put to another, more profitable use.
The Trust argues that the decision forced upon it by the sign code is a Hobson’s choice which allows Mesa to accomplish indirectly, the removal of nonconforming billboards, what it cannot compel directly. The Trust relies for support on Frost v. Railroad Comm'n 271 U.S. 583, 46 S.Ct. 605, 70 L.Ed. 1101 (1926). In that case, the Court reaffirmed the principle that “a state is without power to impose an unconstitutional requirement as a condition for granting a privilege.” Id. at 598, 46 S.Ct. at 609. There are at least two factors which distinguish the Trust’s case.
First, the degree of compulsion in this case, if it exists at all, is minute in comparison to the forced choice facing the carriers in Frost. See id. at 593, 46 S.Ct. at 607 (observing that a carrier must either “forego a privilege which may be vital to his livelihood or submit to a requirement which may constitute an intolerable burden”). Far from a Hobson’s choice, whether to build a sports complex or retain a billboard on the Trust property, in economic terms, appears to be a fairly easy decision. That the Trust cannot do both hardly forces upon it a Hobson’s choice.
Second, and more importantly, the Trust mischaraeterizes the operation of the vacant-lot provision. This provision does not “compel” indirectly the immediate removal of nonconforming billboards; such billboards may remain for as long as a landowner desires. Even if we assume that compelling the immediate removal of nonconforming billboards would be unconstitutional, which is a question we have yet to decide, see Lake Tahoe, 685 F.2d at 1145 (recognizing the “doubtful constitutionality of compelling the immediate discontinuance of nonconforming uses”), it would not follow that the eventual elimination of nonconforming uses is also unconstitutional. For that to be true, a landowner would have to have the perpetual right to continue a nonconforming use.
We look to state law to determine “what property rights exist and who is entitled to recover for a taking.” Milens of California v. Richmond Redev. Agency, 665 F.2d 906, 909 (9th Cir.1982). Under Arizona law, a landowner has only limited rights to retain nonconforming uses. As the Arizona Supreme Court reaffirmed in Outdoor Systems, “the owner of a nonconforming use does not have a vested right to expand or change the nature of that existing use.... [T]he right to continue a nonconforming use ceases once it is put to a different use, regardless of whether the municipality offers compensation.” 819 P.2d at 51. As there is no property right under Arizona law to continue a nonconforming use once that use is altered, it cannot be an unconstitutional taking to require a nonconforming billboard to be removed once the land on which it stands changes use. See id. at 52 (defining nonconforming property as the parcel of land and the nonconforming billboard).
The Trust also argues that the Supreme Court’s recent decision in Lucas v. South Carolina Coastal Council, - U.S. -, 112 S.Ct. 2886, 120 L.Ed.2d 798 (1992), demon*618strates that the sign codes effect a per se taking. Lucas holds that a regulation that deprives a property owner of all economically beneficial or productive use of his or her land constitutes a per se taking, regardless of the governmental interest advanced by the regulation, unless the intended use is already proscribed by extant state rules. Id. at -, 112 S.Ct. at 2899-900. As stated earlier, a viable land use would remain. This holding has no relevance to these appeals.
As for Whiteco and Outdoor Systems’s property interests, these consist of leases with the landowners, including the Trust, whose land supports their billboards. While leasehold interests are considered compensable property rights under Arizona law, see Mobil Oil Corp. v. Phoenix Cent. Christian Church, 138 Ariz. 397, 399, 675 P.2d 284, 286 (Ariz.Ct.App.1983), these interests are in no way altered by the sign codes. The codes allow the billboards to remain as long as the landowner wishes. They therefore do not change the contractual rights or duties between lessor and lessee. So long as Outdoor Systems and Whiteco have enforceable leases, they should retain the right to whatever remedies state law provides in the event of a breach. Thus, the sign codes do not deprive them of any property interest.
We therefore hold that the sign codes do not facially violate the Takings Clause. Nor do they effect a taking of the Trust’s property or the leasehold interests of Whiteco or Outdoor Systems. Whiteco suggests that the conclusion that it has no takings claim should not be made on summary judgment. We recognize that the Supreme Court, “unable to develop any set formula for determining” when a taking has occurred, engages in “essentially ad hoc, factual inquiries” to make that determination. Hodel v. Virginia Surface Mining & Reclamation Ass’n, 452 U.S. 264, 295-96, 101 S.Ct. 2352, 2370, 69 L.Ed.2d 1 (1981) (internal quotations and citations omitted). Here, however, neither the district court nor we need any additional facts to determine that the ordinance, as a matter of law, does not affect the property interests of a lessee.
B.
Whiteco and Outdoor Systems also press a takings argument based on article II, section 17 of the Arizona Constitution, which states that “[n]o private property shall be taken or damaged for public or private use without just compensation.” Arizona law follows federal law in holding that neither diminution in the value of land nor deprivation of the land’s most beneficial use, standing alone, constitutes a taking of property. Ranch 57 v. City of Yuma, 152 Ariz. 218, 226, 731 P.2d 113, 121 (Ariz.Ct.App.1986) (Ranch 57). The court in Ranch 57 interpreted Arizona’s test as being consistent with the federal one. Id. at 227, 731 P.2d at 122; see also Laidlaw Waste Sys., Inc. v. Phoenix, 168 Ariz. 563, 565 n. 1, 815 P.2d 932, 934 n. 1 (Ariz.Ct.App.1991) (observing that court in Ranch 57 “harmonized the takings clauses” of the federal and state constitutions). Under Arizona law, as under federal law, a statute effects a taking if it deprives a property owner of all “economically viable” uses of his property. Ranch 57, 152 Ariz. at -, 731 P.2d at 122. As we have already held that these sign codes do not cause such a deprivation, we also hold that the sign codes do not violate article II, section 17 of the Arizona Constitution.
V
In a separate appeal that we consolidate with the others for purposes of decision, Whiteco challenges the amount of attorneys’ fees awarded by the district court. Whiteco argues that the district court abused its discretion by (1) characterizing Tucson’s amendment to its sign code as the sole benefit Whiteco received, (2) limiting recovery to work done only on the First Amendment claim that Tucson’s unamended sign code preferred commercial over non-commercial speech, and (3) denying fees to the Rubin law firm on the grounds that the hours spent by that firm were duplicative.
42 U.S.C. § 1988 authorizes district courts to award reasonable attorneys’ fees to “the prevailing party” in civil rights litigation. We review the district court’s award of fees and the amount awarded for abuse of discretion. Chalmers v. City of Los Angeles, 796 F.2d 1205, 1210 (9th Cir.1986) (Chalmers), *619amended, 808 F.2d 1373 (9th Cir.1987). Our limited review “is appropriate in view of the district court’s superior understanding of the litigation and the desirability of avoiding frequent appellate review of what essentially are factual matters.” Hensley v. Eckerhart, 461 U.S. 424, 437, 103 S.Ct. 1933, 1941, 76 L.Ed.2d 40 (1983) (Hensley).
The district court determined that Whiteco was a “prevailing party” only on the claim that Tucson’s original sign code preferred commercial over noncommercial speech. The court found that Whiteco had established this claim by March 1987, when it learned that Tucson would amend its code to include the substitution clause, thereby removing any preference the code had toward commercial speech. The code was not actually amended until July 1987. Whiteco argues that it is entitled to compensation for all the work it did prior to the district court’s order of February 1988, in which the court declared that Tucson’s original sign code unconstitutionally preferred commercial over noncommercial speech.
When calculating a reasonable fee, a district court may exclude hours for work that do not “contribute[ ] to any favorable result achieved by the litigation.” Clark v. City of Los Angeles, 803 F.2d 987, 993 (9th Cir.1986). As the Third Circuit has held, a district court has the discretion “to disallow any fees for time spent litigating the case after the last benefit won from the defendant, because the expenditure of such time is equivalent to expending time litigating particular claims that are unrelated to the relief ultimately obtained, for which Hensley directs a disallowance of fees.” Institutionalized Juveniles v. Secretary of Public Welfare, 758 F.2d 897, 920 (3d Cir.1985).
Here, the district court properly concluded that the only benefit secured by Whiteco’s litigation was the City’s decision to amend its sign code. The district court’s subsequent declaration that the original sign code was unconstitutional added nothing to the benefit provided Whiteco by Tucson’s amendment to the code. The district court also found that Whiteco secured this benefit in March 1987, when it learned that Tucson would amend its code. Whiteco has not disputed that it knew in March that the code would be amended, nor have we found anything in the record indicating otherwise. Therefore, we believe the district court did not abuse its discretion in limiting Whiteco’s recovery to work done prior to March 1987.
Whiteco also contends that the district court abused its discretion in limiting the fee award to work done on the First Amendment claim. Whiteco argues that all of its claims were interrelated and that it deserves fees for work done on its unsuccessful arguments as well as its successful one. Both parties agree that this question is governed by Hensley.
When a party, like Whiteco, is only partially successful, Hensley requires the court to determine first if the plaintiffs losing claims were related to the plaintiffs successful claims; if they were not, no fees should be awarded for work done on the losing claims. If the claims were related, the court must then evaluate the significance of the result achieved and calibrate the compensation accordingly. See Thorne v. City of El Segundo, 802 F.2d 1131, 1141 (9th Cir.1986).
The district court found that Whiteco’s First Amendment claim was unrelated to its other claims. The method for determining whether claims are related is not precise: “related claims will involve a common core of facts or will be based on related legal theories, while unrelated claims will be distinctly different and based on different facts and legal theories.” Id. (internal quotations and citation omitted). This imprecise test is particularly difficult to apply in this case, as it arises not so much from an incident or course of conduct, but instead involves, for the most part, a facial challenge to Tucson’s sign code.
Nevertheless, Whiteco’s First Amendment claim was “distinctly different” from its other claims. The other challenges brought by Whiteco are obviously distinct from its argument that the original sign code on its face preferred commercial over noncommercial speech. Those challenges rest on different legal theories, focus on different aspects of the sign codes, and rely on different facts for support. Thus, the district court did not abuse its discretion in limiting Whiteco’s re*620covery to the work done on the First Amendment claim.
Nor did the court abuse its discretion in denying fees for the work completed by the Rubin law firm. An applicant for fees “bears the burden of establishing entitlement to an award and documenting the appropriate hours expended.” Hensley, 461 U.S. at 437, 103 S.Ct. at 1941. A district court may reduce a fee award by excluding hours that are duplicative or unnecessary. Chalmers, 796 F.2d at 1210. Here, the district court ruled that the hours spent by the Rubin law firm were duplicative.
Whiteco argues that the district court had a duty to be more specific as to why it found the efforts of the Rubin firm to be duplicative. This argument misconstrues the court’s ruling. The court found that Whiteco failed to justify the involvement of the Rubin firm as necessary to its success. Simply because the Rubin firm was helpful, the court correctly pointed out, does not entitle them to an award of fees. Failing to meet its burden of establishing the Rubin firm’s entitlement to fees, Whiteco is in no position to challenge the district court’s ruling as lacking in detail.
In summary, we uphold the sign codes as consistent with both the federal and state constitutions. We therefore affirm in the Whiteco litigation, No. 89-15568; and affirm in part and reverse in part in the Outdoor Systems, Nos. 88-15804 and 88-15838. We remand the latter case to allow the district court to enter judgment in favor of Mesa. We also affirm the district court’s limited award of attorneys’ fees to Whiteco, in case No. 90-15208.