Integer Coding

memo={

def count_distance(s,pos,tight,mask, is_leading):

if pos == len(s):  
return 1 if not is_leading else 0

state =(pos,tight,mask,is_leading)

if state i memo[state]

ans=0

upper_bond = int (s[pos])if tight else 9

for digit in range(upper_bound+1):

if is_leading and digit==0:

ans+=count_distinct(s,pos+1,tight and digit == upper_bound,mask,true)

elif not (mask&(1<<digit)):

ans+= count_distinct(s,pos+1,tight and digit == upper_bound,mask | (1<< digit),false)

memo[state]=ans

return ans

def special_integers(N):

s = str(N)

return count _ distrinct(s,0,true,0,true)

Sorry late to the party but only found out about challenges now. Below my KDB/Q code. I know answers have already been published but I highly doubt anyone posted a KDB/Q solution.

// create a list of 1M random numbers between 0 and 9
q)list:1000000?10
// show that it's actually 1M numbers
q)count list
1000000
// check list
q)list
8 1 9 5 4 6 6 1 8 5 4 9 2 7 0 1 9 2 1 8 8 1 7 2 4 5 4 2 7 8 5 6 4 1 3 3 7 8 2 1 4 2 8 0 5 8 5 2 8 6 9 0 0 0 9 5 2 3 9 5 9 7 6 6 4 7 8 4 4 6 9 9 2 5 4 2 5 8 7 9 9 7 7 1 9 1 0 8 8 3 1 0 5 1 0 0 1 7 6 3 4 3 4 8 4 6 8 2 8 3 4 1 6 4 4 2 2 7 2 0..
// group numbers together. output, each distinct number and their indexes
q)group list
8| 0 8 19 20 29 37 42 45 48 66 77 87 88 103 106 108 128 135 138 147 153 157 166 199 201 211 216 254 256 281 287 290 295 306 310 319 331 339 344 354 371 375 388 391 394 396 440 464 466 470 483 486 519 534 549 584 600 601 615 623 631 641 652..
1| 1 7 15 18 21 33 39 83 85 90 93 96 111 127 129 141 142 170 181 187 190 203 206 212 221 224 228 250 255 280 283 304 309 327 351 357 377 378 400 402 424 425 431 442 443 445 455 469 477 498 510 515 517 523 524 547 553 571 572 592 593 599 62..
9| 2 11 16 50 54 58 60 70 71 79 80 84 139 143 145 156 160 161 168 180 217 239 242 272 277 291 320 326 330 332 333 342 345 347 349 352 361 363 372 376 387 392 404 426 427 436 448 471 480 492 494 500 502 505 538 568 574 581 588 604 606 610 6..
5| 3 9 25 30 44 46 55 59 73 76 92 120 122 152 169 171 205 219 220 226 229 230 236 237 246 263 266 289 297 302 316 317 325 334 366 368 379 399 407 408 414 415 418 423 447 453 462 522 526 530 531 532 562 563 570 573 578 587 591 619 629 640 6..
4| 4 10 24 26 32 40 64 67 68 74 100 102 104 110 113 114 148 151 155 176 191 194 200 223 235 243 245 251 261 264 274 275 301 322 328 335 337 348 360 381 397 409 417 430 439 452 468 476 489 501 504 535 552 558 566 611 613 614 627 635 669 676..
6| 5 6 31 49 62 63 69 98 105 112 123 134 144 163 165 193 195 197 213 238 241 247 248 253 260 262 270 292 293 296 312 353 356 365 369 386 405 422 429 437 463 467 475 481 490 491 496 509 516 533 541 557 567 577 582 585 609 616 622 625 630 63..
2| 12 17 23 27 38 41 47 56 72 75 107 115 116 118 126 136 164 173 185 186 207 208 218 222 231 234 240 265 271 273 279 285 308 364 374 383 389 390 395 401 406 413 435 451 456 460 474 479 484 488 495 506 508 514 521 527 536 537 565 569 576 59..
7| 13 22 28 36 61 65 78 81 82 97 117 121 124 131 146 175 177 178 184 188 196 227 232 233 252 259 267 268 269 276 284 298 299 305 311 314 315 321 323 324 341 343 350 355 380 385 398 410 419 420 421 434 438 441 449 457 458 459 507 513 540 54..
0| 14 43 51 52 53 86 91 94 95 119 125 130 140 150 154 158 162 167 172 179 192 202 204 209 244 249 258 286 288 300 303 313 318 336 340 358 370 373 393 411 428 432 444 446 450 454 461 478 482 487 503 528 542 543 548 556 559 561 583 594 598 6..
3| 34 35 57 89 99 101 109 132 133 137 149 159 174 182 183 189 198 210 214 215 225 257 278 282 294 307 329 338 346 359 362 367 382 384 403 412 416 433 465 472 473 485 493 497 499 511 512 518 520 525 529 539 550 554 555 560 580 595 602 612 6..
// count the number of indexes for each number
q)count each group list
8| 99761
1| 99949
9| 99788
5| 99216
4| 100449
6| 99742
2| 100472
7| 99912
0| 100455
3| 100256
// store the resulting dictionary in variable d and get the max occurrence q)max d:count each group list
100472
// compare the original dictionary with the max occurrence
q)d=max d:count each group list
8| 0
1| 0
9| 0
5| 0
4| 0
6| 0
2| 1
7| 0
0| 0
3| 0
// find the number associated to the max value
q)where d=max d:count each group list
,2
// time it. This takes 6 millisecond 
q)\ts where d=max d:count each group list
6 27272656
q)
// the whole exercise with the original file, reading from the file
q)where d=max d:count each group "I"$read0`:1M_random_numbers.txt
,142i
// takes 84 millisecond 
q)\ts where d=max d:count each group "I"$read0`:1M_random_numbers.txt
84 44584000

If you want to learn more about KDB/Q, read my blog here www.defconq.tech

pyspark can handle huge data easily. so, i used it on a google colab machine.

142 is the integer with highest number of occurrences (1130 times).

import pyspark.sql.functions as func
from pyspark.sql.types import *
from pyspark.sql.window import Window as wd

file_path = './drive/MyDrive/1M_random_numbers.txt'

# read text file as dataframe
data_sdf = spark.read.csv(file_path, schema=StructType([StructField('nums', IntegerType())]))

data_sdf. \
    groupBy('nums'). \
    agg(func.count('*').alias('cnt')). \
    withColumn('rank', func.dense_rank().over(wd.orderBy(func.desc('cnt')))). \
    filter(func.col('rank') == 1). \
    select('nums'). \
    rdd.map(lambda x: x.nums). \
    collect()

# result
# [142]

approach

• count the number of times each integer occurs using a groupBy
• dense_rank the integers based on the descending order of its number of occurrence
• filter the integer(s) with rank == 1; in case of a tie in the top rank, all integers get "1" as rank due to the use of dense_rank
• in the end, select the integer column and output the integer(s) as a list using rdd.map()

execution and machine details

• with the 1M data, it took the process 760 ms ± 22 ms per loop
• python3
• v5e-1 Google compute engine (single core TPU)
• RAM in use: 3GB

def find_most_frequent_counter(numbers):
    """
    Find the most frequent number(s) using Counter.
    Testing with 1,000,000 numbers Takes 0.0408 seconds
    """
    counter = Counter(numbers)
    max_count = max(counter.values())
    most_frequent = [num for num, count in counter.items() if count == max_count]
    return most_frequent, max_count

// Return Most Common Number in Array
// by Alexander Burton
// https://alexburton.com
// or string of numbers delimited by one of a few options
// https://stackoverflow.com/beta/challenges/79766578/code-challenge-6-integer-counting
// forgive me if this solution looks ridiculous, it was fun building it
function most_common_number(data, str_split, debug_mode = false) {
    // Declare data catchers
    let uc = {}; // unique counter - how many time each number (key) occurs (value)
    let d_numbers = []; // data array

    if(debug_mode) {console.log("Phase 0:\n", typeof data === "object", data === Array, data.length > 0);}
    // If data passed into this function is already an array,
    //then use it as-is
    if(typeof data === "object" && data.length > 0) {
        d_numbers = data;
    }
    // If data passed into this function is a string,
    // then the second argument will be used
    // to tell the function which delimeter to use
    //to split this string into array of number
    // without chaos ensuing
    if(typeof data === "string") {
        // This is the gate keeper that limits which delimeters
        // the user can use to split the string
        if(["\n", ",", " ", ";"].indexOf() > -1) {
            d_numbers = data.split(str_split);
        } else {
            // If you want to trust the user to choose
            // the correct delimiter without erroring
            // then get of the if/else this
            return {"warning": "You have chosen a delimiter that is not in my list of approved delimiters: \"\\n\", \",\", \" \", \";\""};
        }
    }

    if(debug_mode) {console.log("Phase 1:\n", {uc, d_numbers});}
    // Build the Unique Counter (uc) that creates a dictionary of
    // keys (the number that uniquely occurs in the array) and
    // values (the number of times that the unique number [the "key" itself]
    // occurs in the array)
    d_numbers.forEach((n,i) => {
        let key = (n.toString());
        key in uc ? uc[n] += 1 : uc[n] = 1;

    });

    if(debug_mode) {console.log("Phase 2:\n", {uc, d_numbers});}
    // the array of the number of times each unique number occurred
    let uc_values = Object.values(uc); // unique counter's array of value
    // the array of unique numbers that occurred in an order
    // that corresponds with the uc_values array above
    let uc_keys = Object.keys(uc);
    // the most amount of times a number has occurred in the array
    // selected by finding the largest number in the array of uc_values
    let max_num = Math.max(...uc_values);
    // the long variable name explains itself oddly enough
    // if the max_num occurs in the uc_values multiple times
    // then the index will reflect the position the first time
    // the max_num was found in the .indexOf() the uc_values array
    let index_of_number_of_times_the_number_that_occurs_most_happens = uc_values.indexOf(max_num);
    // sort the uc_keys in an order that lines up with the uc_values
    // so that the oddly named variable above can be used
    // to return the number that occurs most in the array
    uc_keys = uc_keys.sort((a,b) => {return parseInt(a) - parseInt(b);});
    // and voila parse the value selected back into an integer
    // and you have the number that occurs most in the array
    let number_that_occurs_most = parseInt(uc_keys[index_of_number_of_times_the_number_that_occurs_most_happens]);
    if(debug_mode) {console.log("Phase 3:\n", {uc_values, max_num, uc_keys, number_that_occurs_most, index_of_number_of_times_the_number_that_occurs_most_happens});}
    // return the number that actually occurs most
    // in the provided in the original data array
    return number_that_occurs_most;
}

Explanation:

- I opted for parallel execution because this is a CPU-bound operation with a high workload. This strategy allows us to divide the task into multiple chunks that run concurrently, resulting in faster completion times at the cost of increased resource utilization.

1. Parallel Frequency Counting

The first major optimization is how the code counts the numbers. Instead of using a dictionary or a single-threaded loop, it employs a highly efficient, albeit constrained, method:

• Frequency Map (int[] arr): The code pre-allocates an integer array arr of size 1000. This array acts as a direct-address table or frequency map. The index of the array corresponds to an integer from the input file (e.g., arr[42] stores the count of the number 42), and the value at that index is its frequency. This is incredibly fast because updating the count is an O(1) operation. However, it assumes all numbers in the input file are within the range of 0 to 999.

• Parallel Processing (Parallel.Invoke): To speed up the counting process on the large input list, the list is logically divided into 100 smaller segments. An array of Action delegates is created, where each Action is responsible for iterating over one segment and updating the shared arr frequency map. Parallel.Invoke then executes all these actions concurrently, utilizing multiple CPU cores to process the data much faster than a single sequential loop would.

Important Note on Thread Safety: The operation arr[integers[j]]++ is not atomic and therefore not thread-safe. It involves three steps (read the value, increment it, write it back), and a race condition can occur if two threads try to update the same counter simultaneously, potentially leading to incorrect counts. A more robust implementation would use Interlocked.Increment(ref arr[integers[j]]) to ensure thread-safe increments.

2. Parallel "Divide and Conquer" Search

Once the arr frequency map is populated, the next task is to find the index with the highest value. A simple linear scan would work, but to further optimize, the code implements a parallel "divide and conquer" algorithm:

• Recursive Splitting: The FindMaxRec method recursively splits the frequency array in half.

• Parallel Search: Parallel.Invoke is used again to run the search on both halves of the array concurrently.

• Combine Results: Once the parallel tasks complete, the method simply compares the maximum value found in the left half with the maximum from the right half and returns the greater of the two. This process continues up the recursion stack until the overall maximum for the entire array is found. This parallel search can offer a significant speedup for finding the maximum value in a large array.

Performance:

The code ran in 165 ms on average

Device Config:

CPU: Intel Core i5 6400 2.7GHz

Memory: 32G DDR3 2133MHz

SSD: WDC WDS240g20A

Code:

public class Executer
{
    [Benchmark]
    public void Exec()
    {
        var file = File.ReadAllLines(@".\1M_random_numbers.txt");

        var integers = file.Select(c => int.Parse(c)).ToList();

        var result = CountIntegers.MostRepeated(integers);

        Console.WriteLine(result);
    }
}

public static class CountIntegers
{
    private static int[] arr = new int[1000];

    public static (int value, int index) MostRepeated(List<int> integers)
    {
        var interval = integers.Count / 100;

        var actions = new Action[100];

        for (int i = 0; i < 100; i++)
        {
            var local_i = i;

            actions[i] = () =>
            {
                for (int j = local_i * interval; j < (local_i + 1) * interval; j++)
                {
                    arr[integers[j]]++;
                }
            };
        }

        Parallel.Invoke(actions);

        var maxItem = FindMaximum(arr);

        return maxItem;
    }

    public static (int value, int index) FindMaximum(int[] array)
    {
        return FindMaxRec(array, 0, array.Length - 1);
    }

    private static (int value, int index) FindMaxRec(int[] array, int from, int to)
    {
        if (to <= from + 1)
            return array[from] > array[to] ? (array[from], from) : (array[to], to);

        (int value, int index) left = default;
        (int value, int index) right = default;

        Parallel.Invoke
            (
                () => left = FindMaxRec(array, from, (from + to) / 2),
                () => right = FindMaxRec(array, (from + to) / 2 + 1, to)
            );

        return left.value > right.value ? left : right;
    }
}

I put all the numbers in a hash, in case they are needed for later processing. But the hash as implemented is only used for counting. As far as optimization, the fastest solution will certainly be to keep a running total of the number with the largest frequency. I used an array in case there are many numbers with the same frequency. This way you dont have to spend time sorting all the numbers by frequency. Basically you get the answer in O(n) time instead of O(n log n), so always faster.

I have included the time, but it may be useful to look at the Shortcomings of Empirical Metrics section in the Analysis of Algorithms Wikipedia article. Big O analysis will always be better than Empirical Metrics for exactly these reasons.

My solution is in Perl. With C and Assembler, run time will surely be faster, but development time will be longer. The code will also be less direct, less concise, and more difficult to follow. Fumbling around with a strict rather than dynamic type system will always add to development time and frustration.

Here is the code...

#!/usr/bin/perl -w

my $appearanceCount = -1;
my @appearanceNumber;
my %count;

while(<>){
  chomp;
  $count{$_}++;
  #keeping a running total will always be faster than sorting all hash values
  if($appearanceCount < $count{$_}){
    undef @appearanceNumber;
    push(@appearanceNumber,$_);
    $appearanceCount = $count{$_};
  }elsif($appearanceCount == $count{$_}){
    push(@appearanceNumber,$_);
  }
  if(eof){
    print "$ARGV: ";
    print "Numbers with biggest count, ordered by first appearance  <$appearanceCount> @appearanceNumber\n";
    #DEBUG print "$count{$_}: $_\n" for(sort{$count{$b} <=> $count{$a}} keys(%count)); #print all appearances in descending order
    #reset variables for next file
    undef %count;
    undef @appearanceNumber;
    $appearanceCount = -1;
  }
}

Here is the output...

$ time perl biggest.pl biggest1.txt biggest2.txt biggest3.txt

biggest1.txt: Numbers with biggest count, ordered by first appearance  <2> 208 188 641 546 374 694
biggest2.txt: Numbers with biggest count, ordered by first appearance  <23> 284
biggest3.txt: Numbers with biggest count, ordered by first appearance  <1130> 142

real    0m0.213s
user    0m0.209s
sys     0m0.004s

That is a metric for all three files at once sequentially, here is the biggest file individually...

$ time perl biggest.pl biggest3.txt
biggest3.txt: Numbers with biggest count, sorted by first appearance  <1130> 142

real    0m0.203s
user    0m0.200s
sys     0m0.003s

That timing is on a ~6 year old laptop with a million tabs open watching youtube videos and hasnt been rebooted in 19 days. Not exactly a top of the line server. But I know for certain this is the fastest algorithm. Hooray for Big O Analysis!

C AVX2 intrinsics

Uses SIMD to parse and reduce.

Tries to parse an integer starting at every byte position. Then discards inactive lanes.

#include <stdint.h>
#include <immintrin.h>

static uint32_t frequency[1000];

static inline const uint8_t* collect_number(const uint8_t* ptr){
    size_t n = *ptr++ - 0x30;
    for(;;) {
        uint8_t c = *ptr++;
        if(c == 0x0A) break;
        n = (n * 10) + (c - 0x30);
    }
    frequency[n]++;
    return ptr;
}

// parse and return the most frequent number
// if tied return the largest
uint32_t do_challenge (const uint8_t* file_buf, size_t file_size) {
  const uint8_t* ptr = file_buf;

  if(file_size >= 4) {
    // the simd routine looks-back three bytes
    // so special case the first token
    if((file_buf[1] == 0x0A) || (file_buf[2] == 0x0A)) collect_number(ptr);

    const uint8_t* end = &file_buf[((file_size - 3) & ~31)]; // YOLO ?
    while(ptr < end){
      __m256i v0 = _mm256_loadu_si256((const __m256i *)&ptr[0]);
      __m256i v1 = _mm256_loadu_si256((const __m256i *)&ptr[1]);
      __m256i v2 = _mm256_loadu_si256((const __m256i *)&ptr[2]);
      __m256i v3 = _mm256_loadu_si256((const __m256i *)&ptr[3]);
      ptr += 32;

      // get bytes depending on odd or even run start
      // non-active lanes will contain garbage
      //
      // we don't go pure vertical because tokens will have a minimum of
      // 2 bytes in length and we have to widen to 16-bit integers anyways
      __m256i lo = _mm256_min_epi16(v2, v3);
      __m256i hi = _mm256_blendv_epi8(v0, v1, _mm256_cmpeq_epi16(v3, lo));

      // convert text to binary
      const __m256i ascii_zero = _mm256_set1_epi8(0x30); // '0'
      const __m256i mul = _mm256_set1_epi16(0x0A64); // hi-byte * 10, lo-byte * 100
      hi = _mm256_max_epi16(hi, ascii_zero); // fixup low byte if token only had 1 digit
      hi = _mm256_maddubs_epi16(_mm256_subs_epu8(hi, ascii_zero), mul);
      __m256i bin = _mm256_add_epi16(_mm256_subs_epu8(lo, ascii_zero), hi);

      // despace
      //
      // counting non-active lanes could double the required work
      // but we also don't want to branch too much....
      //
      // the blend makes sure the lo-word of each dword is always an active lane
      // the shuffle moves all the "always" lo-words to the lo-qword
      // and moves the "maybe" hi-words to the hi-qword
      // (more work will happen later to deal with the hi-qwords)
      __m256i active = _mm256_cmpgt_epi16(mul, lo); // if '\n' in high byte
      const __m256i shuf = _mm256_set_epi8(
        15,14,11,10,7,6,3,2, 13,12,9,8,5,4,1,0,
        15,14,11,10,7,6,3,2, 13,12,9,8,5,4,1,0
      );
      __m256i r = _mm256_blendv_epi8(_mm256_srli_epi32(bin, 16), bin, active);
      r = _mm256_shuffle_epi8(r, shuf);
      __m128i r_lo = _mm256_castsi256_si128(r);
      __m128i r_hi = _mm256_extracti128_si256(r, 1);

      // extract lo-qwords and count
      uint64_t q0 = _mm_cvtsi128_si64x(r_lo);
      uint64_t q2 = _mm_cvtsi128_si64x(r_hi);
      frequency[q0 & 0xFFFF]++;
      frequency[q2 & 0xFFFF]++;
      (*((uint32_t*)(((uintptr_t)frequency) + ((q0 >> 14) & 0xFFFF))))++;
      (*((uint32_t*)(((uintptr_t)frequency) + ((q2 >> 14) & 0xFFFF))))++;
      (*((uint32_t*)(((uintptr_t)frequency) + ((q0 >> 30) & 0xFFFF))))++;
      (*((uint32_t*)(((uintptr_t)frequency) + ((q2 >> 30) & 0xFFFF))))++;
      (*((uint32_t*)(((uintptr_t)frequency) + (q0 >> 46))))++;
      (*((uint32_t*)(((uintptr_t)frequency) + (q2 >> 46))))++;

      // despace hi-qwords, then count
      static const uint64_t table[8] = {
        0x0000000000000F0E, 0x000000000F0E0908, 0x000000000F0E0B0A, 0x00000F0E0B0A0908,
        0x000000000F0E0D0C, 0x00000F0E0D0C0908, 0x00000F0E0D0C0B0A, 0x0F0E0D0C0B0A0908
      };
      unsigned key = (unsigned)_mm256_movemask_ps(_mm256_castsi256_ps(
        _mm256_cmpeq_epi32(active, _mm256_set1_epi32(-1))));
      uint64_t q1 = _mm_cvtsi128_si64x(_mm_shuffle_epi8(r_lo, _mm_loadl_epi64((__m128i*)(&table[key & 7]))));
      uint64_t q3 = _mm_cvtsi128_si64x(_mm_shuffle_epi8(r_hi, _mm_loadl_epi64((__m128i*)(&table[(key >> 4) & 7]))));
      int q1_popcnt = _mm_popcnt_u32(key & 0x0F);
      int q3_popcnt = _mm_popcnt_u32(key >> 4);
      for(int i = 0; i < q1_popcnt; i++) {frequency[q1 & 0xFFFF]++; q1 >>= 16;}
      for(int i = 0; i < q3_popcnt; i++) {frequency[q3 & 0xFFFF]++; q3 >>= 16;}
    }

    // re-align to point to the first unparsed token
    ptr += 3;
    while(*ptr != 0x0A) ptr--;
    ptr++;
  }

  // tail loop
  while(ptr != &file_buf[file_size]){
    ptr = collect_number(ptr);
  }

  // find max
  //
  // stuff the number in the bottom of the fequency count
  // so we don't have to do a 2nd pass looking for
  // numbers matching max count
  __m256i max256 = _mm256_setzero_si256();
  __m256i offset = _mm256_set_epi32(7,6,5,4,3,2,1,0);
  __m256i inc = _mm256_set1_epi32(8);
  for (int i = 0; i < 1000; i+=8) {
    __m256i v = _mm256_loadu_si256((const __m256i *)&frequency[i]);
    v = _mm256_or_si256(_mm256_slli_epi32(v, 10), offset);
    offset = _mm256_add_epi32(offset, inc);
    max256 = _mm256_max_epu32(max256, v);
  }
  __m128i max_lo = _mm256_castsi256_si128(max256);
  __m128i max_hi = _mm256_extracti128_si256(max256, 1);
  __m128i max128 = _mm_max_epu32(max_lo, max_hi);
  __m128i max64 = _mm_max_epu32(max128, _mm_unpackhi_epi64(max128, max128));
  __m128i max32 = _mm_max_epu32(max64, _mm_srli_epi64(max64, 32));
  uint32_t max = (uint32_t)_mm_cvtsi128_si32(max32);
  return max & 0x3FF;
}

The Solution Method:

• I implemented different version of solution functions with incremental code optimization changes(some are decremental and reversal) to check whether those changes really improved the execution time. Surprised me, ...it is not always the case! It depends a lot on how the numbers are arranged in the list.

• Just an important note: I wrote all the codes by myself and did not use code generated by AI. All the codes came from my thoughts and my fingers. I consulted search engines for specific programming syntax things I did not know yet just like in the no-AI days back then. No copy-paste solution method is used in this mini project.

• Here is my git repo to see the full code, test scripts, and more results.

  • all of the solution code and execution time measurement resides in cpp/main.cpp file.
  • build scripts and bigger benchmark customizations are handled by *.sh scripts.

The Environment and Tools:

• Dev OS: Windows 11 64bit
• Execution Environment: WSL2 Ubuntu 24.04
• Programming Languages: C/C++, Bash
• Hardware Specs:
  • Processor: AMD Ryzen 7 5800H with Radeon Graphics ~3.2GHz
  • RAM: 16GB
• Execution method:
  1. Restart the PC.
  2. Open terminal, start wsl
  3. Open task-manager via Ctrl+Shift+Esc to check if no other resource intensive app is running.
  4. Navigate to project_path/cpp/.
  5. Execute the benchmark script: ./benchmark.sh > benchmark_result.md
  6. Don't you dare touch your keyboard and mouse until the process is complete.
  7. Open benchmark_result.md in VS Code.
  8. Ctrl+K V to preview in markdown viewer.
  9. You can now look on the execution result.

The Solution Functions:

