Минимальная уникальная сумма массива

Ответ 1

Ваш алгоритм будет терпеть неудачу в случаях с более повторяющимися значениями, например

2, 2, 2

Вы получите 7 вместо 9.

Минимальное исправление, использующее ваш алгоритм, будет:

static int minUniqueSum(int[] A) {
    int n = A.length;

    int sum = A[0];
    int prev = A[0];

    for( int i = 1; i < n; i++ ) {
        int curr = A[i];

        if( prev >= curr ) {
            curr = prev+1;
        }
        sum += curr;
        prev = curr;
    }

    return sum;
}

* Как указано в комментариях, нет необходимости сортировать уже отсортированный массив.

Ответ 2

Мне так понравилось, без сортировки.

    // Complete the getMinimumUniqueSum function below.
static int getMinimumUniqueSum(int[] arr) {

 int sum = 0;

 ArrayList < Integer > arrayList = new ArrayList < Integer > (arr.length);

 arrayList.add(arr[0]);


 for (int i = 1; i < arr.length; i++) {

  int val = arr[i];

  while (arrayList.contains(val)) {

   val++;
  }

  arrayList.add(val);

 }



 for (int i = 0; i < arrayList.size(); i++) {
  sum += arrayList.get(i);
 }

 return sum;
}

И это прошло все (13) тестовых случаев.

Ответ 3

Хотя это решение основано на Java, мыслительный процесс может применяться везде.

Ваше решение почти правильное и оптимизированное. Использование множественных циклов for замедлит работу LOT, и поэтому, по возможности, его следует избегать! Поскольку ваш массив уже предварительно отсортирован, вам достаточно с циклом 1 for.

Ваше предположение, что вы ошиблись в последнем тестовом примере, похоже, неверно, поскольку приращение означает, что вы можете делать только +1 (и действительно, большинство вопросов ограничивают это назначение только приращениями).

То, что вы пропустили, был максимальный диапазон целых чисел.

Если они передают Integer.MAX_VALUE, ваша сумма будет переполнена и будет отрицательной. Таким образом, ваша переменная суммы должна быть большего типа. double или BigInteger должны работать (лучше будет BigInteger).

Также, когда они дважды передают MAX_VALUE, ваш курс +1 также будет переполнен и станет отрицательным. Таким образом, вы хотите, чтобы ваш curr и prev также были более крупного типа. долго надо делать для этого.

 public static double calculateMinSumSorted(int[] input){
    double sum = input[0];

    long prev = input[0];
    long cur;

    for(int i = 1 ; i < input.length ; i++){
        cur = input[i];
        if(cur <= prev){
            cur = ++prev;
        }
        prev = cur;
        sum += cur;
    }
    return sum;
}

Вот некоторые из тестовых случаев, которые я использовал:

@Test
public void testSimpleArray(){
    double test1 = muas.calculateMinSumSorted(new int[]{1,2,3,4});
    Assert.assertEquals(10, test1, 0.1);

}
@Test
public void testBeginningSameValues(){
    double test1 = muas.calculateMinSumSorted(new int[]{2,2,3,4});
    Assert.assertEquals(14, test1, 0.1);
}
@Test
public void testEndingSameValues(){
    double test1 = muas.calculateMinSumSorted(new int[]{1,2,4,4});
    Assert.assertEquals(12, test1, 0.1);
}
@Test
public void testAllSameValues(){
    double test1 = muas.calculateMinSumSorted(new int[]{1,1,1,1});
    Assert.assertEquals(10, test1, 0.1);
}

@Test
public void testOverMaxIntResult(){
    double test1 = muas.calculateMinSumSorted(new int[]{1,2,3,3,4,4,4,4,4,Integer.MAX_VALUE});
    System.out.println(test1);
    Assert.assertEquals(2147483692.0, test1, 0.1);
}

@Test
public void testDoubleMaxIntArray(){
    double test1 = muas.calculateMinSumSorted(new int[]{2,2,3,4,5,6,7,8,9, Integer.MAX_VALUE, Integer.MAX_VALUE});
    Assert.assertEquals(4294967349.0, test1, 0.1);
}

@Test
public void testDoubleMinIntArray(){
    double test1 = muas.calculateMinSumSorted(new int[]{Integer.MIN_VALUE, Integer.MIN_VALUE,2,2,3,4,5,6,7,8,9});
    Assert.assertEquals(-4294967241.0, test1, 0.1);
}

Ответ 4

