等価配列を得るための無制限の変更

Question

最初は明確にするため、これは宿題ではありません。私は最近のインタビューでこの質問を受け、空白を描きました。 だから、

{1, 6, 3, 2, 9} 

変化が1で任意の要素をインクリメント等とすることができる。1.したがって1つの変化によって他の要素をデクリメントするステップ、私は「

{2, 5, 3, 2, 9} 

は、以下の配列でありましmがIが等しい要素の最大数を得るまで、したがって、所与のアレイは複数の変更がそれ以上ELEを取得することはできません。この点を超える

{3, 3, 3, 3, 7} or {3, 4, 4, 4, 4} 

になる可能性があり、無制限のような変更を行うことが許さ等しい。したがって、問題は無制限の変更を行い、等しいとすることができる要素の最大数は何ですか？ したがって、上記の配列の答えは4です。したがって

{2, 2, 2} 

を取得する

{1, 4, 1} 

その場合では、変更を加えることができ、別の例は、配列になり （答えは4ですが、2例は、いずれの場合も、ある注）この場合の答えは3です。 誰かが始めるためのアプローチを手伝うことができますか？私はまだ空白を描いている。

Answer 1

これはコンピュータ関連の問題ではなく、数学的な問題のようです。すべての「変更」は1つの要素をインクリメントし、別の要素をデクリメントするため、配列内のすべての値の合計は一定です。

これは、すべての要素の合計をnで均等に分けることができる場合にのみ、配列のすべての要素が同じになることを意味します。さもなければ、要素の1つはn-1を等しい要素にするために別の値をとる必要があります。

ところで、回答{3, 3, 3, 3, 7}と{3, 4, 4, 4, 4}（合計19）は、前の状態の解決策ではない{1, 6, 3, 2, 9}（合計21）です。