0

This program is written in C++

The purpose of this program is to read set of numbers that is <= 100,000 into an array and then sum up consecutive numbers and test if they are a multiple of N. Once sum % N == 0 is true then the program outputs the indices of i and j showing exactly from which positions i through j sum to be a multiple of N. There could be multiple solutions, but only one is required so once a solution is found the bool variable is set to true to exit the loop.

My code does correctly calculate a single solution, however, it doesn't do it efficiently enough. Furthermore, I am told that the use of an unsigned sum variable is not necessary as a standard int sum variable is enough to satisfy the requirements of this program. Without the unsigned version of sum I encountered overflow that seemed to ruin my calculations as each test case does contain 100,000 combinations of integers.

Any help or direction is appreciated. Thank you!

#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    int testCases = 0, n = 0;
    
    unsigned int sum = 0;
    
    const int arraySize = 100000;
    
    int array[arraySize];
    
    ofstream outFile ("output.txt");
    
    ifstream inFile ("input.txt");
    
    inFile >> testCases;
    
    while(testCases > 0)
    {
        
        bool found = false;
        
        inFile >> n;
                
        for(int a = 0; a < n; a++)
            inFile >> array[a];
    
        for(int i = 0; i < n && !found; ++i)
            for(int j = i; j < n && !found; ++j)
            {
                sum = 0;
            
                for(int d = i; d <= j; d++)
                    sum += array[d];
                                
                if (sum % n == 0)
                {
                    outFile << i << ' ' << j << endl;
                    found = true;
                }
                    
             }
        testCases--;
    }
            
    outFile.close();
    inFile.close();
    
    return 0;
}
Mark Keasal
  • 1
  • 1
  • 1
    Looks like the same homework problem as [this one](https://stackoverflow.com/questions/69674853/finding-number-of-pairs-product-of-whose-indices-is-divisible-by-another-number). Maybe you folks can get together. – President James K. Polk Oct 22 '21 at 17:00
  • Why do you need a nested `for` loop to solve this problem? Couldn't you make a single pass through the loop and use some logic in each pass, thus making this an `O(n)` complexity? – PaulMcKenzie Oct 22 '21 at 17:04
  • If your code is too slow, you usually have to many iterations. Rethink the approach to your solution, it is not a code problem. (Also note this is why I don't like competitve coding sites, they teach you problem solving, but not how to write good software) – Pepijn Kramer Oct 22 '21 at 17:07
  • Maybe [this helps?](https://stackoverflow.com/questions/8269916/what-is-sliding-window-algorithm-examples) – PaulMcKenzie Oct 22 '21 at 17:11
  • What are the constraints on input data? There is a crafty way to do it with `o(n)` or `o(n long n)` complexity depending on those constraints. – Marek R Oct 22 '21 at 17:13
  • @PresidentJamesK.Polk K. Polk - After reading your reply to him it does give me some ideas. Thank you. – Mark Keasal Oct 22 '21 at 17:28
  • @PaulMcKenzie I may not need a nested for loop, I'll try to see if I can reduce it. Thank you. – Mark Keasal Oct 22 '21 at 17:29
  • @MarekR The only restraints are that there will be at most 10 test cases and 2 <= n <= 100000 – Mark Keasal Oct 22 '21 at 17:31
  • just to be clear: `n` defines two things: modulo operation and size of the array. There is no other value distinguishing those two. – Marek R Oct 23 '21 at 07:32
  • @MarekR Yes, you are correct! – Mark Keasal Oct 24 '21 at 09:35
  • Is it absolutely necessary to read the entire input file before you begin processing? – Den-Jason Oct 25 '21 at 09:01

1 Answers1

0

Problem with your program is that it has high time complexity. Each test case run two nested for loops n times. This means that your program has O(n^2) complexity. This is quite poor for this problem.

Now the trick here is to track indexes for partial sums modulo n in some data structure. When you adding new item x to this data structure first you should check if it already contains element for partial sum equal to (n - x) % n, if it has then you will be able to find begin and end index for your solution. This approach will give you o(n) complexity or o(n log n) depending what kind of data structure you will use.

I will give just this hint (which IMO is more then enough to find solution), since IMO giving ready solution is not a good teaching practice. If you have more question let me know.

Offtopic: do not use std::endl it slows down IO operations a lot. Replace it with '\n'.

Marek R
  • 32,568
  • 6
  • 55
  • 140