Problem Statement
The city of Byteland has plans to give the city a new skyline by building n new skyscrapers in a row. The skyscrapers will be numbered 0 through n-1 from left to right. The height of skyscraper i will be h[i]. It is guaranteed that all the heights are distinct.
The height profile of a skyline is a sequence of integers that is produced by writing down the numbers of the skyscrapers in the order of their height, starting from the tallest one. For example, if the heights of the skyscrapers were {50,20,10,40,30}, the height profile would be {0,3,4,1,2}: skyscraper 0 is the tallest one, skyscraper 3 is the second tallest, and so on.
Unfortunately, due to some budget constraints, Byteland can only afford to build n-1 of the planned n skyscrapers. A committee is going to choose which one of the n skyscrapers they won't build. The remaining n-1 skyscrapers will then receive new numbers: 0 through n-2, again going from left to right.
Different choices by the committee may lead to skylines with different height profiles. Compute and return the number of distinct height profiles that can be produced.
Definition
- Class:
- RelativeHeights
- Method:
- countWays
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int countWays(int[] h)
- (be sure your method is public)
Constraints
- h will contain between 2 and 50 elements, inclusive.
- Each element of h will be between 1 and 1,000, inclusive.
- Elements of h will be distinct.
Examples
{1,3,6,10,15,21}
Returns: 1
The committee can choose one of six different skylines: {3,5,10,15,21} {1,5,10,15,21} {1,3,10,15,21} {1,3,5,15,21} {1,3,5,10,21} {1,3,5,10,15} However, all of these skylines have the same height profile: {4,3,2,1,0}.
{4,2,1,3}
Returns: 3
Here, the committee can choose one of four possible skylines: {2,1,3}, {4,1,3}, {4,2,3}, or {4,2,1}. The height profiles of these skylines are {2,0,1}, {0,2,1}, {0,2,1}, and {0,1,2}, respectively. As the second and the third skyline share the same height profile, there are only three distinct height profiles.
{6,2,352,43,5,44}
Returns: 6
{4,5,6,1,2,3}
Returns: 2
{10,9,7,5,3,1,8,6,4,2}
Returns: 9
{12,47,69,7,64,18,27,36,58,59,5,33,65,22,57,51,38,32,41,62,43,17,68,53,11,10,8,1,67,15,30,3,61,55,29,63,49,46,19,25}
Returns: 37
{481,53,22,440,637,309,650,90,61,566,609,238,455,596,418,38,109,200,187,81,269,468,511,578,371,348,625,9,318,379,124,169,250,279,498,158,401,291,525,335,223,540,138,553}
Returns: 42
{715,248,479}
Returns: 2
{32,56,48,58,41,10,11,54,6,60,42,8,31,15,52,40,21,45,55,27,38,14,18,20,59,46,3,30,23,50,4,37,49,39,9,35,51,2,43,25,29}
Returns: 39
{141,40,77,364,95,380,353,306,197,70,249,21,170,371,154,243,289,64,38,331,160,346,123,183,324,282,204,54,165,231,260,220,147,188,84,17,177,268,116,133,299,34,275,316,237,339,105,212,8}
Returns: 49
{566,163,405,391,578,469,379,339,78,320,30,453,200,418,506,262,134,303,38,48,430,14,518,215,492,291,116,241,612,554,353,185,149,225,95,598,532,629,276,65,174}
Returns: 39
{65,180,187,131,16,25,156,146,88,20,42,100,31,51,196,161,80,70,137,106,171,112,123,7}
Returns: 20
{510,556,886,781,349,397,117,937,290,448,61,608,730,228,665,178,832}
Returns: 15
{670,730,213,379,633,442,760,362,693,615,107,301,328,66,501,236,549,750,167,21,568,809,649,710,476,84,197,826,278,45,143,344,460,524,782,248,587,421,397,122}
Returns: 38
{370,253,202,268,165,86,361,126,223,408,173,138,285,74,295,347,308,44,239,57,422,320,433,28,388,214,450,95,12,459,336,112,187,150,469}
Returns: 35
{485,234}
Returns: 1
{501,198,407,231,525,451,78,182,539,419,151,276,299,390,287,112,12,438,555,487,132,32,47,376,337,514,582,359,212,247,462,569,64,313,472,261,95,168}
Returns: 37
{105,206,148,56}
Returns: 3
{349,305,152,596,100,451,21,635,410,204,277,229,74,371,327,128,520,573,433,256,187,57,473,45,658,498,616,552}
Returns: 28
{461,699,234,142,348,788,589,315,489,519,730,618,380,904,764,80,822,27,267,52,295,939,410,553,171,655,440,105,202,874,849}
Returns: 29
{92,156,129,45,174,116,24,66}
Returns: 7
{273,393,308,233,353,497,197,462,162,63,100,36,129,426}
Returns: 13
{279,218,5,134,139,11,213,70,17,174,287,198,98,153,255,204,63,192,262,22,56,108,227,76,236,33,142,122,113,86,41,244,162,298,303,188,270,309}
Returns: 35
{659,623,484,60,690,427,216,83,152,675,185,236,326,310,135,41,22,112,538,440,347,97,604,519,254,463,590,380,268,12,201,501,394,414,551,642,368,576,72,168,293}
Returns: 38
{708,520,172,365}
Returns: 2
{11,62,27,49}
Returns: 3
{66,164,544,453,368,267,27,347,477,209,191,281,423,116,224,249,96,436,306,143,82,326,385,517,409,494,295,49}
Returns: 26
{214,144,170,97,203,15,51,104,115,66,223,263,252,242,236,156,85,183,131,36}
Returns: 16
{147,212,406,651,230,311,689,861,429,561,754,57,274,451,727,828,363,594,126,791,504,90,522,667,111,343,170,610,538,15,253,37,190,809,847,580,70,333,632,493,878,892,707,463,391,293,474,767}
Returns: 47
{391,824}
Returns: 1
{4, 2, 1, 3 }
Returns: 3
{4, 5, 6, 1, 2, 3 }
Returns: 2
{1, 3, 6, 10, 15, 21 }
Returns: 1
{6, 2, 352, 43, 5, 44 }
Returns: 6