• Here is the summary table of the test functions I implemented, to be used in this benchmark:

  name	Description
  funcA	unoptimized. basis for correct results.
  funcB	like funcA but search maxcount starting from iMin.
  funcC	like funcB but now, search upto iMax only.
  funcD	like funcC but counting ahead consecutive same numbers.
  funcE	like funcD but converted most conditional branches to branchless version.
  funcF	like funcE but converted back the branches that uses &&, and `
  funcG	like funcE but remove all const specifier of vars inside the loops.
  funcH	like funcE but changed the inside loop from while to for.
  funcI	like funcE but removed counting ahead of consecutive same numbers.

• The solution list -- the number(s) with the most count --, is/are saved in a fixed size vector<int> so no allocation will happen when collecting them. Here is the preview with skipped lines:

  ...
  vector<int> counts(1000, 0);
  vector<int> results(1000, 0);
  ...
  std::fill(counts.begin(), counts.end(), 0); 
  results.clear();
  ...
  f.func(listNums, counts, results);
  ...
  listResult.push_back(results);
  ...
  

  • See/Jump to [The Measurement](#the-measurement) section for the complete code.

• The solution functions code from funcA to funcI are provided below:

  /* ===================================
  * funcA: Count and search with maxCount
  --------------------------------------*/
  void funcA(const vector<int>& listN, vector<int>& counts, vector<int>& results){
      int iMaxCount = 0, vMaxCount = 0; 
      // --- count
      const size_t numItems = listN.size();
      for(size_t i = 0; i < numItems; i++){
          auto vCur = ++counts[ listN[i] ];
          if(vMaxCount < vCur) {
              vMaxCount = vCur;
              iMaxCount = listN[i];
          }
      }
      // --- search and get the results
      const size_t numCounts = counts.size();
      for(size_t i = 0; i < numCounts; i++){
          if ( counts[i] != vMaxCount ) continue;
          results.push_back(i);
      }
  
  }
  
  /* ===================================
  * funcB: Count and search maxcount from index iMin.
  --------------------------------------*/
  void funcB(const vector<int>& listN, vector<int>& counts, vector<int>& results){
  
      int iMin = 0, vMaxCount = 0;  //
      // --- count
      const size_t numItems = listN.size();
      for(size_t i = 0; i < numItems; i++){
          auto const iCur = listN[i];
          auto const vCur = ++counts[ iCur ];
          if(vMaxCount < vCur) {
              vMaxCount = vCur;
              iMin = iCur;
          } else if (vMaxCount == vCur && iCur < iMin) {
              iMin = iCur;
          }
      }
      // --- search and get the results
      const size_t numCounts = counts.size();
      for(size_t i = iMin; i < numCounts; i++){
          if (counts[i] != vMaxCount) continue;
          results.push_back(i);
      }
  
  }
  
  
  /* ===================================
  * funcC: Count and search maxcount from iMin to iMax indices
  -------------------------------------*/
  void funcC(const vector<int>& listN, vector<int>& counts, vector<int>& results){
      int iMin = 0, iMax = 0, vMaxCount = 0;
      const size_t numItems = listN.size();
      for(size_t i = 0; i < numItems; i++){
          auto const iCur = listN[i];
          auto const vCur = ++counts[ iCur ];
          if(vMaxCount < vCur) {
              vMaxCount = vCur;
              iMin = iMax = iCur;
          } else if (vMaxCount == vCur) {
              if (iCur < iMin) {
                  iMin = iCur;
              }
              else if (iCur > iMax) {
                  iMax = iCur;
              }
          }
      }
      // --- search and get the results
      for(size_t i = iMin; i <= iMax; i++){
          if (counts[i] != vMaxCount) continue;
          results.push_back(i);
      }
  
  }
  
  /* ===================================
  * funcD: Count and search maxcount from iMin to iMax indices
  *  + take advantage of consecutive same numbers.
  -------------------------------------*/
  void funcD(const vector<int>& listN, vector<int>& counts, vector<int>& results){
      int iMin = 0, iMax = 0, vMaxCount = 0;
      const size_t numItems = listN.size();
      for(size_t i = 0; i < numItems; i++){
          auto const iCur = listN[i];
  
          // --- count ahead consecutive same numbers
          int j = i+1;
          while (iCur == listN[j] && j < numItems) j++;
          auto const vCur = counts[ iCur ] += (j - i);
          i = j - 1;
  
          // --- update searching info
          if(vMaxCount < vCur) {
              vMaxCount = vCur;
              iMin = iMax = iCur;
          } else if (vMaxCount == vCur) {
              if (iCur < iMin) {
                  iMin = iCur;
              }
              else if (iCur > iMax) {
                  iMax = iCur;
              }
          }
      }
      // --- search and get the results
      for(size_t i = iMin; i <= iMax; i++){
          if (counts[i] != vMaxCount) continue;
          results.push_back(i);
      }
  
  }
  
  /* ===================================
  * funcE: Count and search maxcount from iMin to iMax indices
  *  + take advantage of consecutive same numbers
  *  + less branches inside the loop by using &,| instead of &&,||
  *     to lessen branch mispredictions.
  -------------------------------------*/
  void funcE(const vector<int>& listN, vector<int>& counts, vector<int>& results){
      int iMin = 0, iMax = 0;
      int vMaxCount = 0;
      const size_t numItems = listN.size();
      for(size_t i = 0; i < numItems; i++){
          auto const iCur = listN[i];
  
          // --- count ahead consecutive same numbers
          int j = i+1;
          while (iCur == listN[j] & j < numItems) j++;
          auto const vCur = counts[ iCur ] += (j - i);
          i = j - 1;
  
          // --- update searching info
          const int diffCount = vCur - vMaxCount;
          const int diffIdxMin = iCur - iMin;
          const int diffIdxMax = iCur - iMax;
          const bool bDiffCountNeg = diffCount < 0;
          const bool bDiffCount0   = diffCount == 0;
          vMaxCount += ((diffCount <= 0)-1) & diffCount;
          iMin += ((bDiffCountNeg | (bDiffCount0 & diffIdxMin >= 0))-1) & diffIdxMin;
          iMax += ((bDiffCountNeg | (bDiffCount0 & diffIdxMax <= 0))-1) & diffIdxMax;
  
      }
  
      // --- search and get the results
      for(size_t i = iMin; i <= iMax; i++){
          if (counts[i] != vMaxCount) continue;
          results.push_back(i);
      }
  
  }
  
  /* ===================================
  * funcF: Count and search maxcount from iMin to iMax indices
  *  + take advantage of consecutive same numbers
  *  ? convert back branches(&&,||) on conditions expression
  *    because surprisingly, it is sometimes faster than funcE
  *    (I'm still not sure why.)
  -------------------------------------*/
  void funcF(const vector<int>& listN, vector<int>& counts, vector<int>& results){
      int iMin = 0, iMax = 0;
      int vMaxCount = 0;
      const size_t numItems = listN.size();
      for(size_t i = 0; i < numItems; i++){
          auto const iCur = listN[i];
  
          // --- count ahead consecutive same numbers
          int j = i+1;
          while (iCur == listN[j] && j < numItems) j++;   // changed back from & to &&.
          auto const vCur = counts[ iCur ] += (j - i);
          i = j - 1;
  
          // --- update searching info
          const int diffCount = vCur - vMaxCount;
          const int diffIdxMin = iCur - iMin;
          const int diffIdxMax = iCur - iMax;
          const bool bDiffCountNeg = diffCount < 0;
          const bool bDiffCount0   = diffCount == 0;
          vMaxCount += ((diffCount <= 0)-1) & diffCount;
          iMin += ((bDiffCountNeg || (bDiffCount0 && diffIdxMin >= 0))-1) & diffIdxMin;  //changed back from &,| to &&,||
          iMax += ((bDiffCountNeg || (bDiffCount0 && diffIdxMax <= 0))-1) & diffIdxMax;
  
      }
  
      // --- search and get the results
      for(size_t i = iMin; i <= iMax; i++){
          if (counts[i] != vMaxCount) continue;
          results.push_back(i);
      }
  
  }
  
  /* ===================================
  * funcG: Count and search maxcount from iMin to iMax indices
  *  + take advantage of consecutive same numbers
  *  + less branches inside the loop by using &,| instead of &&,||
  *     to lessen branch mispredictions.
  *  ? remove 'const' variables inside the loop.
  -------------------------------------*/
  void funcG(const vector<int>& listN, vector<int>& counts, vector<int>& results){
      int iMin = 0, iMax = 0;
      int vMaxCount = 0;
      const size_t numItems = listN.size();
      for(size_t i = 0; i < numItems; i++){
          auto iCur = listN[i];
  
          // --- count ahead consecutive same numbers
          int j = i+1;
          while (iCur == listN[j] & j < numItems) j++;
          auto vCur = counts[ iCur ] += (j - i);
          i = j - 1;
  
          // --- update searching info
          int diffCount = vCur - vMaxCount;
          int diffIdxMin = iCur - iMin;
          int diffIdxMax = iCur - iMax;
          bool bDiffCountNeg = diffCount < 0;
          bool bDiffCount0   = diffCount == 0;
          vMaxCount += ((diffCount <= 0)-1) & diffCount;
          iMin += ((bDiffCountNeg | (bDiffCount0 & diffIdxMin >= 0))-1) & diffIdxMin;
          iMax += ((bDiffCountNeg | (bDiffCount0 & diffIdxMax <= 0))-1) & diffIdxMax;
  
      }
  
      // --- search and get the results
      for(size_t i = iMin; i <= iMax; i++){
          if (counts[i] != vMaxCount) continue;
          results.push_back(i);
      }
  
  }
  
  /* ===================================
  * funcH: Count and search maxcount from iMin to iMax indices
  *  + take advantage of consecutive same numbers
  *  + less branches inside the loop by using &,| instead of &&,||
  *     to lessen branch mispredictions.
  *  ? changed 'while' to 'for' for consecutive same numbers
  -------------------------------------*/
  void funcH(const vector<int>& listN, vector<int>& counts, vector<int>& results){
      int iMin = 0, iMax = 0;
      int vMaxCount = 0;
      const size_t numItems = listN.size();
      for(size_t i = 0; i < numItems; i++){
          auto iCur = listN[i];
  
          // --- count ahead consecutive same numbers
          int j;
          for (j = i+1; iCur == listN[j] & j < numItems; j++);
          auto vCur = counts[ iCur ] += (j - i);
          i = j - 1;
  
          // --- update searching info
          const int diffCount = vCur - vMaxCount;
          const int diffIdxMin = iCur - iMin;
          const int diffIdxMax = iCur - iMax;
          const bool bDiffCountNeg = diffCount < 0;
          const bool bDiffCount0   = diffCount == 0;
          vMaxCount += ((diffCount <= 0)-1) & diffCount;
          iMin += ((bDiffCountNeg | (bDiffCount0 & diffIdxMin >= 0))-1) & diffIdxMin;
          iMax += ((bDiffCountNeg | (bDiffCount0 & diffIdxMax <= 0))-1) & diffIdxMax;
  
      }
  
      // --- search and get the results
      for(size_t i = iMin; i <= iMax; i++){
          if (counts[i] != vMaxCount) continue;
          results.push_back(i);
      }
  
  }
  
  /* ===================================
  * funcI: Count and search maxcount from iMin to iMax indices
  *  + less branches inside the loop by using &,| instead of &&,||
  *     to lessen branch mispredictions.
  -------------------------------------*/
  void funcI(const vector<int>& listN, vector<int>& counts, vector<int>& results){
      int iMin = 0, iMax = 0;
      int vMaxCount = 0;
      const size_t numItems = listN.size();
      for(size_t i = 0; i < numItems; i++){
          auto const iCur = listN[i];
          auto const vCur = ++counts[ iCur ];
  
          // --- update searching info
          const int diffCount = vCur - vMaxCount;
          const int diffIdxMin = iCur - iMin;
          const int diffIdxMax = iCur - iMax;
          const bool bDiffCountNeg = diffCount < 0;
          const bool bDiffCount0   = diffCount == 0;
          vMaxCount += ((diffCount <= 0)-1) & diffCount;
          iMin += ((bDiffCountNeg | (bDiffCount0 & diffIdxMin >= 0))-1) & diffIdxMin;
          iMax += ((bDiffCountNeg | (bDiffCount0 & diffIdxMax <= 0))-1) & diffIdxMax;
  
      }
  
      // --- search and get the results
      for(size_t i = iMin; i <= iMax; i++){
          if (counts[i] != vMaxCount) continue;
          results.push_back(i);
      }
  
  }
  

Internal Test Data Generation:

• The program will generate internal test data if there are no valid input files are provided in the command-line argument.

• The generation of the internal test data happens in this code:

  auto randomPure = [](auto& listN) {
      for(auto& list : listN) {
          for(auto& v : list) {
              v = rand() % 1000;
          }
      }
  };
  
  // --- if input data from command line argument is empty...
  if (listTestData.empty()){
      vector<STestData> internalTestData {
          {"10k", vector(100, vector<int>(10'000))},
          {"100k", vector(100, vector<int>(100'000))},
          {"1M",  vector(50, vector<int>(1'000'000))},
          {"10M",  vector(10, vector<int>(10'000'000))},
      };
  
      // --- generate test data.
      vLog("- Generating internal test data...");
      for(auto& test : internalTestData){
          randomPure(test.listTest);
      }
      listTestData = std::move(internalTestData);
  }
  

  • Here, for "10M" test data, there are 10 different set of 10 million random numbers that are run for each test functions.
  • For the input files, 1 file means only 1 list of random numbers. To execute it to a test function multiple times, set a value to --num-iterations in the command line argument.

The Measurement:

• The Timer strictly starts and stops right before and right after the execution of a solution function.

• And then the elapsed time are accumulated for a specific test data set.

• Solution functions results must be correct. funcA is the basis function.

• If a solution functions produced atleast 1 incorrect answer, the total duration will be set to -1, stopping further execution of test data, and then proceed to measuring the next test data set.

• If you see a -1μs in a summary table, that means the function failed to give the correct solution.

• After the measurement process, a summary table is printed that shows average execution time values.

• Execution time of each test data is performed with the following code.

  // --- start benchmark
  vLog("# Start benchmarking...");
  Timer timer;
  vector<int> counts(1000, 0);
  vector<int> results(1000, 0);
  vector<int> expected;
  const int IDX_BASIS_FUNC = 0;
  
  for(auto& test : listTestData){
      //randomPure(*test.listTest);
      //randomSorted(*test.listTest);
      vector<vector<int>> listResult, listExpected;
      listExpected.clear();
      test.listDurations.clear();
      for(auto& f : listFuncToTest) {
          Timer::duration_t totalDur = 0;
          listResult.clear();
          if(bVerbose) {
              cout << "\n ## Testing `" << f.name << "` with `" << test.name << "`:" << endl;
              cout << "- dur list: " << endl << "    ```c++" << endl  << "    ";
          }
          for(int i = 0; i < numIterations; i++) {
              for(auto& listNums : test.listTest) {
  
                  // --- prepare input/output containers.
                  std::fill(counts.begin(), counts.end(), 0); 
                  results.clear();
  
                  // --- execute process
                  timer.start();
                  f.func(listNums, counts, results);
                  timer.stop();
  
                  // --- accumulate execution time.
                  if(bVerbose) cout << timer.getElapsed() << "μs, ";
                  totalDur += timer.getElapsed();
                  listResult.push_back(results);
  
              }
          }
          if(bVerbose) cout << endl << "    ```" << endl;
  
          if (f.func == listFuncToTest[IDX_BASIS_FUNC].func) {
              listExpected = listResult;
              if(bVerbose) {
                  cout << "- get funcA result as basis." << endl;
                  cout << " - **actual result**: " << endl;
                  printResult(listResult);
              }
          } else if (listExpected != listResult) {
              totalDur = -1;
              if(bVerbose) {
                  cout << "- ### result not matched!" << endl;
                  printResultComparison(listExpected, listResult);
              }
              break;
          }
  
          test.listDurations.push_back(totalDur);
  
          if(bVerbose) {
              cout << "- ### total duration: " << totalDur << " μs" << endl;
          }
  
      }
  }
  
  // --- print average execution time summary table(in markdown syntax).
  vLog( "\n\n # Summary: Average execution time.");
  printSummaryTable(listFuncToTest, listTestData, numIterations, bShowFuncDesc);
  

The Result:

• The next section below shows a sample generated result of the resulting app and benchmark scripts.
• The values in the tables are average execution time.
• You can see that the optimize version of functions is slower than the unoptimized version when the input data are purely random but a lot better when the data are sorted.
• In my conclusion, it really pays well if the input data is normalized first before processing. In this case, "sorted".
• For the unoptimized version -- funcA, the execution time is consistent whether the data is sorted or not.
• I am expecting funcE will be the most optimized and will win on all the data cases but it didn't happen. Probably due to the write-then-read delay of iMin, iMax, and vMaxCount between iterations in the loop. (need more study)
• There are times, funcE, which is mostly branchless, was beaten by other functions, with a lot of branches, even on a sorted data. I think these are the cases where branch predictions really speed-up the execution time, but kind of randomly, it seems. Sometimes, a function won against others and then on the next benchmark run it was beaten by others.

Benchmark Results: Built with -std=c++17 -O3

• Internal Test Data

  name	10k	100k	1M	10M
  funcA	5.84 μs	57.12 μs	578.34 μs	6522.20 μs
  funcB	21.85 μs	220.06 μs	2104.02 μs	20774.20 μs
  funcC	5.49 μs	57.69 μs	540.14 μs	5554.10 μs
  funcD	12.25 μs	119.10 μs	1192.10 μs	11800.10 μs
  funcE	21.36 μs	218.82 μs	2199.56 μs	21898.20 μs
  funcF	14.31 μs	142.08 μs	1419.20 μs	14195.70 μs
  funcG	21.49 μs	218.27 μs	2189.46 μs	21813.90 μs
  funcH	21.23 μs	218.92 μs	2188.74 μs	21745.00 μs
  funcI	20.74 μs	211.34 μs	2118.92 μs	21211.40 μs

• Internal Test Data Sorted

  name	10k	100k	1M	10M
  funcA	16.27 μs	64.75 μs	479.82 μs	4727.50 μs
  funcB	9.12 μs	81.17 μs	698.62 μs	6906.10 μs
  funcC	10.07 μs	62.45 μs	478.00 μs	4788.50 μs
  funcD	10.06 μs	41.42 μs	361.02 μs	3613.00 μs
  funcE	11.07 μs	52.21 μs	474.64 μs	4758.40 μs
  funcF	10.02 μs	41.75 μs	362.26 μs	3648.90 μs
  funcG	11.29 μs	51.46 μs	470.04 μs	4729.90 μs
  funcH	11.00 μs	53.18 μs	472.74 μs	4712.20 μs
  funcI	22.21 μs	221.65 μs	2059.62 μs	20615.30 μs

• Input Files

  name	input/100_nums.txt	input/10k_nums.txt	input/1M_nums.txt
  funcA	0 μs	6.00 μs	571.00 μs
  funcB	0 μs	15.00 μs	1467.00 μs
  funcC	0 μs	6.00 μs	516.00 μs
  funcD	0 μs	12.00 μs	1151.00 μs
  funcE	0 μs	21.00 μs	2135.00 μs
  funcF	0 μs	14.00 μs	1379.00 μs
  funcG	0 μs	21.00 μs	2123.00 μs
  funcH	0 μs	21.00 μs	2161.00 μs
  funcI	0 μs	20.00 μs	2063.00 μs

• Input Files Sorted

  name	input/100_nums.txt	input/10k_nums.txt	input/1M_nums.txt
  funcA	0 μs	16.00 μs	487.00 μs
  funcB	0 μs	9.00 μs	699.00 μs
  funcC	0 μs	10.00 μs	489.00 μs
  funcD	0 μs	10.00 μs	352.00 μs
  funcE	0 μs	11.00 μs	456.00 μs
  funcF	0 μs	10.00 μs	345.00 μs
  funcG	0 μs	8.00 μs	468.00 μs
  funcH	0 μs	6.00 μs	465.00 μs
  funcI	0 μs	22.00 μs	2091.00 μs

• Input Files - Run 100x Each

  name	input/100_nums.txt	input/10k_nums.txt	input/1M_nums.txt
  funcA	0.01 μs	5.12 μs	553.54 μs
  funcB	0 μs	8.72 μs	1406.53 μs
  funcC	0 μs	6.85 μs	542.77 μs
  funcD	0 μs	11.81 μs	1159.99 μs
  funcE	0 μs	21.05 μs	2121.98 μs
  funcF	0 μs	14.16 μs	1375.58 μs
  funcG	0 μs	21.02 μs	2138.88 μs
  funcH	0 μs	21.30 μs	2134.64 μs
  funcI	0 μs	20.05 μs	2084.02 μs

• Input Files Sorted - Run 100x Each

  name	input/100_nums.txt	input/10k_nums.txt	input/1M_nums.txt
  funcA	0.01 μs	14.97 μs	474.40 μs
  funcB	0 μs	9.15 μs	697.87 μs
  funcC	0 μs	10.00 μs	469.82 μs
  funcD	0 μs	4.13 μs	346.24 μs
  funcE	0 μs	5.10 μs	458.06 μs
  funcF	0 μs	4.09 μs	346.53 μs
  funcG	0 μs	5.15 μs	458.65 μs
  funcH	0 μs	5.00 μs	462.79 μs
  funcI	0 μs	22.10 μs	2077.07 μs

Learnings:

• I improved my skills in boolean algebra to optimize the conditional expressions.
• I discovered how to convert code branches to their branchless version.
• I realized, I really should benchmark my work when I need to optimize. It's not enough to know that you added an optimization code.
• To really achieve better performance, you need to normalize the data. (in this case, SORT them). Feeding a random data to an optimized function does not guarantee the optimization will take effect. Sometimes the result will be worse than the unoptimized version. The optimization must be applied to both the code and the data, not just to the code.
• Using a documentation syntax, like markdown, for the logs will make the result more presentable and easier to see and analyze.

Conclusion:

• Optimize both the data and the code to achieve better performance.
• Branch prediction is unpredictable. It really speeds up the execution time but not always guaranteed.

Beyond:

• Feel free to suggest ideas on what can be improved to my solutions, like any technical things I might not know or overlooked.
• Like you see, I didn't researched for existing solutions like any algorithms related to this kind of problem. I really don't know where to start sometimes and just enjoy solving the puzzle by myself.
• Can someone explains or provide details regarding cache misses and where in my code was affected by it?
• Also, why/when/where the branch predictions failed/succeed in my given code?
• Anything you like to comment.
• Feel free to check my todo_list.txt in the my git repo and based your suggestions/comments/ideas from there.

I have used a variant of counting sort.

As we know that all the numbers are between 0 and 999 we can have an array of 1000 counters indexed by the input numbers.

Then after the iteration on all numbers we iterate on the counter array to get its maximum value with the related index corresponding to the number that appears the most.

After, we need another iteration on the counter array to ensure there exists a unique number appearing most often than others because there could have been several numbers with same number of occurrence as in the provided list of 100 integers. This final loop can be only partial, beginning after the minimum index of maximum count computed in the previous loop, nevertheless its worst case is in 999 iterations, with the first iteration at index 1.

So we need 3 loops, the first one with n iterations where n is the length of the input list, the 2 others with at most k iterations where k = maximum number value + 1 = 1000 is a constant. Consequently the algorithm time complexity is linear in n: O(n). The memory complexity to process the data does not depend on n as we need only an internal array of 1000 counters.

We could merge the first loop on the inputs with the second loop computing the max on the 1000 counters, but it leads to worst time result because as n is 1000 times greater than 1000 (number of counters), it implies 1000 times more comparisons in loops, whereas by computing the max in a separate loop, the loop of n iterations is kept without any comparison leading to more efficiency.

The implementation of the algorithm in integer_counting.c++:

#include "integer_counting.h"
#include <array>

using namespace std;

static constexpr size_t max_number = 999;

optional<uint16_t>
get_most_common_number(const uint16_t *numbers, size_t len)
{
    array<size_t, max_number + 1> counts{};

    for (size_t i = 0; i < len; ++i) {
        ++counts[numbers[i]];
    }

    size_t max_count = 0;
    uint16_t idx_max_count = 0;
    for (uint16_t idx = 0; idx <= max_number; ++idx) {
        if (counts[idx] > max_count) {
            max_count = counts[idx];
            idx_max_count = idx;
        }
    }

    // Check if maximum count occurs for more than one number.
    for (uint16_t idx = idx_max_count + 1; idx <= max_number; ++idx) {
        if (counts[idx] == max_count) {
            return {};
        }
    }

    return make_optional(idx_max_count);
}

The related include file with the prototype and its needed includes in integer_counting.h:

#pragma once
#include <cstddef>
#include <cstdint>
#include <optional>

std::optional<std::uint16_t>
get_most_common_number(const std::uint16_t *numbers, std::size_t len);

The code used to test with lists of 100 and 10000 numbers in test.c++:

#include <iostream>
#include <array>
#include <vector>
#include "integer_counting.h"

using namespace std;

const vector<uint16_t> random_numbers_100 = {
    #include "100_random_numbers.inc"
};

const vector<uint16_t> random_numbers_10000 = {
    #include "10000_random_numbers.inc"
};

const array<const vector<uint16_t> *, 2> test_data = {
    &random_numbers_100,
    &random_numbers_10000,
};

int main()
{
    for (auto p: test_data) {
        const auto ret = get_most_common_number(p->data(), p->size());
        cout << "In list of " << p->size() << " numbers ";
        if (!ret) {
            cout << "there is not a unique number appearing most often than others." << endl;
            continue;
        }
        cout << "the number that appears the most is: " << ret.value() << endl;
    }
}

The code used for the benchmark with google-benchmark v1.9.4 in benchmark.c++:

#include <benchmark/benchmark.h>
#include <array>
#include "integer_counting.h"

using namespace std;

namespace {
const array<uint16_t, 1'000'000> random_numbers_1M = {
    #include "1M_random_numbers.inc"
};

void BM_get_most_common_number(benchmark::State& state)
{
    for (auto _: state) {
        get_most_common_number(random_numbers_1M.data(), random_numbers_1M.size());
    }
}
BENCHMARK(BM_get_most_common_number);

}

BENCHMARK_MAIN();

NB: to produce the .inc files containing the lists of numbers with lines terminated by a comma I used sed on the raw text files (the utterance of the challenge is about processing a list of numbers not an external raw text file):