Вам разрешено добавлять отрицательные значения к любому из входов, тогда минимум - это просто N-е треугольное число, где N - количество элементов в массиве. (Я предполагаю, что мы имеем дело только с положительными числами для скорректированного массива, так как мы могли бы сделать его произвольно малым (отрицательным) в противном случае.

Итак, вы алгоритм - это просто поиск пары последовательных значений, которые являются одинаковыми. Если не найдено, возвращаем сумму else N * (N + 1) / 2.

Если вместо этого верно, что можно отрегулировать только повторяющиеся элементы, то подход заключается в поиске дыр между последовательными элементами и заполнении их ранее "поставленными в очередь" значениями. Фактические значения "поставленных в очередь" элементов не имеют значения, и необходим только счетчик. Ниже приведено решение С#, где я предполагаю, что корректировки элементов должны быть положительными. Это означает, что мы не можем вернуться назад и заполнить неиспользуемые отверстия, что упростит проблему.

int F()
{
    int[] a = {2, 2, 2, 3, 8, 9}; // sorted list

    int n = 0; /* num */   int p = 0; /* prev; zero is an invalid value in the list */
    int q = 0; /* queue */ int s = 0; /* sum */

    for (int i = 1; i < a.Length; i++)
    {
        n = a[i];
        if (n == p)
            q++; // increment queue on duplicate number
        else
        {
            // for every hole between array values, decrement queue and add to the sum
            for (int j = 1; q > 0 && j < n - p; j++, q--)
                s += p + j;
            s += (p = n);
        }
    }
    // flush the queue
    for (; q > 0; q--)
        s += ++n;

    return s;
}

Пример {1, 2, 4, 4, 7, 7, 8} предполагает, что предыдущее предположение неверно. Поэтому я пошел вперед и написал версию, которая использует очередь для хранения пропущенных отверстий для последующего заполнения. Это не так уж больно, и это очень похоже на структуру, но это может быть слишком много для большинства интервью.

using System.Collections.Generic;
int F2()
{
    int[] a = {1, 1, 8, 8, 8, 8, 8}; // sorted list

    int n = 0; /* num */   int p = 0; // prev; zero is an invalid value in the list
    int q = 0; /* queue */ int s = 0; // sum
    Queue<int> h = new Queue<int>(); // holes

    for (int i = 1; i < a.Length; i++)
    {
        n = a[i];
        if (n == p)
            q++; // increment queue on duplicate number
        else
        {
            for (int j = 1; j < n - p; j++)
                if (h.Count <= q + a.Length - i) // optimization
                    h.Enqueue(p + j);
            s += (p = n);
        }
    }
    // flush the queue
    for (; q > 0; q--)
        s += h.Count > 0 ? h.Dequeue() : ++n;

    return s;
}

Попробуйте оба из них: http://rextester.com/APO79723

Ответ 5

int a[] = {1,2,2,3,5,6,6,6,6 }; So what would be elements in array for sum
As per above problem statement it would be {1,2,3,4,5,6,7,8,9 }

Solution
public static void uniqueSum(){
        int a[] = {1,2,2,3,5,6,6,6,6 };
        int n = a.length;
        int sum = a[0];
        int prv=a[0];
        for(int i=1; i<n;i++){
            int cur = a[i];
            if(cur==prv){
                cur = cur+1;
                sum+= cur;
                System.out.print("--"+cur);
            }else{
                if(cur<prv){
                    cur = prv +1;
                }
                sum += cur;
            }
            prv = cur;
        }
        System.out.println("===================== "+sum);
    }

Ответ 6

Вы можете попробовать приведенный ниже код.

int a[] = {1, 1 , 1};
ArrayList<Integer> arr = new ArrayList<Integer>();
HashMap hash = new HashMap();
for(int i=0;i<a.length;i++){
    arr.add(a[i]);
}
int sum = 0;
hash.put(0, arr.get(0));
sum = (int) hash.get(0);
for(int i=1;i<arr.size();i++){
    for(int j=1;j<=a.length;j++){
        if(hash.containsValue((arr.get(i)))){
            arr.set(i, arr.get(i)+1);
        }else{
            hash.put(i, arr.get(i));
            sum += (int) hash.get(i);
            break;
        }
    }
}

System.out.println(sum);

PS: Даже я получил этот вопрос в своем интервью, приведенный выше код прошел все тестовые примеры.

Ответ 7

public static int minSum (int arr []) {

    for(int i=0; i<arr.length-1;i++){

        if(arr[i]==arr[i+1]){

            arr[i+1]= arr[i+1]+1;
        }
    }

    int sum=0;

    for(int i=0; i<arr.length;i++){

        sum=sum+arr[i];
    }

    System.out.println("sum: "+sum);
    return sum;
}

Ответ 8

Судя по описанию скрытого ввода/вывода, это, вероятно, вопрос теста HackerRank. Лучший способ сформулировать проблему: "Учитывая отсортированный массив чисел, выделите числа, увеличивая их (num++ за раз) таким образом, чтобы сумма массива была минимизирована".

Проблема допускает только увеличение, то есть увеличение числа на 1 за раз. Это также гарантирует, что массив всегда остается отсортированным. Итак, {1, 2, 4, 4, 7, 7, 8} → {1, 2, 4, 5, 7, 8, 9}

Вот проблема с решением. https://www.geeksforgeeks.org/making-elements-distinct-sorted-array-minimum-increments/

Ответ 9

Рабочий раствор (JAVA 7):

public static int getMinimumUniqueSum(List <Integer> arr){
    int sum = 0, val = 0;
    ArrayList < Integer > arrayList = new ArrayList < Integer > (arr.size());
    arrayList.add(arr.get(0));
    for (int i = 1; i < arr.size(); i++) {
        val = arr.get(i);
        while (arrayList.contains(val)) {
            val++;
        }
        arrayList.add(val);    
    }
    for (int i = 0; i < arrayList.size(); i++) {
        sum += arrayList.get(i);
    }
    return sum;
}

Ответ 10

В JavaScript

var list = [1, 1, 1, 10, 3, 2];

function minUniqueSum(arr) {
  const temp = arr.reduce((acc, cur) => {
    while (acc.includes(cur)) cur++;
    acc.push(cur);
    return acc;
  }, []);
  console.log(temp); // [1, 2, 3, 10, 4, 5]
  return temp.reduce((acc, cur) => acc + cur, 0);
}

var result = minUniqueSum(list);
console.log(result); // 25

Ответ 11

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

/* No sorting required. Works even with random list */
public static int getMinUniqueSum(List<Integer> list)
    {
        Set<Integer> set = new HashSet<Integer>();

        int sum = 0;

        for (Integer val : list) 
        {
            if(!set.add(val))
            {
                while(true)
                {
                    Integer temp = val + 1;
                    if(set.add(temp))
                    {
                        sum = sum + temp;
                        break;
                    }
                }
            }
            else
            {
                sum = sum + val;
            }
        }

        return sum;
    }

    public static void main(String[] args) 
    {
        Scanner s = new Scanner(System.in);

        System.out.println("Enter size of the list");

        int n = s.nextInt();

        List<Integer> list = new ArrayList<Integer>(n);

        System.out.println("Enter " + n + " elements of the list");

        for(int i = 0; i < n; i++)
            list.add(s.nextInt());

        s.close();

        System.out.println("MinUniqueSum = " + getMinUniqueSum(list));

    }
}

