I solve similar problems for selection for an internship at Yandex, I think I solved the problem, but it gives out WA (Wrong Answer)

Conditions: 1. The amount of various

Time limit 2 seconds

Memory limit 256Mb

Input standard input or input.txt

Output standard output or output.txt

You need to send the source code of the program that solves the task.

Given an array a of n integers. Write a program that displays the sum of the various numbers in the array.

Input format

The first line of the input contains the number n (1 ≤ n ≤ 100 000). The second line contains n integers ai (0 ≤ ai ≤ 1 000 000 000).

Output format

Print the single number s, the sum of the various numbers in the array a. Be careful in choosing which integer data type to use.

Example 1

Input
3

3 5 4

Conclusion

12

Example 2

Input
five

5 5 5 5 5

Conclusion

five

Example 3

Input
ten

7 10 3 2 7 4 8 5 9 10

Conclusion

48

My code is:

import Foundation var arrayCount: Int? = Int(readLine() ?? "0") var arrayOfElements: [Int] = [] for _ in 0...(arrayCount ?? 0) { let element: Int? = Int(readLine() ?? "") arrayOfElements.append(element ?? 0) } var setOfElements: Set = Set(arrayOfElements) print(setOfElements.reduce(0, +))
  • You have a basic mistake in that you are reading elements not from one line but each element from a new line. In addition, you have a cycle from 0 to the number of elements and you read 1 more elements than you need. - coder675

4 answers 4

Looking at the condition of the problem and examples of input / output, it seems that the task was copied from some task book for C and did not bother to adapt to Swift. Therefore, based on examples.

The first remark is to ignore n (the number of elements in the array, since it is not given), and the numbers entered are a string.

The second is to ignore incorrect input. Therefore, the entered array is read as follows:

 let inputArray = readLine()!.split(separator: " ").compactMap({ Int($0) })

Well, a complete, simple solution would be:

 let outputValue: Int = Set(readLine()!.split(separator: " ").compactMap({ Int($0) })).reduce(0, +)

The bottleneck in memory is here:

 .split(separator: " ").compactMap({ Int($0) })

If it does not pass through memory, you must first optimize here, then look at what problems may exist on the input data.

  • The number of items given in the condition. - Son'ka V
  • @ Son'kaV, in the edited question really now is. Before that, when I answered, there was 1 line for each example :) - VAndrJ

Decision

 import Foundation let countOfElementsInArray: String? = readLine() // Записываю количество элементов в следующий строке let sringWithElements: String? = readLine() // Сама строка с элементами let outputValue = Set(sringWithElements!.split(separator: " ")).compactMap( { Int($0) } ).reduce(0, +) print(outputValue)

By the time it turned out: 201ms

From memory it turned out: 29.13Mb

Thanks for the help - Victor Mishustin, MBo, VAndrJ.

  • Sorry, you thanked the authors of the other answers, but none of the answers were accepted as correct. They really did not help with the decision? - 0xdb
  • They helped, their code did not pass the tests, but the logic of the decision was correct, I brushed the code a little, he passed the tests, so I thanked them, but did not mark their answers as correct. - Arthur Bodrov

You can try to solve through the indexing of elements, solved in 3 passes, but in general, the speed is O (n), the only thing I do not know is there enough memory. But you can try.

 func doubleSum(baseArray: [Int]) -> Int { let max = baseArray.max()! var ks = Array(repeating: 0, count: max + 1) baseArray.forEach { element in ks[element] += 1 } var result = 0 for index in baseArray.indices { if ks[baseArray[index]] > 0 { result += baseArray[index] ks[baseArray[index]] = 0 } } return result }

    Limitations 0 ≤ ai ≤ 1 000 000 000 and a Ограничение памяти 256Mb tell us that you can meet the memory limit using the simplest dictionary - an array of bytes or integers, in which the presence of each value corresponds to one bit , this will take 128 megabytes. Using a full dictionary will be slower.

    At the same time, the input data need not be added somewhere, if there is a possibility to read one input value after another (although reading into an array of a predetermined length should be fast enough)

    The result should be 64-bit, i.e. in a 32-bit system, the answer does not fit into Int.

    Pseudocode:

     bits = array[128000000] of Byte для каждого значения value: addr = value / 8 mask = 1 << (value % 8) if (bits[addr] && mask) == 0: //если бит ещё не установлен sum += value bits[addr] |= mask //установить его