$ for f in ../data/*_random_numbers.txt; do sed 's!$!,!' $f > $(basename $f .txt).inc; done

Then to build the test program:

g++ -std=c++17 -Wall -Wextra integer_counting.c++ test.c++ -o test_integer_counting

Then testing:

$ ./test_integer_counting 
In list of 100 numbers there is not a unique number appearing most often than others.
In list of 10000 numbers the number that appears the most is: 284

To build the benchmark program assuming that google-benchmark v1.9.4 is installed on the machine:

g++ -std=c++17 -Wall -Wextra -O3 integer_counting.c++ benchmark.c++ -lbenchmark -o benchmark_integer_counting

The benchmark on an intel core i9 14900K give a time of around 200 microseconds:

$ ./benchmark_integer_counting
2025-10-01T01:13:16+02:00
Running ./benchmark_integer_counting
Run on (32 X 5700 MHz CPU s)
CPU Caches:
  L1 Data 48 KiB (x16)
  L1 Instruction 32 KiB (x16)
  L2 Unified 2048 KiB (x16)
  L3 Unified 36864 KiB (x1)
Load Average: 0.03, 0.06, 0.08                                                                                 
--------------------------------------------------------------------
Benchmark                          Time             CPU   Iterations
--------------------------------------------------------------------
BM_get_most_common_number     193105 ns       192908 ns         3606

While executing the benchmark I have first encountered the warning message:

***WARNING*** CPU scaling is enabled, the benchmark real time measurements may be noisy and will incur extra overhead.

Then I had to install cpupower and execute

sudo cpupower frequency-set --governor performance

to run the benchmark without warning.

#include <chrono>
#include <fstream>
#include <print>

int get_most_frequent_number(std::ifstream& ifs) {
    int counts[1000]{};
    int ret{};
    int n{};
    while (ifs >> n) {
        if (++counts[n] >= counts[ret]) {
            ret = n;
        }
    }
    return ret;
}

int main(int argc, char** argv) {
    if (argc != 2) {
        std::println("Usage: most_frequent_number <FILE_PATH>");
        exit(1);
    }

    char* file_path = argv[1];
    std::ifstream ifs{ file_path };
    if (!ifs.is_open()) {
        std::println("Error: couldn't open {}", file_path);
        exit(2);
    }

    auto start = std::chrono::steady_clock::now();
    auto ret = get_most_frequent_number(ifs);
    auto finish = std::chrono::steady_clock::now();
    auto elapsed = std::chrono::duration_cast<
        std::chrono::duration<double>>(finish - start).count();
    std::println("{} ({:6} milliseconds)", ret, elapsed*1000);
}

• Approach: read from input file stream, keep the most frequent number in ret.

  • If reading from an input file stream wasn't such a big bottleneck, I may have written the main loop in a less clear but more performant way (using an extra variable, avoiding one extra access to counts, and avoiding to update ret on equality).

int ret{};
int ret_value{-1};
int n{};
while (ifs >> n) {
    if (auto current_value = ++counts[n]; current_value > ret_value) {
        ret = n;
        ret_value = current_value;
    }
}

• Code execution runtime: 29.587966 milliseconds.

• Machine details: AMD Ryzen 7 5700G, 16 processors, 3557.512 MHz.

• Anything I've learnt:

  • That steady_clock is better than system_clock.

  • That duration_cast would return 0 if the elapsed time is less than a second and you don't template it on a duration<double>.

Optimal solution

Here is the best result I could achieve:

#include <iostream>
#include <fstream>
using namespace std;

int fast_atoi( const char * str )
{
    int val = 0;
    while( *str ) {
        val = val*10 + (*str++ - '0');
    }
    return val;
}


int main() {
    ifstream input_stream("1M_random_numbers.txt", ios_base::in);
    string line;
    int number;
    int numbers[1000] = { 0 };
    int max_occurence = 0;
    int max_number;

    while (input_stream >> line) {
        number = fast_atoi(line.c_str());
        numbers[number]++;
        if (numbers[number] > max_occurence){
            max_occurence = numbers[number];
            max_number = number;
        }
    }
    
    cout << max_number << std::endl;
    return 0;
}

I simply convert each string to an integer, increment its occurence in a list and attribute on the fly the most frequent number. The most interesting part is the fast conversion from char to int which is achieved by fast_atoi (see https://stackoverflow.com/a/16826908/14027775). This is improving the execution time by a modest 5-10 %.

Alternate solutions

I tried to use maps or Python dictionnary thinking that the conversion to integer might slow things down too much but this was not the case at all.

Optimal solution without fast conversion

#include <iostream>
#include <fstream>
using namespace std;

int fast_atoi( const char * str )
{
    int val = 0;
    while( *str ) {
        val = val*10 + (*str++ - '0');
    }
    return val;
}


int main() {
    ifstream input_stream("1M_random_numbers.txt", ios_base::in);
    string line;
    int number;
    int numbers[1000] = { 0 };
    int max_occurence = 0;
    int max_number;

    while (input_stream >> number) {
        numbers[number]++;
        if (numbers[number] > max_occurence){
            max_occurence = numbers[number];
            max_number = number;
        }
    }
    
    cout << max_number << std::endl;
    return 0;
}

maps

#include <iostream>
#include <fstream>
#include <string>
#include <unordered_map>
using namespace std;


int main() {
    ifstream input_stream("1M_random_numbers.txt", ios_base::in);
    string line;
    std::unordered_map<string, int> occurences;
    int max_occurence = 0;
    string max_number;
    while (getline(input_stream, line)) {
        occurences[line]++;
        if (occurences[line] > max_occurence){
            max_occurence = occurences[line];
            max_number = line;
        }
    }
    
    cout << max_number << std::endl;
    return 0;
}

Python dictionnary

#!/usr/bin/env python3

number_occurences = {}
max_occurences = 0
max_number = None
with open("1M_random_numbers.txt", 'r') as f:
    for number in f:
        if number in number_occurences:
            number_occurences[number] += 1
        else:
            number_occurences[number] = 1
        if number_occurences[number] > max_occurences:
            max_occurences = number_occurences[number]
            max_number = number

print(max_number.strip())

Run times

Each command was run 100 times on a Ubuntu 24.04.3 LTS machine with i7-14700 processor.

Optimal solution: 18 ms on average

        Command being timed: "bash -c for ((i=0;i<100;i++)); do ./count_integers_int &> /dev/null; done"
        User time (seconds): 1.66
        System time (seconds): 0.08
        Percent of CPU this job got: 96%
        Elapsed (wall clock) time (h:mm:ss or m:ss): 0:01.82

Optimal solution without fast conversion: 20 ms on average

        Command being timed: "bash -c for ((i=0;i<100;i++)); do ./count_integers_int &> /dev/null; done"
        User time (seconds): 1.83
        System time (seconds): 0.09
        Percent of CPU this job got: 96%
        Elapsed (wall clock) time (h:mm:ss or m:ss): 0:01.99

maps: 91 ms on average

        Command being timed: "bash -c for ((i=0;i<100;i++)); do ./count_integers &> /dev/null; done"
        User time (seconds): 9.00
        System time (seconds): 0.13
        Percent of CPU this job got: 99%
        Elapsed (wall clock) time (h:mm:ss or m:ss): 0:09.15

Python dictionnary: 120 ms on average

        Command being timed: "bash -c for ((i=0;i<100;i++)); do ./count_integers.py &> /dev/null; done"
        User time (seconds): 11.82
        System time (seconds): 0.35
        Percent of CPU this job got: 99%
        Elapsed (wall clock) time (h:mm:ss or m:ss): 0:12.24

Using this typescript function, assuming numbers are from 0 to 999, and there is only one number which appear the most without draws (it is not said in the challenge):

  function findMostPopularNumber(): number {
    let maxNumOccurrences = 0;
    let numberMaxOccurrences = -1;

    //This method load the list of random numbers from the file
    const list: Array<number> = loadListFromFile();
    const occurrences: Array<number> = new Array(1000).fill(0);

    list.forEach(num => {
      occurrences[num] = occurrences[num] + 1;
      if (occurrences[num] > maxNumOccurrences) {
        maxNumOccurrences = occurrences[num];
        numberMaxOccurrences = num;
      }
    });

    return numberMaxOccurrences;

  }

I use an array to save the number of occurrences of each number. At any moment a number surpass the saved value of the maximum occurrences, I update the value of the max occurrences founded and the number which appears the most.

This has a cost of O(n), (being n the number of numbers in the loaded list), the minimum to get the number which appears the most. Then, we only need to use a NASA super-computer and we can get the less execution time possible ;)

My solution using MatLab accumarray

The basic idea is to use that function with:

• The input random numbers dataset as ind parameter
• An array of 1 of the same length of the input data set as the data parameter

Since accumarray does not accept 0andnegativevalue asind` parameters a pre-processing of the input data set is required:

• the 0 are replaced with the maximum input value + 1
• the negative values are replaced with their absolute value + 3

These value can be easily identified within the results and their original value can be then restored

Here the code:

Script to call the function

%
% Load the input
% The input random numbers will be used as first parameter for ACCUMARRAY
%
rand_data_set=load('1M_random_numbers.txt');
%
% Enable the profiler
profile on
%
% Call count_rand_occurr to search to find the number that appears the most
%
[str,vals]=count_rand_occurr(rand_data_set);
% Get the profile results
profile viewer
str
vals

Function count_rand_occurr

function [str,vals]=count_rand_occurr(rand_data_set)
%
% Assess the number of values
%
n_rand=numel(rand_data_set);
%
% Identfy the maximum random numner
%
the_max=max(rand_data_set);
% Add 1 to the random values equal to 0
% This because the first input SUBS must contain positive integer subscripts
rand_data_set(rand_data_set==0)=the_max+1;
%
% Enable the following line to test for negative numbers and for multiple
% max occurrence
%rand_data_set(1:1130)=-3;
%
% Identify the index of the random number < 0 (if any)
%
the_neg=rand_data_set<0;
%
% Replace the negative values with its absolute value
% This because the first input SUBS must contain positive integer subscripts
% Then add the max value + 3 to distinguish them from the values altered
% in the previous step
%
rand_data_set(the_neg)=abs(rand_data_set(the_neg))+the_max+3;
%
% Create the second input for ACCUMARRAY as an array of 1
%
data=ones(n_rand,1);
%
% Call ACCUMARRAY
B = accumarray(rand_data_set,data)';
%
% Get the MAX calculated by ACCUMARRAY
% "how_many_times" is the maximun number of repetition of one or more
% random number in the input data set
%
most_times=max(B);
%
% The indices of the elements of B equals to "most_times" aer the valuers
% of the random number with the most repetitions
%
vals=find(B==most_times);
% 
% Format the output"
%
str='the values=';
for i=1:numel(vals)
    if(vals(i)) > the_max+3
        vals(i)=(vals(i)-the_max-3)*-1;
    elseif(vals(i)) == the_max+1
        vals(i)=vals(i)-the_max-1;
    end
    str=sprintf('%s %d',str,vals(i));
end
str=sprintf('%s\nappear = %d times',str,most_times);

Results

The values= 142 appears = 1130 times

Profile

Profile Summary (Total time: 0.017 s)

Code:

#include <random>
#include <iostream>
#include <chrono>
#include <array>
#include <fstream>

std::vector<int> getNumbers(int argc, char** argv)
{
    if (argc == 1)
    {
        int totalNumbers;
        std::cout << "Enter the total number of random integers to generate: ";
        std::cin >> totalNumbers;

        std::mt19937_64 rng(std::chrono::high_resolution_clock::now().time_since_epoch().count());
        std::uniform_int_distribution<int> dist(0, 999);

        std::vector<int> numbers(totalNumbers);
        for (int i = 0; i < totalNumbers; ++i) {
            numbers[i] = dist(rng);
        }
        return numbers;
    }
    else if (argc == 2)
    {
        std::ifstream inputFile(argv[1]);
        if (!inputFile.is_open()) {
            std::cout << "Failed to open the file: " << argv[0] << std::endl;
            std::abort();
        }

        std::vector<int> numbers;
        int value;
        while (inputFile >> value) {
            numbers.push_back(value);
        }
        inputFile.close();
        return numbers;
    }
    else 
    {
        std::cout << "Invalid number of arguments." << std::endl;
        std::abort();
    }
}

int main(int argc, char** argv)
{
    std::vector<int> numbers = getNumbers(argc, argv);
    std::array<int, 1000> counts = { 0 };
    int maxCount = 0;

    auto start_time = std::chrono::high_resolution_clock::now();
    for (size_t i = 0; i < numbers.size(); ++i) {
        counts[numbers[i]]++;
        maxCount = std::max(maxCount, counts[numbers[i]]);
    }
    auto end_time = std::chrono::high_resolution_clock::now();

    auto elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time);

    std::cout << "The number(s) that appeared the most is(are): ";
    
    for (int i = 0; i < 1000; i++) {
        if (counts[i] == maxCount) {
            std::cout << i << " ";
        }
    }

    std::cout << " with a count of: " << maxCount << std::endl;
    std::cout << "Time spent on counting: " << elapsed.count()/1e6 << " seconds" << std::endl;

    return 0;
}

Explanation:

The program can be run in 2 ways:

• Pass the input text file of integers.

• Just pass the number of integers you would want to generate.

In the 1st case, it would read the text file and create a vector of numbers. In the second case, it would call C++ built in function to randomly generate given number of integers.

Once it has a vector of integers then it will create an empty array named counts of size 1000, each index is initialized with 0.

Why 1000? - Because the range of integers can only be 0 to 999.

It will treat counts array to keep the count of each integer. Once it processes all the integers, it will have maxCount.

Then it will iterate on the counts array and which index has a count equal to maxCount , it will print those.

Execution Time and Machine Details:

100_random_numbers.txt
The number(s) that appeared the most is(are): 188 208 374 546 641 694  with a count of: 2
Time spent on counting: 0 microseconds

10000_random_numbers.txt
The number(s) that appeared the most is(are): 284  with a count of: 23
Time spent on counting: 3e-06 seconds

1M_random_numbers.txt
The number(s) that appeared the most is(are): 142  with a count of: 1130
Time spent on counting: 0.000409 seconds

Machine Details:

Processor: 13th Gen Intel(R) Core(TM) i9-13900K, 3000 Mhz, 24 Core(s), 32 Logical Processor(s)

Installed Physical Memory (RAM) 64.0 GB

Compiler Details:

MSVC 19.44.35217 for x64

My answer to the challenge

#include <stdio.h>
#include <stdlib.h>

#define NUMBERS_RANGE_END    1000

/*
Given a list of random integer numbers between 0 and 999 (=NUMBERS_RANGE_END-1),
finds the (tied) number(s) that appears the most.
- Parameters: 
  [char array string] filepath - Path of the text file containing the list of integer numbers 
- Returns: 
  [dynamically allocated int array] - Negative one (-1) terminated array of (tied) most common integer numbers
*/
int *find_most_common_integer_numbers(const char *filepath){    
    int *counters = calloc(NUMBERS_RANGE_END, sizeof *counters); // Counters for each number
    if (!counters) exit(EXIT_FAILURE);
    int biggest_counter = 0;                                     // Biggest counter
    int number = 0;                                              // Current number
    
    // Count number of times each number appears in the list and find the biggest counter:
    FILE *f = fopen(filepath, "r");  // Open list of 1 million random integer numbers
    if (!f) exit(EXIT_FAILURE);
    while (fscanf(f, "%d", &number) == 1) {        // For each number in the list:
        counters[number]++;                        // Increment the number's counter;
        if (counters[number] > biggest_counter) {  // If the counter of the current number is bigger
            biggest_counter = counters[number];    // store it as the biggest counter.
        }
    }
    fclose(f);
    
    // List all the (tied) most common integer numbers:
    int *most_common = malloc((NUMBERS_RANGE_END + 1) * sizeof *most_common); // Most common integer number(s)
    if (!most_common) exit(EXIT_FAILURE);
    int i = 0;
    for (number = 0; number < NUMBERS_RANGE_END; number++) { // For all numbers in the range:
        if (counters[number] == biggest_counter){  // If the number's counter equals the biggest counter
            most_common[i] = number;               // add the number to the list.
            i++;
        }
    }
    most_common[i] = -1; // Indicates the end of the list of (tied) most common integer numbers
    
    free(counters);
    return most_common;
}

How it works

My solution is very simple and straightforward...

There are 1000 possible distinct integer numbers in the list, going from 0 to 999, so the function uses 1000 counters representing each possible number respectively to count how many times each number appears in the list.

And as it goes though the list of integers it also keeps track of and updates the value of the biggest counter, such that by the end of the list, the value of the biggest counter is known.

Finally, it returns an array containing all the numbers whose counter equals the biggest counter, by going through the list of counters and adding each number with the biggest counter to the array (and adding a -1 at the end to indicate the end the sequence of most common numbers found).

What I did to optimize it

The basic logic of the program has remained unchanged from its inception, however many attempts to make it faster were made, most of which barely improved its performance if at all, and some of which made the code significantly slower.

Here are some of the most notable attempts and their results:

1. Decrease from 2 assignment operations to 1 assignment each time a bigger counter is found while going though the list - Had a minute improvement in the performance, in the thousands of a second.

2. Loading the entire files' content to memory, with fread, as a long string, and then parsing it using sscanf (instead of fscanf to read from the file) - Made the execution much slower, by several seconds. (I couldn't conclude why)

3. Using statically allocated memory for the array of counters, instead of dynamically allocated memory - The execution was consistently slower by a few thousands of a second (contrary to my expectation)

Execution runtime

Testing method

I've utilized two methods to time the execution of the code, mentioned in this stack overflow question: One using the function clock() from the time.h standard library, and another using the function get_time() which is system dependent, but has versions for Windows and Linux.