Ответ 12

Использование коллекций в Java очень помогает, здесь я использую HashMap, поскольку он хранит значения для каждого уникального ключа

Мой ключ в hashmap - это элементы массива, а значение - нет. отсчетов, как это появляется в массиве.

package uniquesum;
import java.util.*;
public class Uniquesum {
static HashMap<Integer, Integer> hp = new HashMap<Integer, Integer>();
    static int Sum(int arr[]){
        int sum=0;
        Arrays.sort(arr);
        hp.put(arr[0], 1);
        for(int i=1; i<arr.length; i++){
            if(hp.containsKey(arr[i])){

                Integer val = hp.get(arr[i]);
                hp.put(arr[i], val+1);
                hp.put(arr[i]+val, 1);                
            }
            else{
                hp.put(arr[i], 1);
            }
        }

        for(Map.Entry m:hp.entrySet()){
            sum = sum + (int)m.getKey();
        }
        return sum;
    }
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int arr[] = new int [n];
        for(int i=0; i<n;i++){

        arr[i] = scan.nextInt();
        }

        System.out.println("Sum is " + Sum(arr));


    }

}

Ответ 13

Я пробовал это в С#, и это кажется правильным в соответствии с тестовыми примерами, которые я пробовал.

static int getMinimumUniqueSum(int[] s)
{
    List<int> sa = new List<int>(s);
    sa.Sort();

    for (int i = 1; i < sa.Count(); i++)
    {
        if (sa.ElementAt(i) == sa.ElementAt(i - 1))
        {
            int p = sa.ElementAt(i);
            sa.RemoveAt(i);
            sa.Insert(i, p + 1);
            sa.Sort();
            i--;
        }
    }

    return sa.Sum();
}