array overflow

[samarth123]

how to store 10^9 numbers in an array.

[doug4]

int reallyBigArray[1000000000];

std::vector<int> reallyBigVector;
reallyBigVector.reserve(1000000000);

for (int i = 0; i < 10000000000; ++i)
{
    reallyBigArray[i] = i;
    reallyBigVector[i] = i;
}

[keanedawg]

There was an interesting discussion where the forum members concluded that it was pretty much impossible to store an array if it was too large (like 10^50). http://www.cplusplus.com/forum/beginner/12352/


However, this seems more reasonable. I'm honestly not sure. Would storing on the heap be a consideration? I'm sorry if that's dumb. I've never had a problem like this.

[dhayden]

Storing 1 billion numbers will push you right up against the memory limit on a 32-bit machine. If you're running a 64 bit OS and compiling a 64 bit program then it's much more reasonable.

But I have to ask, do you really need to store a billion numbers in memory? Do you require random access to the elements in the array? If you are accessing them sequentially then you would probably be better off storing the data in a file and reading it in one number at a time.

[keanedawg]

On a sidenote, I wonder if you can't allocate 1 billion sized stack array because the compiler won't let you, or because it's physically impossible. I mean, you can do it on the heap.

[samarth123]

I have to input a number 'n'.
1<=n<=10^9.So i wanted to make an array of 'n' elements.
How can i do this.

[keanedawg]

Well the answer is that there certainly are ways but none of them are probably as simple or as elegant as you like.

Again, you could try heap allocation
int * numArray = new int[100000000]


And now you have a heap array. But assuming you don't know anything about dynamic memory allocation, this could be kinda bad.

[Gamer2015]

or you use the STL and use a fancy class called vector

#include <vector>
#include <iostream>

int main() {
    unsigned int n;
    std::cout << "How many integers do you want to store?\n";
    std::cin >> n;
    
    std::vector<int> arr(n); // creates vector with n elements

    return 0;
}

[dhayden]

I have to input a number 'n'.
1<=n<=10^9.So i wanted to make an array of 'n' elements.

Just because you need a number 1<=n<=10^9 doesn't mean you need to store all of them in RAM. Could you describe the problem you're trying to solve? What are the inputs and outputs? Chances are good that there's a way to do it without needing such a large array.

[samarth123]

@dhayden.
Chef has bought N robots to transport cakes for a large community wedding. He has assigned unique
indices, from 1 to N, to each of them. How it will happen?
Chef arranges the N robots in a row, in the (increasing) order of their indices. Then, he chooses the first M
robots and moves them to the end of the queue. Now, Chef goes to the robot at the first position in the row
and hands it one cake. He then notes this robot's index (say k) in his notebook, and goes to the kth position
in the row. If the robot at this position does not have a cake, he give him one cake, notes his index in his
notebook, and continues the same process. If a robot visited by Chef already has a cake with it, then he
stops moving and the cake assignment process is stopped.
Chef will be satisfied if all robots have a cake in the end. In order to prepare the kitchen staff for Chef's wrath
(or happiness :) ), you must find out if he will be satisfied or not? If not, you have to find out how much robots
have a cake, so that the kitchen staff can prepare themselves accordingly.
Input
The first line of input contains a single integer T denoting the number of test cases.
The single line of each test cases contains two space separated integers N and M.
Output
For each of the T test cases, output a single line:
If all N robots have a cake, output "Yes" (without quotes).
Otherwise, output "No" (without quotes) followed by a space and the number of robots which have a cake.
Constraints and Subtasks
1 ≤ T ≤ 10
0 ≤ M < N
Subtask 1: 25 points
1 ≤ N ≤ 10^5
Subtask 2: 75 points
1 ≤ N ≤ 10^9
Example
Input:
3
2 0
2 1
4 2
Output:
No 1
Yes
No 2
Explanation
In test case 1, we have two robots indexed 1 and 2. They are arranged as (1 2). Chef goes to the first robot,
gives him a cake, and moves to position 1. In the next step, he sees that robot at this position already has a
has cake. So Chef stops moving, and our answer is "No 1".
In test case 2, we again have two robots indexed 1 and 2. Initially, they are arranged as (1 2). Then, Chef
moves robot#1 to the end of the row, and thus the arrangement becomes (2 1). Chef goes to the robot at the
first position, which is robot#2. Chef hands him a cake, and moves to position 2. Then, he hands a cake to
robot#1 at position 2, and moves back to the first position. Since, robot#2 at the first position already ahs a
cake, Chef stops moving. All N robots have cakes, so Chef is satisfied, and our answer is "Yes".
In the 3rd test case, we have the following arrangement of robots: (3 4 1 2). Only robots with indices 3 and 1
will get cakes. So our answer is "No 2".

[helios]

I believe it can be solved using a fixed (and small) amount of memory using modulo N algebra. Furthermore, I think this is what the exercise intends to show.

[kalki]

I dont think that much memory you can access where you have 32-bit of device. So better to go Heap memory and dynamically allocate and de-allocate memory for you array during Run time.

[dhayden]

I think Helios is right. This same problem recently came up here. Try doing a few small examples by hand and look for a pattern.

If you can't figure it out then consider this approach: do you really need to store a vector of numbers? Why not use std::vector<bool> instead. This template is specialized to use a single bit for each value.

[samarth123]

Well how can i implement the modulo N algebra in this.

[helios]

Hah, well, that's the point of the exercise, isn't it? I already learned how to do it, so now it's your turn.

[samarth123]

well ok i will try it.thnxx