The testing code executes the function 1000 times (it's possible to change it by altering the BENCHMARKS macro), and calculates the average, maximum and minimum times.

And here are the respective testing codes:

clock()

#include <math.h>
#include <time.h>

#define BENCHMARKS    1000

int main() {
    double total_time = 0.0;
    double max_time = 0.0;
    double min_time = INFINITY;
    double elapsed_time = 0.0;
    printf("Bechmarking %d times...\n", BENCHMARKS);
    FILE *output = fopen("output.txt", "w");
    for (int i = 0; i < BENCHMARKS; i++) { 
        clock_t start_time = clock(); //Start time
        int *most_common = find_most_common_integer_numbers("1M_random_numbers.txt");
        elapsed_time = ((double)(clock() - start_time)) / CLOCKS_PER_SEC; // Elapsed time
        
        total_time += elapsed_time;
        if (elapsed_time > max_time) max_time = elapsed_time;
        if (elapsed_time < min_time) min_time = elapsed_time;
        
        printf("%5d -> The most common integer number(s) in the list: %d", i+1, most_common[0]);
        for (int j = 1; most_common[j] > 0; j++) {
            printf(", %d", most_common[j]);
        }
        printf("\n");
        free(most_common);
    }
    fclose(output);
    double average_time = total_time / BENCHMARKS;
    printf("\nMaximum time: %f seconds\n", max_time);
    printf("Average time: %f seconds\n", average_time);
    printf("Minimum time: %f seconds\n", min_time);
    
    
    return EXIT_SUCCESS;
}

get_time()

#include <math.h>

#ifdef WIN32

#include <windows.h>
double get_time()
{
    LARGE_INTEGER t, f;
    QueryPerformanceCounter(&t);
    QueryPerformanceFrequency(&f);
    return (double)t.QuadPart/(double)f.QuadPart;
}

#else

#include <sys/time.h>
#include <sys/resource.h>

double get_time()
{
    struct timeval t;
    struct timezone tzp;
    gettimeofday(&t, &tzp);
    return t.tv_sec + t.tv_usec*1e-6;
}

#endif


#define BENCHMARKS    1000

int main() {
    double total_time = 0.0;
    double max_time = 0.0;
    double min_time = INFINITY;
    double elapsed_time = 0.0;
    printf("Bechmarking %d times...\n", BENCHMARKS);
    FILE *output = fopen("output.txt", "w");
    for (int i = 0; i < BENCHMARKS; i++) { 
        double start_time = get_time(); // Start time
        int *most_common = find_most_common_integer_numbers("1M_random_numbers.txt");
        elapsed_time = get_time() - start_time; // Elapsed time
        
        total_time += elapsed_time;
        if (elapsed_time > max_time) max_time = elapsed_time;
        if (elapsed_time < min_time) min_time = elapsed_time;
        
        printf("%5d -> The most common integer number(s) in the list: %d", i+1, most_common[0]);
        for (int j = 1; most_common[j] > 0; j++) {
            printf(", %d", most_common[j]);
        }
        printf("\n");
        free(most_common);
    }
    fclose(output);
    double average_time = total_time / BENCHMARKS;
    printf("\nMaximum time: %f seconds\n", max_time);
    printf("Average time: %f seconds\n", average_time);
    printf("Minimum time: %f seconds\n", min_time);
    
    
    return EXIT_SUCCESS;
}

Testing system specs

Processor: AMD Ryzen 7 5700G
RAM: 8 GiB - DDR4 3200 MT/s
GPU: AMD Radeon(TM) Graphics (495.77 MiB) [Integrated]
Storage: 256 GiB NVME SSD
OS: Windows 11 Pro x86_64 - 10.0.26100.6584 (24H2)
Compiler: gcc.exe (Rev8, Built by MSYS2 project) 15.2.0

Runtime results

clock()

Maximum time: 0.100000 seconds
Average time: 0.095776 seconds
Minimum time: 0.094000 seconds

get_time()

Maximum time: 0.109907 seconds
Average time: 0.095393 seconds
Minimum time: 0.093554 seconds

Solution with Java 25, Lock-free via actor-model approach:

import java.io.RandomAccessFile;
import java.nio.ByteBuffer;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.channels.FileChannel.MapMode;

/**
 * Concurrent Processing, Lock-free via actor-model approach
 * <p>
 * 1. Process concurrently            =~ 67ms
 *    - Interestingly slower than the single thread version
 *    - Spawning platform threads costs a lot (~20ms) and our dataset (1M) is still relatively small.
 *      However, if we assume the dataset is arbitrarily large (like 1 billion) then multi-thread processing should outperform.
 *    - Using virtual threads didn't help, worse in performance ~88ms
 * 2. Compile into native (25-graal)  =~ 5.8ms (slightly better than the single thread version)
 * 3. Added internal timer to exclude startup cost =~ 0.753ms (Impressive! it looks like even if it's natively compiled, there is still a lot of cost to spin up)
 */
public class Solution3 {

  static final int THREAD_COUNT = Integer.getInteger("threads",2 * Runtime.getRuntime().availableProcessors());
  static final int[] NUMBER_MAP = new int[1000];

  static class Actor extends Thread {

    // collecting numbers into an array eleminates a lot of operations like auto-boxing, hash calculation, boundary checks, etc.
    // mapped one-to-one with indices is possible since our data set is limited [0 - 999] Therefore, this eleminates hash calculation because no clashes possible
    final int[] segmentMap = new int[1000];

    final ByteBuffer segment;

    Actor(ByteBuffer segment) {
      this.segment = segment;
    }

    @Override
    public void run() {
      byte b;
      int pos = 0; // relative to segment
      int current = 0; // current number
      final int limit = this.segment.limit();
      while (pos++ < limit) {
        if ((b = this.segment.get()) == '\n') { // read & check each byte
          this.segmentMap[current]++; // increment
          current = 0; // reset current
          continue;
        }
        current = 10 * current + (b-'0');
      }
    }

  }

  static int findSegmentStart(ByteBuffer segment) {
    if (segment == null)
      return 0;
    // read the segment to backwards until find the first '\n'
    int pos = segment.limit() - 1;
    while (segment.get(pos) != '\n') {
      pos--;
    }
    return pos + 1;
  }

  static long findSegmentSize(long fileSize, long start, int segmentSize) {
    // find a safe ending when segments aren't evenly distributed
    if ((start + segmentSize) > fileSize)
      return segmentSize - (start + segmentSize - fileSize);
    if ((start + segmentSize) > (fileSize - segmentSize))
      return fileSize - start;
    return segmentSize;
  }

  public static void main(String[] args) throws Exception {

    final long time = System.nanoTime(); // internal benchmark to exclude startup cost

    final String inputFile = args[0];
    final FileChannel channel;
    final long fileSize;
    final Actor[] actors = new Actor[THREAD_COUNT];
    try (final var file = new RandomAccessFile(inputFile, "r")) {
      channel = file.getChannel();
      fileSize = channel.size();
      final int segmentSize = Math.toIntExact(fileSize / THREAD_COUNT); // each segment must be lower than Integer.MAX_VALUE
      long start = 0;
      MappedByteBuffer prev = null;
      for (int i = 0; i < THREAD_COUNT; i++) {
        start += findSegmentStart(prev); // update the next start pos
        final long size = findSegmentSize(fileSize, start, segmentSize);
        final MappedByteBuffer segment = channel.map(MapMode.READ_ONLY, start, size);
        final var actor = (actors[i] = new Actor(segment));
        actor.start(); // run the actor
        prev = segment; // keep the segment to calculate other's start index
      }
    }

    for (Actor actor : actors) {
      actor.join(); // wait all threads to complete
    }

    int found = 0;
    int maxOccurance = 0;
    // merge partial results into the global and find the max occured number
    for (int i = 0; i < NUMBER_MAP.length; i++) {
      for (int j = 0; j < THREAD_COUNT; j++) {
        final var actor = actors[j];
        final var sum = (NUMBER_MAP[i] += actor.segmentMap[i]);
        if (sum > maxOccurance) {
          maxOccurance = sum;
          found = i;
        }
      }
    }

    // print result
    final long took = (System.nanoTime() - time) / 1000;
    System.out.println("Found " + found + ", max: " + maxOccurance + ", took: " + took + "µs");
  }

}

The answer is for 1M record set:

Found 142, max: 1130

Here is how I came up with the final solution, the timing is measured against 1M record set:

1. Single-thread naive solution with MappedByteBuffer using built-in HashMap ~= 81ms
2. Change HashMap by a custom integer array ~= 52ms
3. Process in parallel via actor-model, no synchronization and locks ~= 67ms (Interestingly, slower than single-thread approach) Each thread uses its own number array, hotspot region is processed in parallel, no locking. Finally, we merge all numbers and sum them into a single array in the main thread. This last part can be ignored since we only have a constant number set [0-999]. So, it's o(n) where n = 1000 (constant)
4. I realized JVM initialization and creating platform threads cost ~= 20ms. Possibly, our 1M record set is still relatively small. Therefore, this approach is slower than the single-thread approach with the 1M record set. However, this should outperform with larger record sets (e.g., n > 100M).
5. Cut the initialization cost by compiling into native. Hell yeah! Now, this approach takes the lead ~= 5.8ms (compared to Single-thread approach in native, which is 6.9ms)
6. Added an internal benchmark to exclude startup cost ~= 0.753ms (Impressive! it looks like even if it's natively compiled, there is still a lot of cost to spin up)

I run the tests on Mac Mini M4 CPU (ARM 10 cores), 16GB ram. The benchmarking is done with hyperfine. Please note that the cost for loading the file (IO cost) and parsing the digits are also included in timings.

BONUS: I run this solution with 1 billion records for fun. It takes under 0.5 seconds! See my detailed comparison and some other possible solutions on Github

UPDATE: I added an internal timer to see the execution time excluding the startup cost:

Found 142, max: 1130, took: 753µs

I hope this contributes to the community. Happy coding!

Here is my entry. I tried the good ol' Python to see exactly how it behaves for the quite simple task.

Following is my code:

def most_frequent(list_of_numbers):
    counts = [0] * 1000
    for n in list_of_numbers:
        counts[n] += 1

    max_count = -1
    max_index = -1
    for i, c in enumerate(counts):
        if c > max_count:
            max_count = c
            max_index = i

    return max_index, max_count

Explanation: Essentially I create a 0-filled fixed with 1000 positions (0 to 999) and just add one to a given position when found the number in the numbers file. Since the lookup is almost immediate to the position, there is no overhead. The problem then is only find the max count and return the index (the number that appered most).

For the optimization, I tried first a version with lamba like index = max(range(len(numbers)), key=lambda x: numbers[x])` to find the index of my array, but I was surprised that the iteration works better at the end.

Runtime: It took `0.03866124153137207 seconds` in my machine ( Intel Core i7, 64GB RAM, Windows 10, Python 3.12.9) to find the result of the 1M file, wich was "Result: (142, 1130)"

I've learned: For long arrays, apparently lambdas introduce some overhead, what I was not expecting. I didn't try to optimize the I/O part of the code.

Full code:

import time


def read_numbers(filename):
    with open(filename, "r") as f:
        return [int(line) for line in f]

def most_frequent(list_of_numbers):
    counts = [0] * 1000
    for n in list_of_numbers:
        counts[n] += 1

    max_count = -1
    max_index = -1
    for i, c in enumerate(counts):
        if c > max_count:
            max_count = c
            max_index = i

    return max_index, max_count


numbers = read_numbers("1M_random_numbers.txt")

start = time.time()
result = most_frequent(numbers)
end = time.time()

print("Result:", result)
print("Elapsed time:", end - start, "seconds")

The most repeated 1,000,000 number in list is 142 with the frequency of 1130.

The code on average took 13.55ms on a 1,000 run.
Min duration on the 1000 run was 9.8ms and max duration was 21.3ms.

In below line nums is a 1,000,000 number array list.

const myNumberList = nums;

You can make it so that its a random number by commenting above line and uncommenting this line

// const myNumberList = generateRandomNumberList(numbersToBeGenerated, minNumberToBeGenerated, maxNumberToBeGenerated);

Below is full source code

function generateRandomNumberList(numberOfItems, minNumber, maxNumber) {
    var generatedNumberList = [];
    for (var i = 0; i < 1000000; i++) {
        generatedNumberList.push(Math.floor(Math.random() * (maxNumber - minNumber) + minNumber));
    }
    return generatedNumberList;
}


function findAvgProcessTime(numberList, numberOfRuns) {
    var sumOfDurations = 0;
    var minDuration = 0;
    var maxDuration = 0;

    for (var i = 0; i < numberOfRuns; i++) {
        const tempDuration = Number(findMostRepeatedNunbers(numberList).durationMs);
        if (i == 0) { minDuration = tempDuration; maxDuration = tempDuration; }

        if (minDuration > tempDuration) {
            minDuration = tempDuration;
        }

        if (maxDuration < tempDuration) {
            maxDuration = tempDuration;
        }

        sumOfDurations += tempDuration;
    }

    return { avgMs: (sumOfDurations / numberOfRuns).toFixed(6), minTime: minDuration, maxTime: maxDuration };
}


function findMostRepeatedNunbers(numberList) {
    var result =
    {
        startTime: 0,
        endTime: 0,
        durationMs: 0,
        mostRepeatedNumbers: [],
        highestRepeatRequency: 0
    };

    result.startTime = performance.now();


    // counts will be used as dictionary that can be used to retrive count of each number 
    // for example [0: 5, 1: 2, 3, 21, 4, 1] when you use counts[0] it means number 0 has been repeated 5 times in the list of nums
    var counts = Object.create(null);

    // Loop through all numbers in nums list
    for (const n of numberList) {

        // c will contains frequncy of number if the number is in counts dictionary or or 0 if the number has not been repeated yet
        // then c will be added by one
        const c = (counts[n] = (counts[n] || 0) + 1);

        // if c is bigger than highest repeated frequency then swithc maxCount with c and then set maxKeys as the number that has been repeated c times
        if (c > result.highestRepeatRequency) {
            result.highestRepeatRequency = c;
            result.mostRepeatedNumbers = [Number(n)];
        } else if (c === result.highestRepeatRequency) { // if c has same value as highest frequency then add number to maxKeys as this number also now the most repeatednumber
            result.mostRepeatedNumbers.push(Number(n));
        }
    }

    result.endTime = performance.now();
    result.durationMs = (result.endTime - result.startTime).toFixed(6);

    return result;
}

const numbersToBeGenerated = 1000000;
const minNumberToBeGenerated = 0;
const maxNumberToBeGenerated = 999;

// const myNumberList = generateRandomNumberList(numbersToBeGenerated, minNumberToBeGenerated, maxNumberToBeGenerated);
const myNumberList = nums;
const result = findMostRepeatedNunbers(myNumberList);

const numberOfRuns = 1000;
const avgPricessTimeMs = findAvgProcessTime(myNumberList, numberOfRuns);

console.log("Most frequent number(s):", result.mostRepeatedNumbers, "with count:", result.highestRepeatRequency);
console.log("Min process time:", avgPricessTimeMs.minTime, "ms");
console.log("Max process time:", avgPricessTimeMs.maxTime, "ms");
console.log('Average process time:', avgPricessTimeMs.avgMs, "ms", " with ", numberOfRuns, " of runs");
console.log("Number of numbers in the list:", myNumberList.length);

Without checking if the input array actually has 1 million elements and if they are actually integers between 0 and 999, the fastest native code in VBA is probably the following:

Public Function FindMostFrequentInt(ByRef integers() As Long) As Long
    Dim i As Long
    Dim j As Long
    Dim arrCount(0 To 999) As Long
    Dim maxCount As Long
    Dim mostFrequent As Long
    '
    For i = LBound(integers) To UBound(integers)
        j = integers(i)
        arrCount(j) = arrCount(j) + 1
    Next i
    For i = LBound(arrCount) To UBound(arrCount)
        If arrCount(i) > maxCount Then
            maxCount = arrCount(i)
            mostFrequent = i
        End If
    Next i
    FindMostFrequentInt = mostFrequent
End Function

The code above basically uses each input integer as an index into an array that stores the a count. E.g. for integer 3 we index into arrCount(3) and we increase the count by one. Once all integers are counted, we simply traverse the count array and find the maximum count.

For a million integers, the above only takes about 13 milliseconds on a Win11, 13th Ge Intel(R) Core(TM) i7-13800H with 32GM of RAM.

Quick test:

Sub TestSpeed()
    Const size As Long = 1000000
    Dim integers() As Long
    Dim i As Long
    Dim c As Currency
    '
    ReDim integers(0 To size - 1)
    For i = 0 To size - 1
        integers(i) = Int(Rnd() * 1000)
    Next i
    c = AccurateTimerMs
    Debug.Print "Most frequent: " & FindMostFrequentInt(integers)
    Debug.Print "Milliseconds: " & Format$(AccurateTimerMs - c, "#,##0")
End Sub

where the AccurateTimerMs is part of the excellent VBA-AccurateTimer module.

#include<stdio.h>
#include<stdlib.h>

void count_ints(const char* file_name) {
    FILE* file = fopen(file_name, "r");

    int arr[1000000];
    int n = sizeof(arr) / sizeof(arr[0]);
    int c = 0;

    while(!feof(file)) {
        fscanf(file, "%d", &arr[c]);
        c++;
    }
    // Hash table
    int hash[1000] = {0};
 
    int lv = 0, lvi = 0;

    for (int j=0; j<n; j++) {
        hash[arr[j]]++;
    }
 
    for (int i=0; i < 1000; i++) {
        if (lv <= hash[i]) {
            lv = hash[i];
            lvi = i;
        } 
    }

        printf("%d occurs %d times\n", lvi, lv);

    fclose(file);
}

int main() {

    count_ints("/home/russellb/Development/c_devel/play/fcountr/1M.txt");

    return 0;

Approach
1. Read the input file
2. Create hashtable
3. Find the maximum from the hash tableInitial approach was to use binary search. Later I learnt hash tables can be used for this problem and adopted it.

Result 142 occurs 1130 times

**Execution time**
real    0m00.11s
user    0m00.10s
sys 0m00.00s



Machine details:

CPU: Intel i5-3230M (4 cores)

OS: GNU/Linux

RAM: 8GM DDR3


}

Approach

1. Read in the file

2. Create hashmap of counts

3. Find the most occuringg value

CPU: i5-3235M

RAM: 8GB DDR3

OS: GNU/Linux

Execution times

\> time ./countr_ic

142 occurs 1130 times

real 0m00.10s

user 0m00.10s

sys 0m00.00s

Max finding is not optimized and working on it.

Hi there:

I am a rookie programmer trying to improve my code every day. Here is my proposal for this challenge.

after reading the conditions of this challenge and spend some time writing a code with a different approaching, like generate my own random list I think now I took the right path. I have learned how to open *.txt files for reading. Also, I learned about how to count occurrences and what datatypes or what counting methods is faster for this purpose. Here I am leaving a small comparison table with the time spend for ten times tries on each datatype (tuple and list):

TUPLE():        LIST[]: DIF:    DATATYPE

1 0.1231167316436760 0.1315355300903320 -0.0084187984466560 TUPLE 2 0.1420800685882560 0.1369962692260740 0.0050837993621820 LIST 3 0.1343727111816400 0.1329193115234370 0.0014533996582030 LIST 4 0.1137866973876950 0.1245462894439690 -0.0107595920562740 TUPLE 5 0.1202738285064690 0.1235520839691160 -0.0032782554626470 TUPLE 6 0.1204180717468260 0.1273376941680900 -0.0069196224212640 TUPLE 7 0.1213290691375730 0.1169397830963130 0.0043892860412600 LIST 8 0.1230452060699460 0.1204888820648190 0.0025563240051270 LIST 9 0.1179533004760740 0.1396424770355220 -0.0216891765594480 TUPLE 10 0.1211564540863030 0.1248850822448730 -0.0037286281585700 TUPLE 0.1237532138824460 0.1278843402862550
-3.2% TUPLE 6 LIST 4 -33.3%

In a summary: the Tuple's time was in average -3.2 faster than of a list's time, and when compare how many times was one faster than the other, the Tuple was 33% faster than the list.

Here is my code:

#Create a Tuple numbers = () #working with the file. Open the file and read the content with open(file_path, 'r') as file: #start the timer st_time = time() #instantiate the list with numbers from the file numbers = [num for num in file.read().strip().split()] #Count the occurrences of each number contador = Counter(numbers) #Get the most common element most_common_elements = contador.most_common(1) #Format the output formatted = ', '.join(f"{key} = {value}" for key, value in most_common_elements) #Calculate the time taken time1 = time() - st_time
#Print the results print("Most repeated #: ", formatted, " #Items: ", len(contador), "Time spend: ", time1, end='\n')

If you want you to use this code with a List, just change numbers = () by numbers = [] (however, I know that know that)

My laptop is:

13th Gen Intel(R) Core(TM) i7-1355U (1.70 GHz) 16 GB Ram Windows 11 Home

Regards;

My results are

Most common of 100 random numbers: 546, took 0.0004891000007773982 s
Most common of 10000 random numbers: 284, took 0.001788400000805268 s
Most common of 1M random numbers: 142, took 0.1768207999994047 s

My machine is an asus computer, with a processor: 11th Gen Intel(R) Core(TM) i5-11400H @ 2.70GHz (2.69 GHz) and 16 GB of RAM

My approach is simply using the Counter built-in class in Python. I figured it would be already optimized.

My code is available on github at https://github.com/genevieve-le-houx/SO_challenge_6_integer_counting

My code is :

import timeit
from collections import Counter
from pathlib import Path
from typing import List


def read_numbers(filepath: Path) -> List[int]:
        list_numbers = []
        with open(filepath, "r", newline="\n") as f:
            for line in f:
                list_numbers.append(int(line))

        return list_numbers

def count_numbers(list_numbers: List[int]) -> int:
    c = Counter(list_numbers)
    return c.most_common(1)[0][0]

def find_most_common_from_file(filepath: Path) -> int:
    list_numbers = read_numbers(filepath)
    return count_numbers(list_numbers)

def main():
    most_common_100 = find_most_common_from_file(Path("100_random_numbers.txt"))
    most_common_10000 = find_most_common_from_file(Path("10000_random_numbers.txt"))
    most_common_1M = find_most_common_from_file(Path("1M_random_numbers.txt"))

    time_100 = timeit.timeit(lambda: find_most_common_from_file(Path("100_random_numbers.txt")), number=1)
    time_10000 = timeit.timeit(lambda: find_most_common_from_file(Path("10000_random_numbers.txt")), number=1)
    time_1M = timeit.timeit(lambda: find_most_common_from_file(Path("1M_random_numbers.txt")), number=1)

    print(f"Most common of 100 random numbers: {most_common_100}, took {time_100} s")
    print(f"Most common of 10000 random numbers: {most_common_10000}, took {time_10000} s")
    print(f"Most common of 1M random numbers: {most_common_1M}, took {time_1M} s")



if __name__ == '__main__':
    main()

This was an interesting challenge. I tried to manually implement a counter by iterating over each number and keep track of the count in a dictionnary, but figured a built-in class would be faster.

This is my Haskell submission. It will not be the fastest here, as my parallel implementation in C++ was ~4 times faster. But it was instructive, since my first Haskell try was ~20 times slower than C++. What I learned:

1. Use Data.ByteString.Char8 instead of the naive read. I expected reading the file to be the most problematic, and it still is the slowest part. I just can't get ahead with optimizing it any more.

2. Used an unboxed vector to accumulate the counts. It gave a little speedup. Maybe I can get more with mutable vectors?

3. Compiling with -O2 had some effect, but not a big one.

4. My first time using the GHC profiler.

Using ghc-9.6.6, vector-0.13
CPU: i7-1260P

Time: ~0.08 sec (avg. over 10 samples)

{-#LANGUAGE TupleSections #-}

module Main (main) where

import Data.Maybe (fromJust)
import Data.List (unfoldr)
import Data.Char (isDigit)

import qualified Data.ByteString.Char8 as B
import qualified Data.Vector.Unboxed as V

-- Functions are broken out for a more granular profiler output
counts :: [Int] -> V.Vector Int
counts lst = V.unsafeAccum (+) (V.replicate 1000 0) (map (,1) lst)

getCounts :: IO (V.Vector Int)
getCounts = do
    numStrs <- B.readFile "data/1M_random_numbers.txt"
    let nums = unfoldr (B.readInt . B.dropWhile (not . isDigit)) numStrs
    return $ counts nums

main :: IO ()
main = do
    cnt <- getCounts
    let maxOccurrence = V.foldr max 0 cnt

    print $ fromJust (V.findIndex (== maxOccurrence) cnt)

For comparison, a naive C++ version without parallelization, AVX, or any bells and whistles (compiled with GCC, using C++23 standard):
Time: ~0.024 sec

#include <fstream>
#include <string>
#include <algorithm>

#include <print>
#include <cstdlib>

int main() {
    std::ifstream numStrs("../haskell/intcount/data/1M_random_numbers.txt");

    if (!numStrs.is_open()) {
        std::println("File open failed");
        return EXIT_FAILURE;
    }
    
    // Just plunk it on the stack, fastest for small vectors like this
    int accum[1000];
    std::fill(accum, accum + 1000, 0);

    std::string line;
    while (std::getline(numStrs, line)) {
        int num = std::atoi(line.data());
        accum[num]++;
    }

    int* maxOccurrence = std::max_element(accum, accum + 1000);
    std::println("Mode: {}", (int)(maxOccurrence - accum));

    return EXIT_SUCCESS;
}

Code Execution Runtime

• 0.0009 second or 0.9 millisecond or 900-1100 microseconds

Output:

highest occuring number is = 142
highest count = 1130
Execution time in seconds: 0.0009 seconds
Execution time in milliseconds: 0.9138 milliseconds
Execution time in microseconds: 913 microseconds

Code:

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <chrono>
#include <omp.h>
#include <cstdint>
#include <vector>
#include <iomanip>

using namespace std;


const string FILE_NAME = "1M_random_numbers.txt";
const int NUMBERS_LENGTH = 1000000;


void readFileIntoArray(string name, int* arr)
{
    ifstream file(FILE_NAME);

    if (!file)
    {
        cerr << "Error opening file!" << endl;
        return;
    }

    stringstream ss;
    ss << file.rdbuf();

    int count = 0;
    string line;

    // Now parse from stringstream like it’s a file
    while (getline(ss, line) && count < NUMBERS_LENGTH)
    {
        arr[count++] = stoi(line);
    }
}

int main()
{
    const int THREADS = 4;
    int* numbers = new int[NUMBERS_LENGTH] { 0 };

    readFileIntoArray(FILE_NAME, numbers);

    // recording start time
    auto start = chrono::high_resolution_clock::now();

    // constraint from question
    const int maxNumber = 999;

    const int RANGE = maxNumber + 1;

    // used as commulative count
    int globalCount[RANGE] = { 0 };

    // static 2 dim array to be used by threads, so each thread counts separate
    static int threadLocals[THREADS][RANGE] = { 0 };

    // using openMP for parallel execution using threads
    #pragma omp parallel num_threads(THREADS)
    {

        int tid = omp_get_thread_num();

        // get a pointer to the thread's respective count array
        int* local = threadLocals[tid];

        #pragma omp for
        for (int i = 0; i < NUMBERS_LENGTH; i++) {
            int num = numbers[i];
            local[num]++;
        }
    }

    // merge the counts from every thread's local counts
    for (int i = 0; i < THREADS; i++) {
        for (int j = 0; j < RANGE; j++) {
            globalCount[j] += threadLocals[i][j];
        }
    }

    int highestCount = 0;
    int highestOccuringNumber = 0;

    // check which number has the highest count in global count array
    for (int i = 0; i < RANGE; i++)
    {
        if (globalCount[i] > highestCount) {
            highestCount = globalCount[i];
            highestOccuringNumber = i;
        }
    }


    auto end = chrono::high_resolution_clock::now();

    auto durationMicro = chrono::duration_cast<chrono::microseconds>(end - start);
        auto durationMilli = chrono::duration<double, milli>(end - start);
        auto durationSeconds = chrono::duration<double>(end - start);

        cout << "highest occuring number is = " << highestOccuringNumber << endl;
        cout << "highest count = " << highestCount << endl;
        cout << fixed << setprecision(4) << "Execution time in seconds: " << durationSeconds.count() << " seconds" << endl;
        cout << fixed << setprecision(4) << "Execution time in milliseconds: " << durationMilli.count() << " milliseconds" << endl;
        cout << "Execution time in microseconds: " << durationMicro.count() << " microseconds" << endl;
        }

Explanation:

• Count Sort Strategy

I used count sort strategy for finding out the highest occuring number as the constraint suggests that numbers can only be between 0-999, which makes it perfect case for count sort as count sort gives best performance when the range of numbers is significantly less than total numbers that are 1M in this case.

I first used linear execution and it gave me 2000-2100 microseconds (2 milliseconds) execution time. Then I added parrallel execution with the help of OpenMP in C++. Running with 4 threads in parallel gave me 900-1100 microseconds (1 millisecond) execution times, meaning I cut the runtime by 50% by applying parallel execution. We can increase threads based on the quality of CPU but 4 threads seems like a reasonable amount as most of the current CPUs can run 4 threads in parallel easily.

• Why I didn't use HashMap

Array pointers give constant O(1) access to the indices and since, the range is just 0-999, array consumes way less memory than a hashmap. If the range was way huge like 0-1B or range wasn't defined, then using HashMap would have been a wiser choice.

Details about my machine

• CPU: Intel Core i5 9600KF
• RAM: DDR4-3200 24GB
• GPU: GIGABYE GeForce GTX 1080
• Motherboard: GIGABYTE Z390 M GAMING

What I Learned:

I got to learn and explore parallel programming using OpenMP, I researched about how I can achieve parallel execution and OpenMP makes the work easy for parallel programming.

import random

import time

from collections import Counter

\# Generate 1 million random integers between 0 and 999

numbers = \[random.randint(0, 999) for \_ in range(1_000_000)\]

\# Start performance measurement

start_time = time.time()

\# Find the most frequent number using Counter

counter = Counter(numbers)

most_common_num, freq = counter.most_common(1)\[0\]

\# End performance measurement

end_time = time.time()

print(f"Most frequent number: {most_common_num} (appears {freq} times)")

print(f"Execution Time: {end_time - start_time:.4f} seconds")

This simple swift-sh script solves the problem.

Memory is cheap these days, and 1M numbers is not a lot. We load the whole file in memory, iterate the lines and store the number of occurrences of each number in a dictionary. We keep the current key which has the maximum of occurrences found, as well as the current maximum number of occurrences found. For every line of the file we update these variables if needed. When we have finished iterating the lines, we have the number with the maximum number of occurrences.

The dictionary keys are Data directly, not Ints. This allows not parsing the numbers, as we never need the value of the numbers. Also we instantiate the dictionary with a minimum capacity of 1000 to avoid having to grow it later.

This solution is probably not optimal; I coded that rapidly in vim…

#!/usr/bin/env swift sh

import Foundation

import ArgumentParser /* @apple/swift-argument-parser ~> 1.6 */
import StreamReader   /* @Frizlab/stream-reader       ~> 3.6 */



_ = await Task{ await Main.main() }.value
struct Main : AsyncParsableCommand {

   @Argument
   var file: String

   func run() async throws {
      let fileURL = URL(fileURLWithPath: file)
      let fh = try FileHandle(forReadingFrom: fileURL)
      let streamReader = FileHandleReader(stream: fh, bufferSize: 50 * 1024 * 1024, bufferSizeIncrement: 1024)
      var values = Dictionary<Data, Int>(minimumCapacity: 1000)
      var maxKey = Data()
      var maxValue = 0
      while let (line, _) = try streamReader.readLine() {
         let value = (values[line] ?? 0) + 1
         values[line] = value
         if value > maxValue {
            maxValue = value
            maxKey = line
         }
      }
      try FileHandle.standardOutput.write(contentsOf: Data("Max occurrences: ") + maxKey + Data("\n".utf8))
   }

}

#include <fstream>
#include <iostream>
#include <vector>
#include <string>
#include <chrono>

using namespace std;

//Faster way to convert string to int than using std::stoi
unsigned int string_to_uint(string str){
    unsigned int output = 0;
    for (char& c : str){
        output = output*10  + (c - '0');
    }
    return output;
}

int main(){

    //Get start time
    auto start_time = chrono::high_resolution_clock::now();

    string filename = "1M_random_numbers.txt";
    ifstream inputfile(filename);

    //Values range from 0 to 999
    const unsigned int NUM_POSSIBLE_VALUES = 1000;

    /*Create array where each index corresponds to a possible value in 
    the text file*/
    unsigned int counts[NUM_POSSIBLE_VALUES] = {0};

    /*Loop through each line of the file*/
    string line;
    while (getline(inputfile, line)){
        /*Convert string to int to access index of 'counts' and 
        increase count by 1*/
        counts[string_to_uint(line)]++;
    }

    /*Create vector to keep track of all numbers tied with the highest 
    count. Initialize to value at index 0, because the count at index 
    0 will start as the highest until we compare with the next 
    index.*/
    vector<unsigned int> mostCommonNumbers = {0};
    unsigned int highestCount = counts[0];

    /*Loop through 'counts' array (starting at index 1) to determine 
    which index has the highest count*/
    for (int i=1; i < NUM_POSSIBLE_VALUES; i++){
        unsigned int val = counts[i];
        if (val == highestCount){
            //Tied with highestCount, so add index to vector
            mostCommonNumbers.push_back(i);
        } else if (val > highestCount){
            //New highest count
            mostCommonNumbers.clear();
            mostCommonNumbers.push_back(i);
            highestCount = val;
        }
    }

    cout << "Highest Count = " << highestCount << endl;
    cout << "Most common number(s):" << endl;
    for (unsigned int element : mostCommonNumbers){
        cout << element << endl;
    }

    inputfile.close();

    //Get end time and calculate elapsed time
    auto end_time = chrono::high_resolution_clock::now();
    auto elapsed_time =
        chrono::duration_cast<std::chrono::duration<double>>
                                            (end_time - start_time);

    cout<<"Elapsed time: "<<elapsed_time.count()<<" seconds"<< endl;

    return 0;

}

Output:

Highest Count = 1130
Most common number(s):
142
Elapsed time: 0.0618517 seconds

Windows 11 Pro (version 24H2)
Processor: Intel(R) Core(TM) i5-10505 CPU @ 3.20GHz (3.19 GHz)
Installed RAM: 16.0 GB (15.7 GB usable)
System type: 64-bit operating system, x64-based processor
Average Execution Time: 62ms

I'm not a very experienced programmer, but came across this challenge and thought it looked fun to try...

My first thought was that it was going to be very slow trying to sort a million entries and keep track of the number of times each value occurs. Then I realized, since the numbers range from 0-999, I could use an array with length 1000, and use each value from the text file as the index of the array (after converting it from a string to an int). I would then just need to increase the value at index 'j' by 1 if 'j' was read from the text file. Finally, I could loop through the whole 1000-length array one single time and see which index had the highest count.

When testing with 100_random_numbers.txt, I noticed that there were a lot of ties, so I created a vector to store multiple numbers that share the highest count. If there was a new highest count, I would clear the vector and add the new index/number.

I noticed that looping though the million lines in the text file and converting the values from strings to integers has the highest potential for wasted time, so I looked into the time-complexity of std::stoi() and found that it could be done quicker with the assumption that all of the strings are positive integers with no letters or white-spacing.

Switching from std::stoi() to string_to_uint() improved the total run-time from 97 to 62ms.

The most important take-away from this challenge for me was that I learned how to convert from a string to an int in a much more efficient way, and I became more familiar with using the ASCII table.

My Submission

Code

from collections import Counter
import random
import time

# For testing purposes with smaller files
def most_frequent_number(filename):
    with open(filename, "r") as f:
        numbers = [int(line.strip()) for line in f]

    counter = Counter(numbers)
    number, freq = counter.most_common(1)[0]
    return number, freq


# Benchmark with 1 million integers (values 0–999)
if __name__ == "__main__":
    # Generate a random dataset of 1 million numbers (0–999)
    nums = [random.randint(0, 999) for _ in range(1_000_000)]

    start = time.time()

    # Counter is implemented in C and very efficient
    counter = Counter(nums)
    number, freq = counter.most_common(1)[0]

    end = time.time()

    print(f"Most frequent number: {number} (appears {freq} times)")
    print(f"Execution time: {end - start:.4f} seconds")

Explanation of Approach

• Since the numbers are bounded between 0 and 999, the maximum number of distinct values is only 1000.

• This makes frequency counting extremely efficient — we don’t need complex data structures.

• I chose collections.Counter because it’s written in optimized C under the hood and handles counting very quickly.

• Alternatively, one could use a fixed-size list of length 1000 and increment counts manually, but the performance difference on Python is marginal compared to Counter (and Counter keeps the code clean).

Optimization Notes

• Reading the file line by line and converting directly to integers avoids unnecessary overhead.

• Using Counter.most_common(1) is faster than manually scanning through the dictionary since it’s optimized internally.

• I compared Counter with a manual list-based frequency array; Counter was slightly faster in my environment, likely due to its C-level optimizations.

Performance (on my machine)

• Machine: Lenovo Ideapad 330, Intel i5 (8th Gen), 8GB RAM, Windows 11, Python 3.11

• Dataset: 1,000,000 integers (0–999)

• Runtime: ~0.23 seconds (average of 5 runs)

What I Learned

• I initially thought a manual array of size 1000 would easily outperform Counter. Surprisingly, the difference was negligible because of Python’s overhead and Counter’s C implementation. The main lesson here: sometimes clean, high-level code in Python is just as fast as micro-optimizing in pure Python.

Here is one simple program in awk which do the work:

awk 'BEGIN {b=0;c=0} {a[$0]+=1; if(a[$0]>c) {b=$0;c=a[$0]}} END {print b,c} '

In "standard" approach I will count in array the occurrences of particular number, then sort and reveal the highest number. But sorting may be complex (in sense of combined memory and processor cycles). So I just check if current value if bigger that stored count and if yes replace it. So complexity of my code is (almost) linear :)

My machine:

Processor   Intel(R) Xeon(R) W-2145 CPU @ 3.70GHz   3.70 GHz
Installed RAM   64,0 GB (63,7 GB usable

TIme to exec for 100 samples:

# /usr/bin/time -p awk 'BEGIN {b=0;c=0} {a[$0]+=1; if(a[$0]>c) {b=$0;c=a[$0]}} END {print b,c} ' f
208 2
real 0.03
user 0.00
sys 0.00

TIme to exec for 10000 samples:

# /usr/bin/time -p awk 'BEGIN {b=0;c=0} {a[$0]+=1; if(a[$0]>c) {b=$0;c=a[$0]}} END {print b,c} ' f1
284 23
real 0.04
user 0.01
sys 0.01

Time with 1M samples:

# /usr/bin/time -p awk 'BEGIN {b=0;c=0} {a[$0]+=1; if(a[$0]>c) {b=$0;c=a[$0]}} END {print b,c} ' 1M_random_numbers.txt
142 1130
real 0.89
user 0.85
sys 0.01

I learned a interesting way to count lines/tokens in awk

template <std::ranges::input_range R>
    requires std::integral<std::ranges::range_value_t<R>>
int findMostCommonValueOf1000(R&& r) {
    std::array<unsigned, 1000> hist{};
    for (auto x : r) {
        ++hist[x];
    }
    return std::distance(hist.begin(), std::ranges::max_element(hist));
}

Since expected range of input values is from 0 to 999 the fastest approach is to use simple array of size 1000 allocated on stack o count each occurrence of specified value. This will avoid cache misses and will reduce branches to minimum.

Disadvantage is that this code is not resistant to invalid data. Any data outside defined range will invoke Undefined Behavior.

Here is live example.

And here is speed comparison of the same algorithm, but with use of std::unordered_map instead std::array.

Comparing different algorithms on different machines is pointless.

    private void BtnSearch_Click(object sender, EventArgs e)
    {
        string filePath = "D:/Projects/1M_random_numbers.txt";
        if (!File.Exists(filePath))
        {
            MessageBox.Show("File not found!");
            return;
        }
        var stopwatch = Stopwatch.StartNew();

        var numberCount = new Dictionary<int, int>();
      
        foreach (var line in File.ReadLines(filePath))
        {
            if (int.TryParse(line, out int number))
            {
                if (numberCount.TryGetValue(number, out int count))
                {
                    numberCount[number] = count + 1;
                }
                else
                {
                    numberCount[number] = 1;
                }
            }
        }

        stopwatch.Stop();

        LstBox.Items.Clear();
        var sortedNumbers = numberCount.OrderByDescending(n => n.Value)
                                       .ToList();
        foreach (var number in sortedNumbers)
        {
            LstBox.Items.Add($"Number: {number.Key}, Count: {number.Value}");
        }

        LblExecutionTime.Text = $"Execution Time: {stopwatch.ElapsedMilliseconds} ms";
    }

    private void BtnMostNumber_Click(object sender, EventArgs e)
    {
        string filePath = "D:/Projects/1M_random_numbers.txt";

        if (!File.Exists(filePath))
        {
            MessageBox.Show("File not found!");
            return;
        }

        var stopwatch = Stopwatch.StartNew();

        var numberCount = new Dictionary<int, int>();

        foreach (var line in File.ReadLines(filePath))
        {
            if (int.TryParse(line, out int number))
            {
                if (numberCount.TryGetValue(number, out int count))
                {
                    numberCount[number] = count + 1;
                }
                else
                {
                    numberCount[number] = 1;
                }
            }
        }

        stopwatch.Stop();

       
        var maxEntry = numberCount.OrderByDescending(n => n.Value).FirstOrDefault();

        LstBox.Items.Clear();

        
        LstBox.Items.Add($"Number with highest frequency: {maxEntry.Key}, Count: {maxEntry.Value}");
        

        LblExecutionTime.Text = $"Execution Time: {stopwatch.ElapsedMilliseconds} ms";
    }

Approach Overview :

1. File.ReadLines streams the file line-by-line.

2. Dictionary<int, int> to store counts of each number.

3. BtnSearch_Click will show all the numbers with count.

4. BtnMostNumber_Click will find the number that appears the most.

Processor :Intel Core i5-10210U CPU @ 1.60GHz 2.11 GHz

RAM : 16.0 GB 64-bit operating system

Average Execution Time :125ms

int CountWithNum()
{
    int count = 0;
    int CompareCount = 0;
    foreach (int number in numbers)
    {

        foreach (int v in compareNum)
        {
            if (number == v) { count++; }

        }
        if (count > 0)
        {
            if(count > CompareCount)
            {
                CompareCount = count;
                mostNum = number;
            }
        }
        count = 0;
    }
    return CompareCount;
}

Here is an histogram-based solution, using RTX5070 and CUDA (22 microseconds for CUDA kernels, 160 microseconds for copying from/to RAM and kernels):

// Windows 11, MSVC CUDA Compiler
// Ryzen 7900, RTX4070, RTX5070 (not overclocked) on PCIE v5.0 x16 lanes for high bandwidth (but still 1M elements are not enough to maximize this)
// 32GB RAM dual-channel 6000 MT/s

#define __CUDACC__
#undef NDEBUG
#include <assert.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cuda.h>
#include <cuda_runtime.h>
// Error-handling assert code from stackoverflow talonmies.
#define gpuErrchk(ans) { gpuAssert((ans), __FILE__, __LINE__); }
inline void gpuAssert(cudaError_t code, const char* file, int line, bool abort = true)
{
    if (code != cudaSuccess)
    {
        fprintf(stderr, "GPUassert: %s %s %d\n", cudaGetErrorString(code), file, line);
        if (abort) exit(code);
    }
}

// Optimized for 1M input elements
constexpr int N = 1000000;
// Designed to work with 1000 bins
constexpr int HISTOGRAM_BINS = 1000;
// RTX5070 has 48 SM units, each SM can have 1.5k in-flight threads (2 x 768)
constexpr int GRID_SIZE = 48 * 2;
// 768 threads per block
constexpr int BLOCK_SIZE = 768;
// 20 blocks will do level-1 reduction and 1 block will reduce the results of 20 blocks at level-2 reduction
constexpr int GRID_REDUCTION = 20;
// Benchmark iterations
constexpr int NUM_BENCH_ITER = 200;

/*
    Parallel Histogram
    Optimizations:
        Block-privatization for histogram, with 4 private histograms per block to further reduce atomicAdd collisions inside each CUDA block.
        Thread-level aggregation
        Block-level aggregation
        Vectorized memory access
        Reduction
        Asynchronous memcpy and kernel launch.
*/
template<int n>
__global__ void k_histogram(const int* const __restrict__ input, int* const __restrict__ histogram) {
    const int4* const __restrict__ inputVectorized = reinterpret_cast<const int4* const __restrict__>(input);
    const int threadIndex = threadIdx.x + blockIdx.x * blockDim.x;
    constexpr int n4 = n / 4;
    constexpr int NUM_THREADS = GRID_SIZE * BLOCK_SIZE;
    constexpr int numSteps = (n4 + NUM_THREADS - 1) / NUM_THREADS;
    constexpr int numBlockSteps = (HISTOGRAM_BINS * 4 + BLOCK_SIZE - 1) / BLOCK_SIZE;
    __shared__ int s_histogram[HISTOGRAM_BINS * 4];
    for (int step = 0; step < numBlockSteps; step++) {
        int i = step * BLOCK_SIZE + threadIdx.x;
        if (i < HISTOGRAM_BINS * 4) {
            s_histogram[i] = 0;
        }
    }
    __syncthreads();
    int registerCountCache = 0;
    int registerValueCache = -1;
    #pragma unroll 4
    for (int step = 0; step < numSteps; step++) {
        const int i = step * NUM_THREADS + threadIndex;
        if (i < n4) {
            int4 inp = inputVectorized[i];
            if (inp.x == registerValueCache) {
                registerCountCache++;
            }
            else {
                atomicAdd(&s_histogram[registerValueCache], registerCountCache);
                registerValueCache = inp.x;
                registerCountCache = 1;
            }
            if (inp.y == registerValueCache) {
                registerCountCache++;
            }
            else {
                atomicAdd(&s_histogram[registerValueCache + HISTOGRAM_BINS], registerCountCache);
                registerValueCache = inp.y;
                registerCountCache = 1;
            }
            if (inp.z == registerValueCache) {
                registerCountCache++;
            }
            else {
                atomicAdd(&s_histogram[registerValueCache + HISTOGRAM_BINS * 2], registerCountCache);
                registerValueCache = inp.z;
                registerCountCache = 1;
            }
            if (inp.w == registerValueCache) {
                registerCountCache++;
            }
            else {
                atomicAdd(&s_histogram[registerValueCache + HISTOGRAM_BINS * 3], registerCountCache);
                registerValueCache = inp.w;
                registerCountCache = 1;
            }
        }
    }
    if (registerCountCache > 0) {
        atomicAdd(&s_histogram[registerValueCache], registerCountCache);
    }
    __syncthreads();
    for (int step = 0; step < numBlockSteps; step++) {
        int i = step * BLOCK_SIZE + threadIdx.x;
        if (i < HISTOGRAM_BINS) {
            histogram[i + blockIdx.x * HISTOGRAM_BINS] = s_histogram[i] + s_histogram[i + HISTOGRAM_BINS] + s_histogram[i + HISTOGRAM_BINS * 2] + s_histogram[i + HISTOGRAM_BINS * 3];
        }
    }
}
template<int NUM_BLOCKS>
__global__ void k_reduceLevel1(int* globalHistogram, int* privateHistogram) {
    const int id = threadIdx.x + blockIdx.x * BLOCK_SIZE;
    constexpr int numSteps = (GRID_SIZE + NUM_BLOCKS - 1) / NUM_BLOCKS;
    constexpr int numBlockSteps = (HISTOGRAM_BINS + BLOCK_SIZE - 1) / BLOCK_SIZE;
    __shared__ int s_accumulator[HISTOGRAM_BINS];
    for (int i = 0; i < numBlockSteps; i++) {
        int b = i * BLOCK_SIZE + threadIdx.x;
        if (b < HISTOGRAM_BINS) {
            s_accumulator[b] = 0;
        }
    }
    for (int step = 0; step < numSteps; step++) {
        const int block = blockIdx.x + step * NUM_BLOCKS;
        if (block < GRID_SIZE) {
            for (int i = 0; i < numBlockSteps; i++) {
                int b = i * BLOCK_SIZE + threadIdx.x;
                if (b < HISTOGRAM_BINS) {
                    s_accumulator[b] += privateHistogram[block * HISTOGRAM_BINS + b];
                }
            }
        }
    }
    for (int i = 0; i < numBlockSteps; i++) {
        int b = i * BLOCK_SIZE + threadIdx.x;
        if (b < HISTOGRAM_BINS) {
            globalHistogram[blockIdx.x * HISTOGRAM_BINS + b] = s_accumulator[b];
        }
    }
}
template<int NUM_BLOCKS>
__global__ void k_reduceLevel2(int* globalHistogram, int* output) {
    const int id = threadIdx.x;
    constexpr int numBlockSteps = (HISTOGRAM_BINS + BLOCK_SIZE - 1) / BLOCK_SIZE;
    const int warpLane = id & 31;
    const int localWarpId = id >> 5;
    __shared__ int s_freq[32];
    __shared__ int s_value[32];
    int frequency = 0;
    int value = id;
    for (int block = 0; block < NUM_BLOCKS; block++) {
        if (id < HISTOGRAM_BINS) {
            frequency += globalHistogram[block * HISTOGRAM_BINS + id];
        }
    }
    __syncthreads();
    /* Finding the most frequent item and copying the result to the output. */
    // Warp-reduction.
    for (unsigned int i = 16; i >= 1; i >>= 1) {
        int gatheredFrequency = __shfl_sync(0xFFFFFFFF, frequency, warpLane + i);
        int gatheredValue = __shfl_sync(0xFFFFFFFF, value, warpLane + i);
        if (warpLane + i < 32) {
            if (gatheredFrequency > frequency) {
                frequency = gatheredFrequency;
                value = gatheredValue;
            }
        }
    }
    // Warp-results.
    if (warpLane == 0) {
        s_freq[localWarpId] = frequency;
        s_value[localWarpId] = value;
    }
    __syncthreads();
    // Finarl warp reduction.
    if (localWarpId == 0) {
        frequency = s_freq[warpLane];
        value = s_value[warpLane];
        for (unsigned int i = 16; i >= 1; i >>= 1) {
            int gatheredFrequency = __shfl_sync(0xFFFFFFFF, frequency, warpLane + i);
            int gatheredValue = __shfl_sync(0xFFFFFFFF, value, warpLane + i);
            if (warpLane + i < 32) {
                if (gatheredFrequency > frequency) {
                    frequency = gatheredFrequency;
                    value = gatheredValue;
                }
            }
        }
    }
    if (id == 0) {
        output[0] = value;
        output[1] = frequency;
    }
}


int main() {

    // My system has rtx5070 as the second device (id = 1).
    int rtx5070 = 1;
    int devices;
    gpuErrchk(cudaGetDeviceCount(&devices));
    gpuErrchk(cudaSetDevice(devices > 1 ? rtx5070 : 0));

    // Preparing benchmark data.
    int* input;
    gpuErrchk(cudaMallocHost(&input, sizeof(int) * N));
    std::ifstream file("./1M_random_numbers.txt");

    std::string line;
    int k = 0;
    while (getline(file, line))
    {
        input[k] = std::stoi(line);
        k++;
    }
    std::cout << "lines=" << k << std::endl;
    assert(k == N);
    file.close();

    std::cout << "computing with cpu: " << std::endl;
    // Preparing reference result with simple readable cpu implementation.
    int* hist;
    gpuErrchk(cudaMallocHost(&hist, sizeof(int) * HISTOGRAM_BINS));
    for (int i = 0; i < HISTOGRAM_BINS; i++) {
        hist[i] = 0;
    }
    for (int i = 0; i < N; i++) {
        hist[input[i]]++;
    }
    int mostFrequent = -1;
    int frequency = 0;
    for (int i = 0; i < HISTOGRAM_BINS; i++) {
        if (frequency < hist[i]) {
            frequency = hist[i];
            mostFrequent = i;
        }
    }
    std::cout << "cpu result = " << mostFrequent << " " << frequency << std::endl;
    std::cout << "computing with gpu: " << std::endl;


    // Preparing CUDA resources.
    cudaStream_t stream;
    cudaEvent_t eventStart;
    cudaEvent_t eventStop;
    cudaEvent_t eventKernelStart;
    cudaEvent_t eventKernelStop;
    gpuErrchk(cudaStreamCreate(&stream));
    gpuErrchk(cudaEventCreate(&eventStart));
    gpuErrchk(cudaEventCreate(&eventStop));
    gpuErrchk(cudaEventCreate(&eventKernelStart));
    gpuErrchk(cudaEventCreate(&eventKernelStop));
    // The input data from host.
    int* input_d;
    // The results from privatized histograms.
    int* histogramPerBlock_d;
    // Reduction level 1 result.
    int* histogramReduced_d;
    // Reduction level 2 result (most frequent element and its frequency). 
    int* histogram_d;
    gpuErrchk(cudaMallocAsync(&input_d, sizeof(int) * N, stream));
    gpuErrchk(cudaMallocAsync(&histogramPerBlock_d, sizeof(int) * HISTOGRAM_BINS * GRID_SIZE, stream));
    gpuErrchk(cudaMallocAsync(&histogramReduced_d, sizeof(int) * HISTOGRAM_BINS * GRID_REDUCTION, stream));
    gpuErrchk(cudaMallocAsync(&histogram_d, sizeof(int) * 2, stream));

    // Warming gpu and pcie up.
    std::cout << "Warming gpu up." << std::endl;

    for (int bench = 0; bench < NUM_BENCH_ITER; bench++) {
        gpuErrchk(cudaMemcpyAsync(input_d, input, sizeof(int) * N, cudaMemcpyHostToDevice, stream));
        void* argsHistogram[] = { (void*)&input_d, (void*)&histogramPerBlock_d };
        gpuErrchk(cudaLaunchKernel((void*)k_histogram<N>, dim3(GRID_SIZE, 1, 1), dim3(BLOCK_SIZE, 1, 1), argsHistogram, 0, stream));

        void* argsReduction1[] = { (void*)&histogramReduced_d, (void*)&histogramPerBlock_d };
        gpuErrchk(cudaLaunchKernel((void*)k_reduceLevel1<GRID_REDUCTION>, dim3(GRID_REDUCTION, 1, 1), dim3(BLOCK_SIZE, 1, 1), argsReduction1, 0, stream));

        void* argsReduction2[] = { (void*)&histogramReduced_d, (void*)&histogram_d };
        gpuErrchk(cudaLaunchKernel((void*)k_reduceLevel2<GRID_REDUCTION>, dim3(1, 1, 1), dim3(1024, 1, 1), argsReduction2, 0, stream));
        gpuErrchk(cudaMemcpyAsync(hist, histogram_d, sizeof(int) * 2, cudaMemcpyDeviceToHost, stream));
    }
    cudaStreamSynchronize(stream);
    std::cout << "Benchmarking gpu." << std::endl;
    // Benchmarking kernel.
    gpuErrchk(cudaEventRecord(eventKernelStart, stream));
    for (int bench = 0; bench < NUM_BENCH_ITER; bench++) {
        void* argsHistogram[] = { (void*)&input_d, (void*)&histogramPerBlock_d };
        gpuErrchk(cudaLaunchKernel((void*)k_histogram<N>, dim3(GRID_SIZE, 1, 1), dim3(BLOCK_SIZE, 1, 1), argsHistogram, 0, stream));

        void* argsReduction1[] = { (void*)&histogramReduced_d, (void*)&histogramPerBlock_d };
        gpuErrchk(cudaLaunchKernel((void*)k_reduceLevel1<GRID_REDUCTION>, dim3(GRID_REDUCTION, 1, 1), dim3(BLOCK_SIZE, 1, 1), argsReduction1, 0, stream));

        void* argsReduction2[] = { (void*)&histogramReduced_d, (void*)&histogram_d };
        gpuErrchk(cudaLaunchKernel((void*)k_reduceLevel2<GRID_REDUCTION>, dim3(1, 1, 1), dim3(1024, 1, 1), argsReduction2, 0, stream));
    }
    gpuErrchk(cudaEventRecord(eventKernelStop, stream));
    gpuErrchk(cudaStreamSynchronize(stream));
    // Benchmarking kernel + copy.
    gpuErrchk(cudaEventRecord(eventStart, stream));
    for (int bench = 0; bench < NUM_BENCH_ITER; bench++) {
        gpuErrchk(cudaMemcpyAsync(input_d, input, sizeof(int) * N, cudaMemcpyHostToDevice, stream));

        void* argsHistogram[] = { (void*)&input_d, (void*)&histogramPerBlock_d };
        gpuErrchk(cudaLaunchKernel((void*)k_histogram<N>, dim3(GRID_SIZE, 1, 1), dim3(BLOCK_SIZE, 1, 1), argsHistogram, 0, stream));

        void* argsReduction1[] = { (void*)&histogramReduced_d, (void*)&histogramPerBlock_d };
        gpuErrchk(cudaLaunchKernel((void*)k_reduceLevel1<GRID_REDUCTION>, dim3(GRID_REDUCTION, 1, 1), dim3(BLOCK_SIZE, 1, 1), argsReduction1, 0, stream));

        void* argsReduction2[] = { (void*)&histogramReduced_d, (void*)&histogram_d };
        gpuErrchk(cudaLaunchKernel((void*)k_reduceLevel2<GRID_REDUCTION>, dim3(1, 1, 1), dim3(1024, 1, 1), argsReduction2, 0, stream));
        gpuErrchk(cudaMemcpyAsync(hist, histogram_d, sizeof(int) * 2, cudaMemcpyDeviceToHost, stream));
    }
    gpuErrchk(cudaEventRecord(eventStop, stream));
    gpuErrchk(cudaStreamSynchronize(stream));
    float totalMiliseconds = 0.0f;
    float totalMilisecondsKernel = 0.0f;
    {
        float miliseconds;
        gpuErrchk(cudaEventElapsedTime(&miliseconds, eventStart, eventStop));
        totalMiliseconds += miliseconds;

        gpuErrchk(cudaEventElapsedTime(&miliseconds, eventKernelStart, eventKernelStop));
        totalMilisecondsKernel += miliseconds;
    }
    // Result from gpu.
    mostFrequent = hist[0];
    frequency = hist[1];
    std::cout << "gpu result = " << mostFrequent << " " << frequency << std::endl;
    std::cout << "gpu average total time (copy to device + kernels + copy to host) = " << totalMiliseconds / NUM_BENCH_ITER << " miliseconds" << std::endl;
    std::cout << "gpu average kernel time (histogram + reduction level 1 + reduction level 2) = " << totalMilisecondsKernel / NUM_BENCH_ITER << " miliseconds" << std::endl;
    
    gpuErrchk(cudaFreeAsync(input_d, stream));
    gpuErrchk(cudaFreeAsync(histogramPerBlock_d, stream));
    gpuErrchk(cudaFreeAsync(histogramReduced_d, stream));
    gpuErrchk(cudaFreeAsync(histogram_d, stream));
    {
        gpuErrchk(cudaEventDestroy(eventStart));
        gpuErrchk(cudaEventDestroy(eventStop));
        gpuErrchk(cudaEventDestroy(eventKernelStart));
        gpuErrchk(cudaEventDestroy(eventKernelStop));
    }
    gpuErrchk(cudaStreamSynchronize(stream));
    gpuErrchk(cudaStreamDestroy(stream));
    gpuErrchk(cudaFreeHost(hist));
    gpuErrchk(cudaFreeHost(input));
    return 0;
}

output:

lines=1000000
computing with cpu:
cpu result = 142 1130
computing with gpu:
Warming gpu up.
Benchmarking gpu.
gpu result = 142 1130
gpu average total time (copy to device + kernels + copy to host) = 0.160253 miliseconds
gpu average kernel time (histogram + reduction level 1 + reduction level 2) = 0.0219413 miliseconds

so its ~22 microseconds for 1M elements for the kernels only, ~160 microseconds if data copy latency is added (if dataset is assumed to be in RAM).

Optimizations used in the histogram kernel:

• templated design to let the CUDA compiler enable more optimizations

• thread-level aggregation for atomics

• block-level aggregation for atomics

• vectorized memory access to hide more latency

• block-privatization of the histogram (this means each CUDA block works on its own local histogram to reduce contention on global atomic increments)

After the histogram kernel, two reduction kernels are run. They reduce the local outputs into a global output and then finally the most frequent element and its frequency to be copied back to RAM. Only the histogram kernel alone takes 3 microseconds according to Nsight profiler but adding event-based timers makes more latency. So, the real kernel performance is 2x better (~10 microseconds for 3 kernels) when not benchmarking but doing real-work (assuming whole project uses VRAM only).

import pandas as pd
data = pd.read_csv('/1M_random_numbers.txt', header=None, names=['number'])

res = {}

for num in data['number']:

    if num in res:
        res[num] += 1
    else:
        res[num] = 1
df = pd.DataFrame(res.items(), columns=['number', 'count'])
df.sort_values('count', ascending=False).iloc[0]

void main() {
  List<int> numbers = [5, 7, 2, 5, 7, 7, 9, 2, 5, 7, 2, 9, 9];
  List<int> maxNumbers = [];
  int maxCount = 0;


  List<int> freq = List.filled(1000, 0);
  for (int i = 0; i < numbers.length; i++) {
    freq[numbers[i]]++;
  }


  for (int i = 0; i < freq.length; i++) {
    if (freq[i] > maxCount) {
      maxCount = freq[i];
    }
  }


  for (int i = 0; i < freq.length; i++) {
    if (freq[i] == maxCount) {
      maxNumbers.add(i);
    }
  }

  print("Most frequent numbers are $maxNumbers with count $maxCount");
}

This program will find the maximum count of any numbers tha is between 0 to 999 in the list and will print that numbers and lets suppose if list have more numbers with maximum counts for example the numbers 5 and 7 have the maximum count and are equals both have 9 than it will print both numbers

<?php
// PHP 8.4 ; Windows 11 ;
// 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz (2.42 GHz)
// 8.00 GB RAM

$counts = array_fill(0, 1000, 0);
while(strlen($str=trim(fgets(STDIN)))){
    $number = intval($str);
    $counts[$number]++;
}
asort($counts);
echo array_key_last($counts);

This seems to be a very simple matter to me so I'm looking forward to seeing some better attempts.

I take it that the input must be read from a file. Placing the numbers directly in the script means processing time is moved to the interpreter making it about 3 times faster to process. I presume this would be cheating.

I tried with a plain dict using setdefault to count, collections.defaultdict, reading direct from the input file and also building a list from the input file first. Nothing really makes much difference and collections.Counter is twice as fast anyway.

It may be possible to stop the search early if the current highest frequency is greater than the number of remaining numbers left to check, but on this kind of input that would be very unlikely to yield a performance improvement because it's necessary to check on every iteration, or even in chunks, and that would introduce more overhead than it saves.

Nothing else really occurs to me other than collections.Counter, except for one thing. The input is clean and regular so there's no need to convert the text to int. That saves a bit of time:

"""
$ python numbers.py
[('142\n', 1130)]
0.08784699440002441
"""

import collections
import time

start = time.time()
with open("numbers.txt") as numbers:
    print(collections.Counter(numbers).most_common(1))
print(time.time() - start)

Round about 0.08784699440002441 seconds using Python 3.10 on WSL2 on an 11th Gen Intel(R) Core(TM) i7-1185G7 @ 3.00GHz with 16.0 GB RAM.

I developed the solution in python3, node and C; and this is the more concise and elegant way I found. The C version is the fastest (about 40 ms) but its too verbose...

I learned the existence of the useful collections.Counter class.

The code runs in about 85 ms on an Apple M1 Pro with 16GB of RAM with Python 3.11.12

This is my solution:

import time
from collections import Counter

start_time = time.process_time_ns()

f = open('1M_random_numbers.txt', 'r')
frequencies = Counter(f.read().split())
print(frequencies.most_common(1))

print((time.process_time_ns() - start_time)/1_000_000_000)

And outputs

[('142', 1130)]
0.086723

So the most frequent number is 142 with a frequency of 1130.

The following code was run on Google Colab (basic free runtime). This seems to be solved in a simple O(N) algorithm where you assign a length-1000 integer list, loop over the numbers adding one to the corresponding entry in the length-1000 list for each number and then loop over the length-1000 list to find the most common number. In terms of optimization this assumes that the list of numbers is much longer than 1000 such that looping over the length-1000 list at the end is fast compared to looping over the numbers.

It's easy to code this algorithm up in python, but is a good example of where [naively written] python can be slow. It's also a great example of where Cython can help (for someone who doesn't know or doesn't want to know C/C++). I implement the simple algorithm in Python, and then show how doing the same in Cython significantly speeds this up. Finally, we also show how this can be done using numpy.unique but that the Cython code is more optimal.

import numpy as np

# Download files from within jupyter/colab using gdown
!gdown 14kbAC0edO05Z1EIYbZMC6Gpzx1u2yecd
!gdown 1OrIx7ZbHr5q1Smo2-T_7MWhVPR9DNny3
!gdown 1BZfKc60zRBoyeGSUAkzgQcxxpgly4IL_

# Reading the numbers in is probably the most expensive part of this.
# But I'm assuming that the function is supposed to work on numbers
# being provided to it, so not looking to optimise this. (np.loadtxt
# is probably pretty good anyway)
numbers_100 = np.loadtxt('100_random_numbers.txt', dtype=np.int32)
numbers_10000 = np.loadtxt('10000_random_numbers.txt', dtype=np.int32)
numbers_1M = np.loadtxt('1M_random_numbers.txt', dtype=np.int32)

# This seems to be easily solved with a O(N) algorithm and a "counts" array
# As the algorithm is handling lengths ~ 1M assigned 1000 integers extra memory
# is negligible to store the counts.
def most_occurring_number(numbers):
    counts = np.zeros(1000)
    for n in numbers:
        counts[n] += 1
    return np.argmax(counts)

print(most_occurring_number(numbers_1M))
%timeit most_occurring_number(numbers_1M)

returns
142 406 ms ± 6.48 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Then adding a Cython function

%load_ext cython

%%cython -a
import cython

@cython.boundscheck(False)
@cython.wraparound(False)
def most_occurring_number_cy(int[::1] numbers, int length, int[::1] counts):
    cdef int i, n
    for n in numbers:
        counts[n] += 1
    cdef int max_occur = 0
    cdef int max_idx = 1000
    for i in range(1000):
        if counts[i] > max_occur:
            max_occur = counts[i]
            max_idx = i
    return max_idx

# We use cython to optimize this. The counts memory allocation is still done in python
# If calling this function many times this could be cached and reset to 0 every time.
def most_occurring_number_v2(numbers):
    counts = np.zeros(1000, dtype=np.int32)
    return most_occurring_number_cy(numbers, len(numbers), counts)

print(most_occurring_number_v2(numbers_1M))
%timeit most_occurring_number_v2(numbers_1M)

returns
142 763 µs ± 36.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Finally:

# numpy has a builtin function to do this. Let's compare it to our Cython code
print(np.argmax(np.unique(numbers_1M, return_counts=True)[1]))
%timeit np.argmax(np.unique(numbers_1M, return_counts=True)[1])

returns
142 8.44 ms ± 1.42 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)

using System.Globalization;

namespace Integer_Counting
{
    internal class Program
    {
        const string file100 = "files/100_random_numbers.txt";
        const string file10000 = "files/10000_random_numbers.txt";
        const string file1M = "files/1M_random_numbers.txt";

        static void Main(string[] args)
        {
            FindMostPopularNumber(file100);
            FindMostPopularNumber(file10000);
            FindMostPopularNumber(file1M);
        }

        static void FindMostPopularNumber(string file)
        {
            var dtStart = DateTime.Now;
            Console.WriteLine($"Start time: {dtStart.ToString("yyyy-MM-dd HH:mm:ss.fff",CultureInfo.InvariantCulture)}");
            var list = new List<int>();
            var fileContents = File.ReadAllLines(file);
            foreach (string line in fileContents)
            {
                list.Add(Convert.ToInt32(line));
            }
            var listWithCount = list.GroupBy(x => x);

            //Figure out the highest count because we need to print all numbers that appear that many times
            var maxCount = listWithCount.OrderByDescending(x => x.Count()).Take(1).First().Count();

            var stringOfMostPopularNumbers = string.Empty;
            foreach (var number in listWithCount.Where(x => x.Count() == maxCount))
            {
                stringOfMostPopularNumbers += $"{number.Key},";
            }
            stringOfMostPopularNumbers = stringOfMostPopularNumbers.Substring(0, stringOfMostPopularNumbers.Length - 1); //Get rid of last comma

            Console.WriteLine($"Most popular number(s): {stringOfMostPopularNumbers}");
            var dtEnd = DateTime.Now;
            Console.WriteLine($"End time: {dtEnd.ToString("yyyy-MM-dd HH:mm:ss.fff", CultureInfo.InvariantCulture)}");
            Console.WriteLine($"Execution runtime: {(dtEnd - dtStart).Milliseconds} milliseconds");
            Console.WriteLine();
        }

        static void PrintList(string file)
        {
            var list = new List<int>();
            var fileContents = File.ReadAllLines(file);
            foreach (string line in fileContents)
            {
                list.Add(Convert.ToInt32(line));
            }
            list = list.OrderBy(x => x).ToList();
            foreach (var x in list)
                Console.WriteLine(x);
        }
    }
}

I optimized this task by reading all lines at once from the file, adding each to a List, and then Grouping By each number. The .NET 9 code is quite efficient, clocking in at less than 250 milliseconds for each of the datasets in each of the runs.

First run:

Start time: 2025-09-25 15:48:19.734
Most popular number(s): 546,188,208,641,374,694
End time: 2025-09-25 15:48:19.763
Execution runtime: 29 milliseconds

Start time: 2025-09-25 15:48:19.763
Most popular number(s): 284
End time: 2025-09-25 15:48:19.769
Execution runtime: 5 milliseconds

Start time: 2025-09-25 15:48:19.769
Most popular number(s): 142
End time: 2025-09-25 15:48:20.016
Execution runtime: 247 milliseconds

Second run:

Start time: 2025-09-25 15:49:00.919
Most popular number(s): 546,188,208,641,374,694
End time: 2025-09-25 15:49:00.949
Execution runtime: 30 milliseconds

Start time: 2025-09-25 15:49:00.949
Most popular number(s): 284
End time: 2025-09-25 15:49:00.955
Execution runtime: 5 milliseconds

Start time: 2025-09-25 15:49:00.955
Most popular number(s): 142
End time: 2025-09-25 15:49:01.180
Execution runtime: 225 milliseconds

Third run:

Start time: 2025-09-25 15:49:22.501
Most popular number(s): 546,188,208,641,374,694
End time: 2025-09-25 15:49:22.530
Execution runtime: 29 milliseconds

Start time: 2025-09-25 15:49:22.531
Most popular number(s): 284
End time: 2025-09-25 15:49:22.536
Execution runtime: 5 milliseconds

Start time: 2025-09-25 15:49:22.536
Most popular number(s): 142
End time: 2025-09-25 15:49:22.768
Execution runtime: 231 milliseconds

Processor is Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz (3.19 GHz). Installed RAM is 48.0 GB.

I learned that it's a good idea to check the small dataset with your eyes to see what the answer should be. I noticed my original answer only had two hits, and then noticed that there was at least one more number had two hits, thus the tie in dataset 1.

Approach

The task consists of two parts.
The first part (BUILD) traverses the input list of numbers and builds a table that counts how many times each number appears.
The second part (FIND) traverses the freshly built table finding the maximum, thereby locating the value that appears the most often in the input list. Since there's no guarantee that this will be a unique solution, I have added the concept of ex-aequo's.

Optimization

• I've put the table in stack memory so it stays distant from the running code. If data is written too close-by to the executing instructions, then the CPU might think it's self-modifying code and performance will suffer from this. Additionally, I have the table's dword elements reside on their natural boundaries. Please note that the same problem does not exist for the filebuffer that I use, because my program only ever reads from it. It is (further away) DOS code that writes to this memory.

• I mostly keep the stackpointer dword-aligned for best performance. Eventhough this is the 16-bit real address mode, in general - surprisingly perhaps - it does matter.

• I have replaced the multiplications by 10 (that are followed by an addition) with a couple of efficient LEA instructions.

• The GetValidByte subroutine was optimized with no branching in the common case.

• Several program variables were not based in memory, but instead kept in a processor register.

Results

I measure the program's execution time by reading the TimeStampCounter twice and converting the difference according to my processor's frequency which is 1.73 GHz. All I/O is included in the execution time. The machine is an Intel Pentium dual core processor T2080 (533 MHz FSB, 1 MB L2 cache). The environment is DOS 6.20 (minimally configured, no TSRs active). The program was assembled with FASM.

C:\SO>100
Next values appear 2 times: 188, 208, 374, 546, 641, 694
The program's runtime is 345 µsec

C:\SO>10K
Next value appears 23 times: 284
The program's runtime is 10571 µsec

C:\SO>1M
Next value appears 1130 times: 142
The program's runtime is 1531207 µsec

C:\SO>

Challenge #6 --- Program to scan a list of numbers
and find the value(s) that appear(s) the most often.

BUFSIZE equ     512
ALLNUM  equ     1000000

        ORG     256             ; .COM program has CS=DS=ES=SS

INIT:   and     sp, -4          ; 4-byte aligned stack
        rdtsc                   ; -> EDX:EAX
        push    edx eax
        sub     sp, 1000*4      ; 4-byte aligned table
        movzx   ebp, sp
        mov     di, sp          ; Wipe the table of dword counters
        mov     cx, 1000
        xor     eax, eax
        cld
        rep stosd

        mov     dx, TheFile
        mov     ax, 3D00h       ; DOS.OpenFile for reading
        int     21h             ; -> AX CF
        jc      ABORT
        mov     [Handle], ax    ; ReadPointer is kept in SI
        xor     bx, bx          ; AvailableBytes is kept in BX
        mov     ecx, ALLNUM

; Extract ALLNUM integers [0,999] from the input list
; and tally in the 1000-dwords table at EBP
BUILD:  call    GetValidByte    ; -> EAX BX SI CF
        jnc     ABORT           ; It's not a number
        mov     edi, eax        ; Build the 1-digit value
        call    GetValidByte    ; -> EAX BX SI CF
        jnc     .INC            ; It's a single-digit number
        lea     edi, [edi+edi*4]; Build the 2-digit value
        lea     edi, [eax+edi*2]
        call    GetValidByte    ; -> EAX BX SI CF
        jnc     .INC            ; It's a double-digit number
        lea     edi, [edi+edi*4]; Build the 3-digit value
        lea     edi, [eax+edi*2]
        call    GetValidByte    ; -> EAX BX SI CF
        jc      ABORT           ; There're more than 3 digits
.INC:   inc     dword [ebp+edi*4]
        dec     ecx
        jnz     BUILD

        mov     bx, [Handle]
        mov     ah, 3Eh         ; DOS.CloseFile
        int     21h             ; -> AX CF

; Find max in the table with 1000 dword counters
        mov     eax, [bp]       ; Value of the initial max
        xor     ebx, ebx        ; Index of the initial max
        xor     cx, cx          ; For now it is a unique find
        lea     esi, [ebx+1]    ; Index [1,999] for other items
FIND:   mov     edx, [ebp+esi*4]; -> EDX is [0,TOTALNUMBERS]
        cmp     edx, eax
        jl      .LT
        je      .EQ
.GT:    mov     eax, edx        ; Set new max (is unique for now)
        mov     ebx, esi        ; Remember its index
        mov     cx, -1          ; Clear EX-AEQUO
.EQ:    inc     cx
.LT:    inc     esi
        cmp     esi, 1000
        jb      FIND

; Show results on the screen and terminate
        mov     dx, msgOK1
        jcxz    SHOW            ; EX-AEQUO is [0,999]
        mov     dx, msgOK2
SHOW:   push    ax
        mov     ah, 09h         ; DOS.PrintString
        int     21h             ; -> AL='$'
        pop     ax

        call    ShowEAX
        mov     dx, msgOK3
        mov     ah, 09h         ; DOS.PrintString
        int     21h             ; -> AL='$'

        mov     dl, ':'         ; Prefix for first/only value
.CSV:   mov     ah, 02h         ; DOS.PrintCharacter
        int     21h             ; -> AL=DL
        mov     eax, ebx
        call    ShowEAX
        mov     dx, msgEOL
        dec     cx              ; More ex-aequo's to display ?
        js      EXIT            ; No
        mov     eax, [ebp+ebx*4]
.NEXT:  inc     ebx             ; Locate the next ex-aequo
        cmp     [ebp+ebx*4], eax
        jne     .NEXT
        mov     dl, ','         ; Prefix so as to obtain
        jmp     .CSV            ;  CSV output format

ABORT:  mov     dx, msgERR
EXIT:   mov     ah, 09h         ; DOS.PrintString
        int     21h             ; -> AL='$'

        rdtsc                   ; -> EDX:EAX
        sub     eax, [bp+4000]  ; Minus the initial TSC
        sbb     edx, [bp+4004]
        mov     ecx, 1730       ; 1.73 GHz -> duration in µsec
        div     ecx
        call    ShowEAX
        mov     dx, msgTIM
        mov     ah, 09h         ; DOS.PrintString
        int     21h             ; -> AL='$'

        mov     ax, 4C00h       ; DOS.TerminateWithExitcode
        int     21h
; ------------------------------
; A valid byte is either a newline (10) or else a decimal digit [0,9]
; Does not return if either the byte is invalid or a file error occured
; IN (bx,si) OUT (eax,bx,si,CF)
GetValidByte:
        dec     bx              ; AvailableBytes - 1
        js      .LOAD
.FETCH: movzx   eax, byte [si]
        inc     si              ; ReadPointer + 1
        cmp     al, 10          ; Is it the newline ?
        je      .RET            ; Yes
        sub     eax, '0'
        cmp     al, 10          ; Is it a decimal digit ?
        ja      ABORT
.RET:   ret                     ; CF=0 for 10, CF=1 for [0,9]
.LOAD:  push    cx dx
        mov     si, Buffer      ; Reset readpointer
        mov     dx, si
        mov     cx, BUFSIZE
        mov     bx, [Handle]
        mov     ah, 3Fh         ; DOS.ReadFile
        int     21h             ; -> AX CF
        pop     dx cx
        jc      ABORT
        dec     ax              ; [0,BUFSIZE] -> [-1,BUFSIZE-1]
        js      ABORT
        mov     bx, ax          ; Remaining bytes
        jmp     .FETCH          ;  AFTER this fetch completes
; ------------------------------
; Prints the unsigned dword in EAX with a prepended space character
; IN (eax) OUT ()
ShowEAX:push    bx ecx edx
        mov     bx, sp
        sub     sp, 12
        dec     bx
        mov     byte [bx], '$'
        mov     ecx, 10
.a:     xor     edx, edx
        div     ecx
        dec     bx
        add     dl, '0'
        mov     [bx], dl
        test    eax, eax
        jnz     .a
        dec     bx
        mov     byte [bx], ' '
        mov     dx, bx
        mov     ah, 09h         ; DOS.PrintString
        int     21h             ; -> AL='$'
        add     sp, 12
        pop     edx ecx bx
        ret
; ------------------------------
TheFile db      'NUM1M.TXT', 0
msgERR  db      'Trouble using the file'
msgEOL  db      13, 10, "The program's runtime is$"
msgOK1  db      'Next value appears$'
msgOK2  db      'Next values appear$'
msgOK3  db      ' times$'
msgTIM  db      ' µsec', 13, 10, '$'
; ------------------------------
        ALIGN   2
Handle  rw      1
Buffer  rb      BUFSIZE

The key insight was the limited range of the possible numbers. This allows simply storing a histogram in a fixed size array.

It is possible to get the highest occurrence in a single pass by storing the current highest value and number and updating it if required after increasing the occurrence of the currently read number. I.e. like if(++count[cur] > max) { max = count[cur]; max_num = cur; }
However this made it 3x slower in my tests. Doing it separately executes only 1000 branches while doing it while counting runs 1 branch per number, i.e. 1M, which seems to explain the difference.

My Result:

Most frequent: 142 (1130 times)

Took 391µs

on a AMD Ryzen 5 3600.

This is fast enough that no further optimization seems to be required.

My code:

#include <iostream>
#include <fstream>
#include <vector>
#include <chrono>
#include <algorithm>

int main(int argc, const char** argv) {
    if (argc < 2)
        return 1;
    std::vector<int> numbers;
    numbers.reserve(1000000);
    std::ifstream file(argv[1]);
    while (true) {
        int cur;
        if (!(file >> cur).ignore())
            break;
        numbers.push_back(cur);
    }

    std::chrono::high_resolution_clock clock;
    auto start = clock.now();
    constexpr int REPEATS = 100;
    unsigned max_count, max_number;
    for (int ct = 0; ct < REPEATS; ct++) {
        unsigned counts[1000] = { 0 };

        max_count = max_number = 0;
        for (const auto cur : numbers) {
            if (++counts[cur] > max_count) {
                max_count = counts[cur];
                max_number = cur;
            }
        }
    }
    auto elapsed = clock.now() - start;
    std::cout << "Most frequent: " << max_number << " (" << max_count << " times)\n";
    std::cout << "Took " << std::chrono::duration_cast<std::chrono::microseconds>(elapsed).count() / REPEATS << "us\n";
    return 0;
}

AVX-512 and Scalar Solutions Written in Assembly + LabVIEW

Spoiler – below are three implementations: 

Assembly: AVX-512 (gather/scatter) – 840 µs   
Assembly: Scalar (unrolled loop) – 370 µs   
LabVIEW: Fully sorted list – 10 ms

The "classical" approach to finding the most frequently occurring number is histogram-based: build a histogram, locate the maximum value, and the index of that maximum is the number you're looking for. A very naive implementation might look like this:

for (int i = 0; i < MAX_ELEMENTS; i++)
    histogram[numbers[i]]++;

for (int i = 0; i < 1000; i++) {
    if (histogram[i] > maxValue) {
        maxValue = histogram[i];
        mostUsed = i;
    }
} 
printf("Most used is %d\n", mostUsed);

Or, if using high-level library functions available, for example in NI LabWindows/CVI, it's even simpler:

FileToArray("1000000_random_numbers.txt", numbers, ...);
Histogram(numbers, 1000000, 0.0, 999.0, histogram, ...);
MaxMin1D(histogram, 1000, &maxValue, &mostUsed, ...);
printf("Most used is %lld\n", mostUsed);

But we're not looking for the simplest solution. Some time ago, I came across the gather/scatter instruction pair, which is a good starting point for building a histogram using SIMD instructions. Let's give it a try.

Core Algorithm in Assembly

The heart of the algorithm is a loop that builds the histogram as follows:

; RAX - Pointer to input data (array of one million 16-bit unsigned integers)
; RCX - Number of element groups (1000000 / 16 = 62500 iterations)
; RDX - Pointer to destination histogram

vpbroadcastd ZMM16, 1 ; Packed dwords of 1 – increments
XOR RBX, RBX                    ; Initial offset index = 0
KXNORD K0, K0, K0               ; Mask of all ones

.loop:
VPMOVZXWD ZMM1, [RAX + RBX] ; Load 32x16-bit words → ZMM1
VPSLLD ZMM2, ZMM1, 2 ; ZMM2 = ZMM1 * 4 (byte offsets)
KMOVD K1, K0 ; Restore mask (cleared by VPGATHERDD)
VPGATHERDD ZMM3, [RDX + ZMM2], MASK=K1 ; Gather current histogram values
VPADDD ZMM3, ZMM3, ZMM16 ; Increment each by 1
KMOVD K2, K0             ; Reset mask
VPSCATTERDD [RDX + ZMM2], ZMM3, MASK=K2 ; Scatter updated values
ADD RBX, 32  ; Move to next 32 elements
LOOP .loop   ; Decrement RCX and loop if not zero

The beauty of this algorithm is that 16 input values are processed simultaneously. Instead of 1,000,000 iterations, we only need 62,500. The VPGATHERDD instruction conditionally loads 16 dword values from memory using dword indices, then VPADDD increments them, and VPSCATTERDD writes them back. Simple and elegant.

Handling Duplicates

However, there's a caveat: if the same value appears multiple times in a group, only one increment is applied. To fix this, I use VPCONFLICTD to detect duplicates:

.loop:
VPMOVZXWD ZMM1, [RAX + RBX] ; Load 32x16-bit words → ZMM1
VPCONFLICTD ZMM4, ZMM1   ; ZMM4 = conflict indices
VPXORD ZMM5, ZMM4, ZMM4  ; ZMM5 = 0
VPCMPD k1, ZMM4, ZMM5, 0 ; k1 = lanes with no conflict (unique)
KNOTW k2, k1 ; k2 = lanes with duplicates
KORTESTW k2, k2   ; Check if any duplicates exist
JNZ .duplicates   ; Jump to scalar fallback if duplicates

Ideally, we could build a mask for VPADDD using VPOPCNT, but the assembler used doesn't support it. So we fall back to a scalar loop:

.duplicates:
MOV R11, RAX
ADD R11, RBX
MOV R12, 16
align 16
.L2:
MOVZX R13D, [R11]
ADD [RDX + R13*4], 1
ADD R11, 2                     ; Two bytes per value
DEC R12
JNZ .L2

Finding the Maximum

Once the histogram is built, scan it to find the maximum value:

.histogram:
XOR RAX, RAX 
XOR R9D, R9D                  ; R9D = final result (max index)
XOR EBX, EBX                  ; EBX = current maximum
MOV RCX, 1000                 ; Range: 0...999

align 16
.L3:
MOV R8D, [RDX]
CMP EBX, R8D
CMOVL R9D, RAX                ; Branchless conditional move
CMOVL EBX, R8D
INC RAX
ADD RDX, 4
LOOP .L3

The interesting part here is the use of CMOVL to avoid branching when updating the maximum value and its index.

File Handling and Input

Here's how the input argument is handled and the file is loaded using EuroAssembler macros:

Start: nop
StdOutput MsgStart, Eol=Yes, Console=Yes
GetArg 1
JC .DefaultFile
StripQuotes RSI, RCX
MOV RDI, File$
REP MOVSB
SUB AL, AL
STOSB

.DefaultFile:
FileAssign theFile, File$
FileExists? theFile
JC .ErrorFileNotFound
FileStreamOpen theFile, BufSize=16K
MOV R10, Buf_arr
XOR R8, R8

.L1:
FileStreamReadLn theFile
JZ .EOF
LodD
MOV [R10], AX
ADD R10, 2
INC R8
JMP .L1

.EOF:
FileClose theFile

Printing the Result

RDTSCP
SHL RDX, 32
OR RAX, RDX
SUB RAX, R15

;; Benchmark finished. RAX = ticks, R9 = most frequent number

StoD Buf_t
MOV EAX, R9D
StoD Buf_n
StdOutput Buf_t, MsgEnd, Buf_n, Eol=Yes, Console=Yes

Result

> numbers.exe
Integer Counting Code Challenge
2611726 Ticks; the number that appears the most is 142

2,6 million ticks for one million numbers is quite efficient — less than three CPU cycles per number, which means roughly 840 µs on my 3.1 GHz Xeon w5-2445 CPU. However, this isn't the fastest method on all CPUs. Some processors have high latency (10-15 cycles) for VPGATHERDD and VPSCATTERDD, and a scalar loop may outperform this, especially with Turbo Boost being more effective without AVX-512. Still, it not only about speed, it was a fun and insightful debugging session. The code may have minor issues, as I didn’t polish it thoroughly due to time constraints.

Anyway, the full code "as is":

;;=======================================================
;;
;; Title:Numbers - AVX-512 approach
;; Purpose:Code Challenge #6: Integer Counting.
;;
;; 23.09.2025 at 08:06:16 by Andrey Dmitriev.
;; 26.09.2025 - benchmark loop added
;;=======================================================
EUROASM AutoSegment=Yes, CPU=X64, SIMD=AVX512, EVEX=ENABLED
numbers PROGRAM Format=PE, Width=64, Model=Flat, IconFile=, Entry=Start:

INCLUDE memory64.htm, winf64.htm, wins.htm, winscon.htm, cpuext64.htm
[.bss] SEGMENT ALIGN=64
EUROASM AutoSegment=yes  ; keep using autosegmentation
MsgStart D "Integer Counting Code Challenge",0 
MsgUsage D "Usage: numbers.exe <File-With-Numbers>",0
MsgEnd D " Ticks; the number that appears the most is ",0
MsgErr D "File Not Found - ",0
File$ D "1M_random_numbers.txt",0
Buf_t DB 128 * B     ; Buffer for Ticks string, act also as guard
Buf_n DB 128 * B     ; Buffer for Number string
align 64
Buf_arr DB 1_000_000 * W ; Aligned Buffer for Input Array of 1M Numbers
Buf_hist DB 1000 * Q     ; Histogramm 1000 elts for up to 1000000 nums

theFile DS FILE64

Start: nop ; For Auto Segmentation
    StdOutput MsgStart, Eol=Yes, Console=Yes ; Welcome message
    GetArg 1 ; RCX is the size of arg (bytes); RSI is ptr to the first char.
    JC .DefaultFile:    ; Report error and show usage if no file was provided.
    StripQuotes RSI,RCX ; Get rid of quotes if they were used.
    MOV RDI, File$  ; Room for the file name.
    REP MOVSB           ; Copy the name.
    SUB AL,AL
    STOSB               ; Zero terminate the string.

.DefaultFile:
    FileAssign theFile, File$
    FileExists? theFile
    JC .ErrorFileNotFound
    
    FileStreamOpen theFile, BufSize=16K
    MOV R10, Buf_arr
    XOR R8, R8 ; R8 is the holder to count lines reset it 
.L1:    
    FileStreamReadLn theFile ; RAX=line size ;RSI=pointer to the line in buffer. 
    JZ .EOF
    LodD ; RSI assumed, parsing stops at LF char; RAX - loaded number
    MOV [R10], AX ; store number in U16 Array
    ADD R10, 2    ; to the next two bytes
    INC R8        ; increment Lines (numbers) counter (do not modify)
    JMP .L1       ; Next line
.EOF:
    FileClose theFile ; No need the File any longer, can be closed now

    MOV EAX, 1
    VPBROADCASTD ZMM16, EAX ; packed dwords of 1 - will be used for increments
    Clear Buf_t, Size=256 ; if it was polluted by long file name string
    Clear Buf_hist, Size=4000 ; Clear Buffer, this will also avoid page fault    
;;=======================================================
;;  Benchmark start here
;;
    CPUID
    RDTSC
    SHL RDX, 32
    OR RAX, RDX
    MOV R15, RAX ; R15 will hold initial Time Stamp counter value
    MOV R14, 1024; amount of benchmark repetitions
.bench:
    MOV RAX, Buf_arr ; All our numbers
    MOV RDX, Buf_hist; Histogram
    CMP R8, 0 ; Check if the list empty
    JE .Exit

    MOV RCX, R8 ; loop counter
    SHR RCX, 4 ; for 1,000,000 / 16 - we will handle 16 values per iteration
    XOR R9, R9 ; index = 0
    KXNORD K0, K0, K0 ; mask of all ones
align 16 ; Recommended by Intel
.loop:
    VPMOVZXWD ZMM1, [RAX + r9]  ; load 32x16-bit words -> ZMM1 (zero-extended)
    VPCONFLICTD ZMM4, ZMM1     ; ZMM4 = conflict indices
    VPXORD   ZMM5, ZMM4, ZMM4   ;
    VPCMPD   k1, ZMM4, ZMM5, 0  ; k1 = lanes with conflict == 0 (unique)
    KNOTW    k2, k1 ; k2 = lanes with duplicates
    KORTESTW k2, k2 ; Check if any duplicates exist
    JNZ .duplicates ; Jump if any duplicates found, proceed to scala approach

    VPSLLD ZMM2, ZMM1, 2        ; ZMM2 = ZMM1 * 4 (byte offsets)
    KMOVD K1, K0                ; Restore Mask
    VPGATHERDD ZMM3, [RDX + ZMM2], MASK=K1 ; gather current histogram values
    VPADDD ZMM3, ZMM3, ZMM16    ; increment each by 1 (which stored in ZMM16)
    KMOVD K2, K0                ; The entire mask register will be set to zero
    VPSCATTERDD [RDX + ZMM2], ZMM3, MASK=K2; scatter updated values
.continue:
    ADD R9, 32 ; MOVe to next 32 elements
    LOOP .loop ; decrement RCX and loop if not zero
    JMP .histogram ; All right, jump to Histogram analysis
.duplicates:
    ; Handle duplicates with scalar loop for this vector
    MOV R11, RAX
    ADD R11, R9
    MOV R12, 16
align 16
.L2:
    MOVZX R13D, [R11], DATA=W
    ADD [RDX+R13*4], 1, DATA=W ; Add count to Histogram                                                                                                                          
    ADD R11, 2
    DEC R12
    JNZ .L2
    JMP .continue

.histogram:
    XOR RAX, RAX 
    XOR R9D, R9D  ; RAX = final result (max index)
    XOR EBX, EBX  ; Current maximum
    MOV RCX, 1000 ; our numbers in Range 0...999
align 16
.L3:
    MOV R10D, [RDX]
    CMP EBX, R10D   ; Is this maximum?
    CMOVL R9D, EAX ; Conditional Move - Branchless swap
    CMOVL EBX, R10D
    INC EAX
    MOV [RDX], 0, DATA=D ; Reset bin for the next run
    ADD RDX, 4 ; no need to keep, next 4 bytes
    LOOP .L3
    DEC R14
    JNZ .bench ; Repeat 1024 times

    RDTSCP
    SHL RDX, 32
    OR RAX, RDX
    SUB RAX, R15 ; Subtract previous stamp
    SHR RAX, 10  ; Divide by 1024 - amount of bench repetitions
;;
;;  Benchmark finished, now RAX contains amount of Ticks and R9 is the number
;;=======================================================
    StoD Buf_t
    MOV EAX, R9D ; Maximal value (index) the number that appears the most.
    StoD Buf_n
    StdOutput Buf_t, MsgEnd, Buf_n, Eol=Yes, Console=Yes ; Print result
    JMP .Exit
.ErrorFileNotFound:
    StdOutput MsgUsage, Eol=Yes, Console=Yes
    StdOutput MsgErr, File$, Eol=Yes, Console=Yes
.Exit:
    TerminateProgram
ENDPROGRAM

Compilation

To compile (or more exactly "assemble"), download EuroAssembler, save the code above as numbers.asm and run:

> euroasm.exe numbers.asm

That’s it.

Update 26-Sep - Scalar solution.

For anyone who has read this up to this point and doesn't have an AVX-512-capable CPU but would still like to experiment with assembly, I've prepared a "naive" scalar version where the histogram is built in a "classical" way. The only optimization I applied is unrolling the loop 4 times. This version will work on any CPU — and on Linux as well:

;;=======================================================
;;
;; Title:Numbers - Naive approach
;; Purpose:Code Challenge #6: Integer Counting.
;;
;; 26.09.2025
;;=======================================================
EUROASM AutoSegment=Yes, CPU=X64, SIMD=AVX2
numnaive PROGRAM Format=PE, Width=64, Model=Flat, IconFile=, Entry=Start:

INCLUDE memory64.htm, winf64.htm, wins.htm, winscon.htm, cpuext64.htm
[.bss] SEGMENT ALIGN=64
EUROASM AutoSegment=yes  ; keep using autosegmentation
MsgStart D "Integer Counting Code Challenge",0 
MsgUsage D "Usage: numbers.exe <File-With-Numbers>",0
MsgEnd D " Ticks; the number that appears the most is ",0
MsgErr D "File Not Found - ",0
File$ D "1M_random_numbers.txt",0
Buf_t DB 128 * B     ; Buffer for Ticks string, atc also as guard
Buf_n DB 128 * B     ; Buffer for Number string
align 64
Buf_arr DB 1_000_000 * W ; Aligned Buffer for Input Array of 1M Numbers
Buf_hist DB 1000 * Q     ; Histogramm 1000 elts for up to 1000000 nums

theFile DS FILE64

Start: nop ; For Auto Segmentation
    StdOutput MsgStart, Eol=Yes, Console=Yes ; Welcome
    GetArg 1 ; RCX is the size of arg (bytes); RSI is ptr to the first char.
    JC .DefaultFile:    ; Report error and show usage if no file was provided.
    StripQuotes RSI,RCX ; Get rid of quotes if they were used.
    MOV RDI, File$  ; Room for the file name.
    REP MOVSB           ; Copy the name.
    SUB AL,AL
    STOSB               ; Zero terminate the string.

.DefaultFile:
    FileAssign theFile, File$
    FileExists? theFile
    JC .ErrorFileNotFound
    
    FileStreamOpen theFile, BufSize=16K

    MOV R10, Buf_arr
    XOR R8, R8 ; reset count lines
.L1:    
    FileStreamReadLn theFile ; RAX=line size ;RSI=pointer to the line in buffer. 
    JZ .EOF
    LodD ; RSI assumed, parsing stops at LF char; RAX - loaded number
    MOV [R10], AX ; store number in U16 Array
    ADD R10, 2    ; to the next two bytes
    INC R8        ; INCrement Lines (numbers) counter
    JMP .L1       ; Next line
.EOF:
    FileClose theFile ; No need the File any longer, can be closed now
    Clear Buf_hist, Size=4000 ; Clear Buffer, this will also avoid page fault

    CMP R8, 0 ; Check if the list empty
    JE .L2
    
;;=======================================================
;;  Benchmark start here
;;
    CPUID
    RDTSC
    SHL RDX, 32
    OR RAX, RDX
    MOV R13, RAX ; R15 will hold initial Time Stamp counter value

    MOV R12, 1024 ; benchmark repetitions
Bench:
    MOV RCX, Buf_arr
    MOV RDX, Buf_hist
    MOV R10, R8
    SHR R10, 2 ; divide by 4 for unrolling
align 16
.L3: ; Fill Histogram in unrolled loop
    MOVZX   EAX, [RCX], DATA=W  ; Load Number value to EAX
    ADD  [RDX+RAX*4], 1, DATA=W ; Increment Histogram Bin                                                                                                                         
    MOVZX   EBX, [RCX+2], DATA=W  ; Load Next number value to EAX
    ADD  [RDX+RBX*4], 1, DATA=W ; and so on                                                                                                                         
    MOVZX   EAX, [RCX+4], DATA=W  
    ADD  [RDX+RAX*4], 1, DATA=W                                                                                                                         
    MOVZX   EBX, [RCX+6], DATA=W
    ADD  [RDX+RBX*4], 1, DATA=W ; unrolled 4 times                                                                                                                         
    ADD RCX, 8 ; Shift to next bytes (2x4)
    DEC R10 ; Next Value
    JNZ .L3
.L2:
    XOR EAX, EAX
    XOR R9D, R9D
    XOR ECX, ECX
align 16
.L5:
    MOV R11D, [RDX]
    MOV [RDX], 0, DATA=D ; Reset bin for the next run
    CMP ECX, R11D
    CMOVL R9D, EAX
    CMOVL ECX, R11D
    INC EAX
    ADD RDX, 4
    CMP AX, 1000
    JNE .L5

    DEC R12
    JNZ Bench

    RDTSCP
    SHL RDX, 32
    OR RAX, RDX
    SUB RAX, R13 ; Subtract previous stamp
    SHR RAX, 10 ; was 1024 runs, therefore divided
;;
;;  Benchmark finished, now RAX contains amount of Ticks and R9 is the number
;;=======================================================
    Clear Buf_t, Size=256
    StoD Buf_t
    MOV EAX, R9D ; MAXimal value (index) the number that appears the most.
    StoD Buf_n
    StdOutput Buf_t, MsgEnd, Buf_n, Eol=Yes, Console=Yes ; Print result
    JMP .Exit
.ErrorFileNotFound:
    StdOutput MsgUsage, Eol=Yes, Console=Yes
    StdOutput MsgErr, File$, Eol=Yes, Console=Yes
.Exit:
    TerminateProgram
ENDPROGRAM

And result? Faster than AVX-512.

>numnaive.exe
Integer Counting Code Challenge
1145561 Ticks; the number that appears the most is 142

1145561 ticks on a 3,1 GHz CPU means approximately 370 µs.

Unfortunately, I wasn't able to break the "1 million CPU ticks for 1 million numbers" barrier. In theory, parallelization across multiple threads is possible, but it likely won't yield significant gains due to the overhead of thread creation and result aggregation.

Update 2: Bonus especially for dear Peter Draganov – this LabVIEW code will display not only the most frequently used number, but all frequently used numbers sorted by frequency:

+-------------------------+
| "1M_random_numbers.txt" |
+-----------+-------------+
            |
            v
+-------------------------------+
| Read Delimited Spreadsheet.vi |<- Transpose = T
+-------------------------------+
            |
            v
    +---------------+
    | Convert to Int|  (Data Type Conversion to Integer)
    +---------------+
            |
            v
    +----------------+
    |  Histogram.vi  |
    +----------------+
            |               +---------------------+
            |-------------->| Histogram Graph     |
            |               +---------------------+
            |
            |
            |   +--------------------+
            |   | Ramp by Samples    | <--- 1000 (bin count)
            |   +--------------------+
            |               |
            v               v
     +-----------------------------------+
     |   Index & Bundle Cluster Array    |
     +-----------------------------------+
            |
            v
+-------------------------+
| Sort 1D Array (Freq.)   |
+-------------------------+
            |
            v
+---------------------+
| Reverse 1D Array     |
+---------------------+
            |
            v
+-------------------+
| Index Array [0]   | ---> most used (most frequent value)
+-------------------+

I don't know why images are not allowed in this challenge (LabVIEW is graphical programming environment).

and the result:

most
used | count

 142 - 1130
 178 - 1101
 677 - 1089
   4 - 1084
  16 - 1083    

Links to images if you're interested — Block Diagram and Front Panel.

Execution time is around 10 ms (excluding file read time). It can be improved, but there’s no chance to reach the microseconds range, since LabVIEW is not the fastest tool.

SELECT TOP 1 n  
From MyTable  
group by n  
Order by count(*) desc

#include <iostream>
#include <unordered_map>

void mFreq() {
    std::unordered_map<int, int> mmap{};
    int tmp{};
    while (std::cin >> tmp) {
        ++mmap[tmp];
    };

    int curr_max{}, curr_max_count{0};
    for (const auto& [num, freq] : mmap) {
        if (freq > curr_max_count) {
            curr_max = num;
            curr_max_count = freq;
        }
    };
    std::cout << curr_max << ' ' << curr_max_count << '\n';
};

int main() {
    mFreq();
    return 0;
};

I decided to take in the input through redirection in order to not need file streams and opening X file with Y name. To me, what made the most sense was to keep an unordered_map of a number and its occurrences. Then I went over the contents of the map and compared the current highest value found with its number of occurrences. If the current frequency was greater than the current_max I updated the values as needed. Finally I just output the result back through stdout. The first number is the value, and the second is the number of occurrences for the value.

*@dsDell:~/Documents/cpp/stackoverflow_challenges/int_counting$ g++ main.cpp -std=c++20 -Wall -o main
*@dsDell:~/Documents/cpp/stackoverflow_challenges/int_counting$ time ./main < 1M_random_numbers.txt 
142 1130

real    0m0.292s
user    0m0.288s
sys 0m0.004s

# System Details Report
---

## Report details
- **Date generated:**                              2025-09-25 11:17:51

## Hardware Information:
- **Hardware Model:**                              Dell Inc. Inspiron 14 7425 2-in-1
- **Memory:**                                      16.0 GiB
- **Processor:**                                   AMD Ryzen™ 7 5825U with Radeon™ Graphics × 16
- **Graphics:**                                    AMD Radeon™ Graphics
- **Disk Capacity:**                               (null)

## Software Information:
- **Firmware Version:**                            1.21.0
- **OS Name:**                                     Ubuntu 24.04.3 LTS
- **OS Build:**                                    (null)
- **OS Type:**                                     64-bit
- **GNOME Version:**                               46
- **Windowing System:**                            Wayland
- **Kernel Version:**                              Linux 6.14.0-29-generic

I'm fairly new to programming and to me this was the best approach I could think of for my favorite language. I just learned about structured bindings and thought this was kind of a great time to test them out. I tried to make my own version without use of the STL but I could not seem to beat its runtime.

from collections import Counter

def most_frequent_numbers(filename):
    # Read all integers from file (one per line or space-separated)
    with open(filename) as f:
        numbers = [int(x) for line in f for x in line.split()]

    # Count frequencies
    counter = Counter(numbers)
    max_count = max(counter.values())

    # Find all numbers with max frequency
    most_common = [num for num, count in counter.items() if count == max_count]

    return most_common, max_count


if __name__ == "__main__":
    # Example: adjust filename to your test file (100, 10,000, or 1,000,000 integers)
    nums, freq = most_frequent_numbers("10000_random_numbers.txt")
    print("Most frequent number(s):", nums)
    print("Frequency:", freq)

How it works

1. Reads the file into a Python list of integers.

2. Uses collections.Counter to count occurrences (O(n) time).

3. Finds the maximum frequency.

4. Returns all numbers that tie for most frequent.

In fact, we could make it even faster/more memory-efficient by using a fixed-size array of length 1000 instead of Counter. That avoids hashing overhead:

from collections import Counter

def most_frequent_numbers_array(filename):
    counts = [0] * 1000  # since numbers are always 0–999

    with open(filename) as f:
        for line in f:
            for x in line.split():
                counts[int(x)] += 1

    max_count = max(counts)
    most_common = [i for i, c in enumerate(counts) if c == max_count]
    return most_common, max_count


if __name__ == "__main__":
    # Example: adjust filename to your test file (100, 10,000, or 1,000,000 integers)
    nums, freq = most_frequent_numbers_array("10000_random_numbers.txt")
    print("Most frequent number(s):", nums)
    print("Frequency:", freq)

This is the fastest way for this problem, since the domain is fixed and small.

Here are the benchmark results on 1,000,000 integers (0–999):

Method 1: collections.Counter

• Time: ~0.16 seconds

• Most frequent number: 284

• Frequency: 23

Method 2: Fixed-size array (length = 1000)

• Time: ~0.19 seconds

• Most frequent number: 284

• Frequency: 23

import time
import random

def most_frequent_number(numbers):
   
    counts = [0] * 1000
    for n in numbers:
        counts[n] += 1

    
    max_count = -1
    max_num = -1
    for i, c in enumerate(counts):
        if c > max_count:
            max_count = c
            max_num = i

    return max_num, max_count


if __name__ == "__main__":
    
    test_data = [1, 2, 2, 5, 7, 7, 7, 3, 2]
    print("Test result:", most_frequent_number(test_data))

    
    data = [random.randint(0, 999) for _ in range(1_000_000)]

    start = time.time()
    num, freq = most_frequent_number(data)
    end = time.time()

    print("Most frequent number:", num)
    print("Frequency:", freq)
    print("Time taken: %.4f seconds" % (end - start))

• Since the input numbers are guaranteed to be in the range 0–999, I didn’t use a dictionary or collections.Counter.

• Instead, I allocated a list of size 1000 to act as counters.

• As I scan through the list once, I increment the appropriate counter.

• After one pass, I just find the index with the highest count.

This solution runs in O(N) time with O(1000) ≈ O(1) space.

After hours and hours and hours of brainstorming I finally gave up and solved it the most unimaginative way:

using System.Diagnostics;

var timer = Stopwatch.StartNew();
// prepare the counting dictionary of (number, occurances)
var dups = Enumerable.Range(0, 1000).ToDictionary(x => x, x => 0);
// read the file as lines
var res = File
    .ReadAllLines("numbers.txt")
        // cast to int while at the same time counting the
        // occurances in the dictionary and returning the
        // number of matches 
    .Select(x => ++dups[int.Parse(x)])
        // take the highest number of matches
    .OrderByDescending(x => x)
    .Take(1)
        // take every key of the dictionary who has the highest number of 
        // occurances (could be multiple ex aequo)
        // also .Select what we want to know as a string for easy logging.
    .SelectMany(x => dups.Where(y => y.Value == x).Select(x => $"{x.Key} ({x.Value} times)"))
;
timer.Stop();
Console.WriteLine(string.Join("\n", res.Take(10)));
Console.WriteLine($"ElapsedMs {timer.ElapsedMilliseconds}");

This gave me 1130 occurances of the number 142 as "winner".

I didn't benchmarked the performance in a loop, but repeatingly dotnet running the program gave me times ranging from 93 to 116 ms on my Surface Laptop Studio. (11370H; 32GB; did not bother to shut down all the programs running in the background)

Explaination

There is nothing much to explain. I used a 1000 length array (as the integer ranges between 0-999) to track frequencies of each integer. While iterating, I am also tracking integer with the highest frequency to avoid additional iteration to get highest value. The complexity of this is O(N).

I tried multiple approaches, with different Obejct (like array vs List). I also tried adding an additional algorithm for early stopping, however the simplest one was the best one. To experiment with all these I ended up creating a helper function, benchmarkFunction. Using which I testing the method over 1000 iterations, and have posted the result below

Output & Benchmarking

Most frequent number is '142'. It occured 1130 times

==== Benchmark Results ====

Total executions performed 1000 which took total of 475.21 ms

 ==== Stats in microseconds ====
Average per execution (microseconds):             475.21
Highest time (microseconds):                     4389.10
Lowest time (microseconds):                       379.60

 ==== Stats in milliseconds ====
Average per execution (milliseconds):               0.48
Highest time (milliseconds):                        4.39
Lowest time (milliseconds):                         0.38
==== ====

Machine Details

Name                      : 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz
NumberOfCores             : 4
NumberOfLogicalProcessors : 8
MaxClockSpeed             : 1382
Total RAM: 15.75 GB
Available RAM: 2.16 MB

Code

import java.io.IOException;
import java.net.URI;
import java.net.http.HttpClient;
import java.net.http.HttpRequest;
import java.net.http.HttpResponse;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.function.Supplier;
import java.util.stream.LongStream;

public class IntegerCounter {

    public static Path downloadFile(String url, String filename) throws IOException, InterruptedException {
        Path outputPath = Paths.get(filename);
        if (Files.exists(outputPath)) {
            return outputPath;
        }
        System.out.println("Downloading: " + url);

        try (HttpClient client = HttpClient.newHttpClient()) {
            HttpRequest request = HttpRequest.newBuilder()
                    .uri(URI.create(url))
                    .build();

            HttpResponse<Path> response = client.send(request,
                    HttpResponse.BodyHandlers.ofFile(outputPath));

            System.out.println("Downloaded to: " + response.body());
            return outputPath;
        }
    }

    public static int[] readIntegersFromFile(Path filePath) throws IOException {
        return Files.lines(filePath)
                .filter(s -> !s.isEmpty())
                .mapToInt((s) -> Integer.valueOf(s.trim()))
                .toArray();
    }

    public static int[] mostFrequentInteger(int[] integers) {
        int[] frequencies = new int[1000];
        int mostFrequent = -1;
        int maxFrequency = 0;

        for (int num : integers) {
            frequencies[num]++;
            if (frequencies[num] > maxFrequency) {
                maxFrequency = frequencies[num];
                mostFrequent = num;
            }
        }
        return new int[] { mostFrequent, maxFrequency };
    }

    public static <T> void benchmarkFunction(Supplier<T> function, int iterations) {
        long[] times = new long[iterations];

        for (int i = 0; i < iterations; i++) {
            long start = System.nanoTime();
            function.get();
            long end = System.nanoTime();
            times[i] = end - start;
        }

        long totalTime = LongStream.of(times).sum();
        long maxTime = LongStream.of(times).max().getAsLong();
        long minTime = LongStream.of(times).min().getAsLong();

        double totalMilliseconds = totalTime / 1_000_000.0;
        double totalMicroseconds = totalTime / 1_000.0;
        double averageMicroseconds = totalMicroseconds / iterations;
        double averageMilliseconds = totalMilliseconds / iterations;
        double maxMicroseconds = maxTime / 1_000.0;
        double maxMilliseconds = maxTime / 1_000_000.0;
        double minMicroseconds = minTime / 1_000.0;
        double minMilliseconds = minTime / 1_000_000.0;

        String decimalFormat = "%-40s %15.2f\n";

        System.out.println("==== Benchmark Results ====");
        System.out.printf("\nTotal executions performed %d which took total of %.2f ms\n", iterations,
                totalMilliseconds);
        System.out.println("\n ==== Stats in microseconds ====");
        System.out.printf(decimalFormat, "Average per execution (microseconds):", averageMicroseconds);
        System.out.printf(decimalFormat, "Highest time (microseconds):", maxMicroseconds);
        System.out.printf(decimalFormat, "Lowest time (microseconds):", minMicroseconds);
        System.out.println("\n ==== Stats in milliseconds ====");
        System.out.printf(decimalFormat, "Average per execution (milliseconds):", averageMilliseconds);
        System.out.printf(decimalFormat, "Highest time (milliseconds):", maxMilliseconds);
        System.out.printf(decimalFormat, "Lowest time (milliseconds):", minMilliseconds);
        System.out.println("==== ====");
    }

    public static void main(String[] args) throws Exception {
        String filename = "1M-integers-list.txt";
        String fileUrl = "https://drive.usercontent.google.com/download?id=14kbAC0edO05Z1EIYbZMC6Gpzx1u2yecd&export=download";
        Path integerFilePath = downloadFile(fileUrl, filename);

        int[] integers = readIntegersFromFile(integerFilePath);
        System.out.println("Read " + integers.length + " integers from file.");

        int[] result = mostFrequentInteger(integers);
        System.out.printf("Most frequent number is '%d'. It occured %d times\n", result[0], result[1]);

        benchmarkFunction(() -> mostFrequentInteger(integers), 1000);
    }
}

My Excel-VBA code took less then 3 seconds for 1 million.

I pasted the numbers in column A of Excel.

Option Explicit

Sub Sample()
    Debug.Print "Start: " & Now
    Debug.Print "The number that appears the most is " & Application.WorksheetFunction.Mode(Sheet1.Columns(1))
    Debug.Print "End: " & Now
End Sub

For multiple numbers, use the below code. This took 4 seconds.

Sub Sample()
    Debug.Print "Start: " & Now
    
    Dim ws As Worksheet
    Set ws = Sheet1
    
    Dim wsNew As Worksheet
    Set wsNew = Sheets.Add
    
    Dim LRow As Long
    Dim i As Long
    Dim Ar As Variant
    
    With wsNew
        .Range("A1").Formula = "=MODE.MULT('" & ws.Name & "'!A:A)"
    
        DoEvents
    
        LRow = .Range("A" & .Rows.Count).End(xlUp).Row
        
        Ar = .Range("A1:A" & LRow).Value2
        
        If IsArray(Ar) Then
            Debug.Print "The numbers that appears the most are:"
            For i = LBound(Ar) To UBound(Ar)
                Debug.Print Ar(i, 1)
            Next i
        Else
            Debug.Print "The number that appears the most is " & Ar
        End If
    End With
    
    Application.DisplayAlerts = False
    wsNew.Delete
    Application.DisplayAlerts = True
    
    Debug.Print "End: " & Now
End Sub

Screenshot: https://www.dropbox.com/scl/fi/ro2tsc51fb3bdug95cqwv/Screenshot-2025-09-25-193143.png?rlkey=3fb0hb0cgq78f7jddehnihvkp&dl=0

Computer Specs Excel.Application.Name: Microsoft Excel
Excel Version: 16
Excel Build: 19127
Excel Bitness (inferred): 64-bit
Operating System: Microsoft Windows 11 Pro (Build 26100, ver 10.0.26100)
OS Architecture: 64-bit
Computer Manufacturer: Gigabyte Technology Co., Ltd.
Computer Model: X870E AORUS ELITE WIFI7
Total Physical Memory (GB): 31.11 GB
CPU: AMD Ryzen 7 9700X 8-Core Processor
Cores / Logical Processors: 45885
Max Clock (MHz): 3800
GPU (primary): NVIDIA GeForce RTX 3080 Ti

C#/.NET solution utilizing Span<T> and less allocations

[MemoryDiagnoser(false)]
public class Benchmark
{
    [Benchmark]
    [Arguments("100_random_numbers.txt")]
    [Arguments("10000_random_numbers.txt")]
    [Arguments("1M_random_numbers.txt")]
    public int GetResult(string fileName)
    {
        var dict = new Dictionary<int, int>();
        using var stream = new FileStream(fileName, FileMode.Open, FileAccess.Read, FileShare.Read);
        using var streamReader = new StreamReader(stream);

        int numberRead;
        Span<char> buffer = new char[4096];

        var parsedValue = 0;
        while ((numberRead = streamReader.ReadBlock(buffer)) > 0)
        {
            for (int i = 0; i < numberRead; i++)
            {
                var item = buffer[i];
                if (item != '\n')
                {
                    parsedValue = parsedValue * 10 + (item - '0');
                    continue;
                }

                if (dict.TryGetValue(parsedValue, out int value))
                {
                    dict[parsedValue] = ++value;
                }
                else
                {
                    dict[parsedValue] = 1;
                }

                parsedValue = 0;
            }
        }

        int max = 0;
        int index = 0;
        foreach (var pair in dict)
        {
            if (pair.Value > max)
            {
                max = pair.Value;
                index = pair.Key;
            }
        }

        return index;
    }
}

Benchmark results (using https://github.com/dotnet/BenchmarkDotNet)

// * Summary *

BenchmarkDotNet v0.15.3, Windows 10 (10.0.19045.6332/22H2/2022Update)
Intel Core i7-10875H CPU 2.30GHz, 1 CPU, 16 logical and 8 physical cores
.NET SDK 9.0.305
  [Host]     : .NET 8.0.20 (8.0.20, 8.0.2025.41914), X64 RyuJIT x86-64-v3
  DefaultJob : .NET 8.0.20 (8.0.20, 8.0.2025.41914), X64 RyuJIT x86-64-v3


| Method    | fileName             | Mean        | Error     | StdDev    | Allocated |
|---------- |--------------------- |------------:|----------:|----------:|----------:|
| GetResult | 100_r(...)s.txt [22] |    547.1 μs |  10.94 μs |  10.74 μs |  22.99 KB |
| GetResult | 10000(...)s.txt [24] |    755.0 μs |  14.95 μs |  25.38 μs |  87.23 KB |
| GetResult | 1M_ra(...)s.txt [21] | 14,770.8 μs | 287.13 μs | 294.86 μs |  87.22 KB |

// * Hints *
Outliers
  Benchmark.GetResult: Default -> 1 outlier  was  removed (584.24 μs)
  Benchmark.GetResult: Default -> 1 outlier  was  detected (686.13 μs)

// * Legends *
  fileName  : Value of the 'fileName' parameter
  Mean      : Arithmetic mean of all measurements
  Error     : Half of 99.9% confidence interval
  StdDev    : Standard deviation of all measurements
  Allocated : Allocated memory per single operation (managed only, inclusive, 1KB = 1024B)
  1 μs      : 1 Microsecond (0.000001 sec)

Using the default methods to read the entire content of file or by line leads to allocation of 30/60/100 MB of memory. Using allocation free Span<T> leads to significant memory optimization (by hundreds of times) and becomes 2-2.5 times faster.

The most appearing numbers (for 100, 10k and 1M integers):

546 (there are multiple numbers appearing twice)

284

142

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

   
    vector<int> freq(1000, 0);

  
    ifstream fin("numbers.txt");
    int x;
    while (fin >> x) {
        freq[x]++;
    }

   
    int maxCount = -1, number = -1;
    for (int i = 0; i < 1000; i++) {
        if (freq[i] > maxCount) {
            maxCount = freq[i];
            number = i;
        }
    }

    cout << "Most frequent number = " << number 
         << " (appears " << maxCount << " times)\n";
    return 0;
}

The code is written in PHP:

<?php
if(empty($argv[1]))die("Usage: {$argv[0]} <text file with integers>\n");
if(($fh=@fopen($argv[1],'r'))===FALSE)die("Cannot open {$argv[1]} for reading\n");
while(($l=fgets($fh))!==FALSE){
  $l=(int)$l;
  if(empty($nums[$l]))$nums[$l]=1;
  else $nums[$l]++;
}
$max=max($nums);
echo "Following number(s) appear(s) the most ($max times): ".implode(', ',array_keys($nums,$max,true))."\n";
fclose($fh);
?>

The algorithm is the simplest I first imagined: create an empty array $nums and fill it with counts of each number in the file (keys are the numbers and values are their counts). After all numbers are processed, the number(s) with highest count $max is/are displayed.

Optimisations I made are:

• not using trim() (it was necessary, as fgets() returns new line in the string), as casting with (int) is enough.

• not initialising $nums=array(), as it is not necessary

• using php function array_keys() with strict option for better performance

Here are the results for time execution on a PC with AMD Athlon(tm) II X4 635 Processor, 16GB RAM and HDD (not SSD) WDC WD5000AAKX:

$ time php intcount2.php 1M_random_numbers.txt
Following number(s) appear(s) the most (1130 times): 142

real    0m0.288s
user    0m0.251s
sys 0m0.033s
$ time php intcount2.php 10000_random_numbers.txt 
Following number(s) appear(s) the most (23 times): 284

real    0m0.094s
user    0m0.051s
sys 0m0.040s
$ time php intcount2.php 100_random_numbers.txt 
Following number(s) appear(s) the most (2 times): 546, 188, 208, 641, 374, 694

real    0m0.093s
user    0m0.055s
sys 0m0.032s

I learned that I can use a filter with array_keys() function.

import time
import random

scratchpad = {}
high = 0
num = 0
## works only if number found is < first elem of list
## -1 means beginning, 1 ends
## list[n] = count(n)
def handlelist(n:int):
    global high, num
    try:
        scratchpad[n]=scratchpad[n]+1
    except:
        scratchpad[n] = 1
    if scratchpad[n] > num:
        num = scratchpad[n]
        high = n

def start(filepath):
    with open(filepath, "r") as f:
        while True:
            s = f.readline()
            if s != "":
                handlelist(int(s))
            else:
                break

def rand(size:int, end:int):
    with open("data.txt", "w") as f:
        for i in range(size):
            val = random.randint(0,end)
            f.write(f"{val}\n")

            
    print(f"{val}:{m}")
#rand(10000, 999)
now = time.perf_counter()
start("1M_random_numbers.txt")
after = time.perf_counter()
print(f"{high}:{num}")
print(f"took {after-now}")

1- the file is read one line at the time
2- each read line is matched to the scratchpad
3- if the scratchpad contains the number then increase the count
3.1- if it doesn't just add the number to scratchpad and leave the count to 1
4- repeat for each line read from file

142:1130
took 0.6354131000007328
Machine Details:
Processor: Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz 2.30 GHz
RAM: 6GB
System: Windows 11 23H2 x64

import random
import time
from collections import Counter
numbers = [random.randint(0, 999) for _ in range(1_000_000)]
start_time = time.time()
counter = Counter(numbers)
most_common_num, count = counter.most_common(1)[0]
end_time = time.time()
print(f"Most frequent num: {most_common_num} (appears {count} times)")
print(f"Execution time: {end_time - start_time:.4f} seconds")

The task was to find the number that shows up the most in a huge list of 1 million numbers. Since the numbers only go from 0 to 999, I realized we don’t need anything fancy, just counting how many times each number appears would be enough. I used Python’s Counter because it’s super fast and already optimized in C for counting things. I just let it scan through the whole list once, then picked the number with the highest count. This makes the code O(N) time complexity, which is perfect for large lists. If I wanted to squeeze out even more speed, I could have used a simple array of size 1000 to count occurrences instead of Counter, since the number range is small. That would skip the hashing overhead entirely.
I ran the code in Google Colab using the free GPU/CPU runtime. The list contained 1 million random integers ranging from 0 to 999. Using Python’s collections.Counter to efficiently count occurrences, the most frequent number was found in 0.098 seconds.
What I learned from this challenge is that choosing the right data structure can make a huge difference in performance. Python’s built-in tools, like Counter, are incredibly efficient for tasks like counting occurrences. I also realized that sometimes, a simple approach—like using an array to count numbers when the range is small—can outperform more complex algorithms. Overall, this challenge reinforced the importance of considering both time and space efficiency, especially when working with large datasets.

def most_frequent_number(filename):
    freq = [0] * 1000  # Since numbers range from 0 to 999

    with open(filename, 'r') as f:
        for line in f:
            for num in line.strip().split():
                freq[int(num)] += 1

    max_count = max(freq)
    most_common = freq.index(max_count)

    return most_common, max_count
if __name__ == "__main__":
    import time

    start = time.time()
    number, count = most_frequent_number("input_1000000.txt")
    end = time.time()

    print(f"Most frequent number: {number} (appeared {count} times)")
    print(f"Execution time: {end - start:.4f} seconds")

Approach

• Read the file data, avoiding unnecessary zeroing of the buffer which will just be overwritten by file data immediately afterward. Memory mapping would be faster, but I stuck with platform agnostic C++ rather than call OS-specific API's.
• Parse the number directly (given the known simple constraints of unsigned numbers 0-999) rather than use std::atoi or std::from_chars.
• Use a simple count table (32-bit integers suffice) knowing numbers range 0-999. Determine the most frequently occurring number (favoring the lower value on ties).
• Build with MSVC using release optimizations set to favor speed.

Code (C++)

#include <iostream>
#include <fstream>
#include <print>
#include <chrono>
#include <algorithm>

const char* fileName = "1M_random_numbers.txt";
//const char* fileName = "10000_random_numbers.txt";
//const char* fileName = "100_random_numbers.txt";

struct FileReadAndCountResult
{
    std::chrono::nanoseconds fileReadDuration;
    std::chrono::nanoseconds numberCountingDuration;
};

FileReadAndCountResult ReadFileAndCountNumbers();

int main()
{
    uint32_t repetitions = 50;
    FileReadAndCountResult totalDurations = {};
    for (uint32_t i = 0; i < repetitions + 1; ++i)
    {
        auto timings = ReadFileAndCountNumbers();
        if (i > 0) // Skip cold start first iteration.
        {
            totalDurations.fileReadDuration += timings.fileReadDuration;
            totalDurations.numberCountingDuration += timings.numberCountingDuration;
        }
    }

    totalDurations.fileReadDuration /= repetitions;
    totalDurations.numberCountingDuration /= repetitions;

    std::println("Filename: {}", fileName);
    std::println(
        "Average file read duration: {} nanoseconds ({} seconds)",
        totalDurations.fileReadDuration.count(),
        totalDurations.fileReadDuration.count() / 1e9
    );
    std::println(
        "Average number counting duration: {} nanoseconds ({} seconds)",
        totalDurations.numberCountingDuration.count(),
        totalDurations.numberCountingDuration.count() / 1e9
    );
    auto combinedDuration = totalDurations.fileReadDuration + totalDurations.numberCountingDuration;
    std::println(
        "Average total duration: {} nanoseconds ({} seconds)",
        combinedDuration.count(),
        combinedDuration.count() / 1e9
    );

    return EXIT_SUCCESS;
}

FileReadAndCountResult ReadFileAndCountNumbers()
{
    std::ifstream inputStream(fileName, std::ios::binary);
    if (!inputStream.is_open())
    {
        std::cerr << "Could not open the file - '" << fileName << "'" << std::endl;
        return {};
    }

    std::string dataBuffer;

    auto preFileReadTime = std::chrono::high_resolution_clock::now();
    {
        // Avoid unnecessary zeroing of the buffer which will just be overwritten anyway.
        // The transient indeterminate values between resize_and_overwrite and read are irrelevant.
        inputStream.seekg(0, std::ios_base::end);
        std::size_t fileSize = inputStream.tellg();
        inputStream.seekg(0, std::ios_base::beg);
        auto dummyResize = [](char* buffer, std::size_t fileSize) noexcept -> size_t { return fileSize;};
        dataBuffer.resize_and_overwrite(fileSize, dummyResize);
        inputStream.read(dataBuffer.data(), fileSize);
        inputStream.close();
    }
    auto postFileReadTime = std::chrono::high_resolution_clock::now();

    int counts[1000] = {};
    int currentValue = 0;
    int mostFrequentCount = 0;
    std::vector<int> mostFrequentValues;
    const char* data = dataBuffer.data();

    auto preNumberCountingTime = std::chrono::high_resolution_clock::now();
    {
        // Include the trailing nul character in the processing loop,
        // rather than any special handling for the terminal condition.
        for (size_t i = 0, dataLength = dataBuffer.size() + 1; i < dataLength; ++i)
        {
            char c = data[i];

            // Given the known limit of numbers 0-999, use faster/simpler logic than std::from_chars.
            if (c >= '0' && c <= '9')
            {
                currentValue = (currentValue * 10) + (c - '0');
            }
            else
            {
                if (currentValue < std::size(counts))
                {
                    ++counts[currentValue];
                }
                currentValue = 0;
            }
        }

        // Find the count of the most frequent numbers
        // (there could be more than with the same count).
        for (int i = 0; i < std::size(counts); ++i)
        {
            if (counts[i] > mostFrequentCount)
            {
                mostFrequentCount = counts[i];
            }
        }

        // Collect all the numbers with the same count.
        for (int i = 0; i < std::size(counts); ++i)
        {
            if (counts[i] == mostFrequentCount)
            {
                mostFrequentValues.push_back(i);
            }
        }
    }
    auto postNumberCountingTime = std::chrono::high_resolution_clock::now();

    auto fileReadDuration = std::chrono::duration_cast<std::chrono::nanoseconds>(postFileReadTime - preFileReadTime);
    auto numberCountingDuration = std::chrono::duration_cast<std::chrono::nanoseconds>(postNumberCountingTime - preNumberCountingTime);

    std::println("Most frequent count: {}, values: {}", mostFrequentCount, mostFrequentValues);
    std::println("File read duration: {} nanoseconds", fileReadDuration.count());
    std::println("Number counting duration: {} nanoseconds", numberCountingDuration.count());
    std::println();

    return {fileReadDuration, numberCountingDuration};
}

Results

• Filename: 100_random_numbers.txt
  • Most frequent values: 188, 208, 374, 546, 641, 694
  • Count: 2
• Filename: 10000_random_numbers.txt
  • Most frequent value: 284
  • Count: 23
• Filename: 1M_random_numbers.txt
  • Most frequent value: 142
  • Count: 1130

Performance numbers

• Filename: 100_random_numbers.txt (0.00002657s)
  • Average file read duration: 26566 nanoseconds
  • Average number counting duration: 716 nanoseconds (0.000000716s)
• Filename: 10000_random_numbers.txt (0.00006143s)
  • Average file read duration: 38550 nanoseconds
  • Average number counting duration: 22882 nanoseconds (0.00002288s)
• Filename: 1M_random_numbers.txt (0.00454427s)
  • Average file read duration: 2300598 nanoseconds
  • Average number counting duration: 2243674 nanoseconds (0.00224367s)

Machine details

Processor: 13th Gen Intel(R) Core(TM) i7-13700KF (3.40 GHz)
Installed RAM: 48.0 GB (47.9 GB usable)
System type: 64-bit operating system, x64-based processor
Edition: Windows 11 Enterprise, Version 24H2, OS build 26100.6584

"""
  Integer counting.
"""

import timeit
from collections import defaultdict

t1 = timeit.default_timer()

freq = defaultdict(int)
with open("1M_random_numbers.txt", 'r') as f:
    for line in f:
        freq[int(line.strip())] += 1
        
        
answer = max(freq, key=freq.get)
print("Max is: ", answer)

t2 = timeit.default_timer()
    

print(t2-t1)

This takes 0.53 seconds on my laptop. Windows. Processor is Intel i9-12900HK.

The approach is just to go through the list updating a frequency dictionary. Then just returning the key with the maximum value.

The insight is that there are only 1000 possible values in the input, and the length of the file will likely be no more than 1000000 * 5, or 5 MB, which is not that large for modern computers.

Rather than being really clever and save memory, I have taken the easy way out. I have coded the contest functionality as a single tcl proc using pure tcl (no extensions).

1. Open the data file

2. Read the entire data file into a variable that will be treated as a list

3. Close the data file

4. Set the value of variables for the maximum count and number corresponding to the maximum count to -1

5. Starting with an empty count array, loop through each element of the list read from the input file, for each element:

   1. increment the count array element indexed by the number from the input list, save a copy of the resulting value in a local variable

   2. compare the local variable to the value of the current maximum count variable, if it is greater then update the maximum count variable with the value of the temporary variable and the variable with the corresponding number with the list element value

6. When the loop completes, return the value of the variable containing the number corresponding to the maximum count

The code for the function itself is:

proc contest filename {
   # Open and read the text file containing decimal integers
   # in the range 0-999 as a single string. The line terminators
   # serve as whitespace between the numbers when the string is treated
   # as a tcl list.
   set fd [open $filename r]
   set list [read -nonewline $fd]
   close $fd

   # The tcl variable "list" (not to be confused with the tcl command of
   # the same name) now contains all of the data for this run.
   # Initialize some variables...
   set maxcnt -1 ; # A copy of the maximum count seen in the count array
   set maxnum -1 ; # The number corresponding to the max count
   array set cnt {} ; # Note: This is not really needed
   foreach w $list { ; # Run through all numbers in the input string
      # Note that incrementing a nonexistent element creates it with val 1
      set t [incr cnt($w)]
      # compare the count calculated against the maximum we've seen
      if {$t > $maxcnt} { ; # new maximum
         set maxcnt $t ; # save the maximum
         set maxnum $w ; # save the value that corresponds to the maximum
      }
   } ; # end of loop
   # puts stdout "Out of [llength $list] numbers, $maxnum was seen $maxcnt times"
   # return the most frequent number ; ties go to the first one seen
   return $maxnum
}

# driver code for contest function that prints out a timing
proc test {argv} {
    set filename [lindex $argv 0]
    if {[file exists $filename]} {
       set runtime [time {set m [contest $filename]}]
       puts stdout "most frequent number: $m, $runtime"
    } else {
       puts stderr "Unable to open input file \"$filename\""
    }
}

if {($tcl_interactive == 0) && ([llength $argv] > 0)} {
   test $argv
}

System I ran it on:

• Dell Precision 7820 tower workstation

• 2 Intel(r) Xeon(r) Silver 4214R CPUs running at 2.4GHz base frequency (total of 24 cores (up to 48 threads) across 2 chips)

• 96 GiB RAM

• Microsoft Windows 11 enterprise

• Tcl version 8.6 (BAWT, built with GCC)

From a git bash command line with the downloaded 1,000,000 number data file, the result reported by proc test was 299405 microseconds, and by the "time" command was 1.182s real, and 0 seconds user and sys. I have not had a chance to run it on a Linux system, and I think the user and sys times are not actually measured with git bash on Windows. There is a large discrepancy between the time reported by the code and by the time command in git bash is the AV and other security software that my employer has installed. Removing the data file name from the command line still reports 0.885 seconds for "real"; the difference is 0.297 seconds (297000 microseconds), which is close to the value reported by the printout from the code itself.

I'm certain that this program can be duplicated in python and most likely quite a few other scripting languages. I could also write it in a compiled language, but it would take substantially longer than the 10 minutes it took to write and test this one plus the data generator for the 1,000,000 number file that I first tested on.

$ time /c/Tcl8.6/bin/tclsh contest-entry.tcl

real    0m0.885s
user    0m0.000s
sys     0m0.000s

$ time /c/Tcl8.6/bin/tclsh contest-entry.tcl ../Downloads/1M_random_numbers.txt
most frequent number: 142, 299405 microseconds per iteration

real    0m1.182s
user    0m0.000s
sys     0m0.000s

$

[edit: Updated numbers for the run on the downloaded 1M sample file rather than my own locally generated file and to put the final run's output in.]

A Perl solution. It keeps a number of occurrences for each number in a hash, at the end it finds the maximal value and outputs the corresponding key.

Takes 0.165s on my machine to process the 1M file.

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

use List::Util qw{ max first };

my %seen = (0 => 0);
while (<>) {
    ++$seen{$_};
}
my $max = max(values %seen);
say first { $seen{$_} == $max } keys %seen;

If several numbers have the maximum frequency, it outputs a random one of them.

The code is written in C for a maximum speed. On a Apple iMac M3 16GB, Sequoia 15.7 using the "cc" compiler, the calculation takes between 50 to 60ms.

The approach is quite simple: as numbers are only from 0 to 999, I create an array to store the occurrences (which takes 8KB on a 64 bit machine). Then I read the input file and add 1 for each occurence. Then I check the maximum of occurrences after (doing this during the main loop is also possible and does not take extra visible time).

With -O3 (for a maximum of optimization), the code is up to 20% faster (only 50ms as a maximum). The speed of the disk is the main reason for the results. The analyse of the string through isdigit() is faster than using atoi() mainly because we do not scan twice I suppose.

Note if 2 numbers have the same number of occurrences, only the minimum value is displayed.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
 
#define BUFFER_SIZE 1000
#define LINE_SIZE 100
 
int main(int argc, char *argv[]) {
    char line[LINE_SIZE];
 
       if(argc < 2){
           fprintf(stderr, "Usage %s <file>\n", argv[0]);
           return 1;
       }
       
       FILE *f = fopen(argv[1], "rt");
       if(!f){
           fprintf(stderr, "Can not open file [%s]", argv[1]);
           return 1;
       }
 
       int array[BUFFER_SIZE]; // Store the occurences of the numbers
       memset(array, 0, BUFFER_SIZE * sizeof(int));

       while(fgets(line, LINE_SIZE, f)){
           int valid = 0;
           int value = 0;
           char *c = line;
           while(isdigit(*c)){
              valid = 1;
              value = value * 10 + (*c - '0');
              c++;
           }
 
           if(value < 0 || value > BUFFER_SIZE){
              fprintf(stderr, "Invalid value \"%s\" found.", line);
              return 1;
           }

           if(valid) array[value]++;
       }

    int imax = array[0];
    int i;
    for(i = 1; i < BUFFER_SIZE; i++){
        if(array[i] > array[imax]) imax = i;
    }
 
    fprintf(stdout, "%i\n", imax);
    fclose(f);
    return 0;
}
 

C# method to identify the most frequent value in a list of integers.

int? IdentifyMostFrequentNumber(List<int> sourceNumbers)
{
    var mostFrequentNumber = new Tuple<int?, int>(null, 0);

    while (sourceNumbers.Count > 0)
    {
        var currentNum = sourceNumbers[0];
        var count = sourceNumbers.RemoveAll(x => x == currentNum);
        if (count > mostFrequentNumber.Item2)
        {
            mostFrequentNumber = new(currentNum, count);
        }
    }

    return mostFrequentNumber.Item1;
}

Given a list of integer values as a parameter called sourceNumbers, create a Tuple called mostFrequentNumber that will be used to store and return results.

mostFrequentNumber.Item1 holds the current value with the highest count. mostFrequentNumber.Item2 holds the count of that value.

While loop continues processing while sourceNumbers contains values.

Process steps:

1. Identify value held within sourceNumbers[0].

2. Remove all instances of the value identified in step #1. The RemoveAll() method returns the number of values that were removed. Store that value.

3. Compare the number of values removed in step #2 with the value held inside mostFrequentNumber.Item2. If higher, update mostFrequentNumber.Item1 with the value retrieved in step #1 and update mostFrequentNumber.Item2 with the value retrieved in step #2.

After the exit condition is reached, return the value held inside mostFrequentNumber.Item1. If the value is null, the list must have been empty.

If there are multiple numbers that share the highest number of duplicate values, this method will return with the first number that it encounters.

Code execution runtimes:

Running this method 10 times in a row, in a loop:

Test 1

0 - Completed in 1.439096 seconds.
1 - Completed in 1.054102 seconds.
2 - Completed in 1.033286 seconds.
3 - Completed in 1.031074 seconds.
4 - Completed in 1.027072 seconds.
5 - Completed in 1.032201 seconds.
6 - Completed in 1.034445 seconds.
7 - Completed in 1.031518 seconds.
8 - Completed in 1.03722 seconds.
9 - Completed in 1.03466 seconds.

Test 2

0 - Completed in 1.435974 seconds.
1 - Completed in 1.027727 seconds.
2 - Completed in 1.034257 seconds.
3 - Completed in 1.033122 seconds.
4 - Completed in 1.034453 seconds.
5 - Completed in 1.041108 seconds.
6 - Completed in 1.035168 seconds.
7 - Completed in 1.036804 seconds.
8 - Completed in 1.037052 seconds.
9 - Completed in 1.041603 seconds.

Test 3

0 - Completed in 1.426722 seconds.
1 - Completed in 1.033837 seconds.
2 - Completed in 1.034194 seconds.
3 - Completed in 1.028629 seconds.
4 - Completed in 1.026413 seconds.
5 - Completed in 1.028895 seconds.
6 - Completed in 1.025808 seconds.
7 - Completed in 1.033369 seconds.
8 - Completed in 1.030351 seconds.
9 - Completed in 1.035759 seconds.

The first execution usually takes between 1.4-1.5 seconds. Subsequent executions normally fall between 1.02 and 1.06 seconds.

The machine that this was tested/developed on is a MacBook with Apple M2 Pro Chip (12 cores) and 32GB of RAM.

This was an interesting project. I had to write a few different versions before I was happy with the result.

sort -n FILE | uniq -c | sort -n | tail -1 | awk -F' ' '{print $NF}'

Algorithm

Use a Linux pipeline, consisting of five stages.

1. The sort -n command sorts the list of numbers numerically.

2. Given a sorted list, the uniq -c command outputs the number of appearances of a number, followed by the number itself, e.g. 1130 142 tells that 142 has appeared 1130 times.

3. Apply sort -n again, to sort by the number of appearances

4. Select the last line, i.e. the one containing the number appearing most often.

5. Return the second part of the last line only, i.e. the number in question.

Tests

$ time sort -n 100_random_numbers.txt | uniq -c | sort -n | tail -1 | awk -F' ' '{print $NF}'
694

real    0m0.003s
user    0m0.007s
sys 0m0.000s

$ time sort -n 10000_random_numbers.txt | uniq -c | sort -n | tail -1 | awk -F' ' '{print $NF}'
284

real    0m0.007s
user    0m0.009s
sys 0m0.002s

$ time sort -n 1M_random_numbers.txt | uniq -c | sort -n | tail -1 | awk -F' ' '{print $NF}'
142

real    0m0.217s
user    0m1.046s
sys 0m0.032s

My machine:

$ uname -a
Linux sebastian-t480s 6.12.38+deb13-amd64 #1 SMP PREEMPT_DYNAMIC Debian 6.12.38-1 (2025-07-16) x86_64 GNU/Linux

Time Complexity

The sorting algorithm in coreutils has a runtime complexity of O(n log n), uniq, tail and awk all show O(n). Overall, the pipeline has a runtime complexity of

O(n log n) + O(n) + O(n log n) + O(n) + O(n), which reduces to O(n log n).

No solution based on sorting will reach faster worst-case time complexity.

Are there any solutions which do not require sorting?