1

I have to print product of elements of array A mod 10^9+7,there should N elements in array and the constraints are 1<=N<=10^3 and 1<=A[i]<=10^3.

The code I wrote

#include<stdio.h> 
int main()
{
    int N, pro = 1;
    scanf("%i", &N);
    int arr[N];
    for (int i = 0; i<N; i++) {
        scanf("%i", &arr[i]);
        pro = (pro*arr[i]) % (1000000007);
    }      
    printf("%i", pro);
}

gave wrong answer but when I replaced int arr[N] to long int arr[N] and changed its precision specifier to %li it gave correct output. My confusion is when the upper limit of array's elements is only 10^3 then why using long int worked and not just int. i am using 64 bit windows OS and the inputs which i am giving are 3 digit numbers as array elements for example 568,253 etc without any 0 in beginning.

return0
  • 215
  • 2
  • 9
  • Your title mentions `long long int`, but your questions makes no reference to that type. Maybe delete it from the title Monika? – gsamaras Jun 29 '18 at 09:09
  • 1
    The [limits of integer types](https://en.cppreference.com/w/c/types/limits#Limits_of_integer_types) are defined in the `` header file. You can also quite easily check the limits using the `sizeof` operator, as it will tell the number of bytes a type uses, which can then be translated to a number of bits, which defines the range. And remember that the size of the standard integer types may differ between systems, platforms, compilers, and even between the same compiler on different platforms. – Some programmer dude Jun 29 '18 at 09:10
  • The real question is what the size of `int` is on your specific system. On a system with 32 bit integers, I wouldn't expect `long int` to change anything. Are you using an embedded system or some old DOS junk like Turbo C? – Lundin Jun 29 '18 at 09:12
  • Probably your system default `int` as `short int`. Otherwise `int arr[N]` and `long int arr[N]` are same as default `int` is `long` in `32 bit`system. – Achal Jun 29 '18 at 09:15
  • 1
    Maybe it doesn't have to do with the limits, but with the "%i". See if this helps: https://www.geeksforgeeks.org/difference-d-format-specifier-c-language/ – Alex G Jun 29 '18 at 09:16
  • i wrote long long int on the title because i tried another making this code work by letting the size of arr[N] as int itself and changing the data type of pro to long long int but again this worked. confused – return0 Jun 29 '18 at 09:18
  • Uh right, you aren't actually typing the input with a leading `0`, are you? Because that would bug up things, you'd get octal numbers. – Lundin Jun 29 '18 at 09:30
  • no the inputs that i am providing are 3 digit numbers without any leading 0. – return0 Jun 29 '18 at 09:39
  • Can you give us the command you enter please ? NB: `10^7 = 10000000 and not 1000000007)` – Umaiki Jun 29 '18 at 09:39
  • you mean the input ? also i meant 10^9+7 not 10^7 ,i just edited that.thanks – return0 Jun 29 '18 at 09:46
  • Please _edit the post_ and provide all the necessary information. What is the input, which system is this, etc. Voting to close this until then, as nobody will be able to reproduce the problem. – Lundin Jun 29 '18 at 09:56
  • Possible duplicate of [how to find muliplication of large numbers modulo 100000007](https://stackoverflow.com/questions/12235008/how-to-find-muliplication-of-large-numbers-modulo-100000007) – Bo Persson Jun 29 '18 at 11:43

2 Answers2

1

The problem may be the result of the expression (pro*arr[i]). If we assume that the maximum value of pro is 1000000006 due to the modulo, and the maximum value of arr[i] is 10^3 as mentioned. So, this expression may take a value greater than a 32bit integer.

The other thing to look for is What the type of (pro * arr[i]) ? :

The compiler answers this question by look to the operands of the expression, and will set the return type, for integer, as the greater type of them.

If you set arr[] as an long int [] this expression will return a long integer, whereas, if you set arr[] as an int, it will return an int and so it'll be wrong :

int * int -> int
int * long int -> long int
Paul Ankman
  • 190
  • 9
  • Eh, what? Why is `arr[i]` limited to 10^3? Also, most of the answer is confusing... Either the constant `1000000006` is of type int, in which case `arr[i]` will fit numbers up to 2^31-1 and this bug wouldn't happen. Or the constant is of type long, in which case the operand `arr[i]` will get promoted to long, the calculation done by long, then truncated back to int. – Lundin Jun 29 '18 at 09:55
  • @Lundin It is a competitive programming question, where upper limit constraints are provided. – jainilvachhani Jun 29 '18 at 09:57
  • 1
    This explains why you have "fixed" your problem, but you have made your array unnecessarily big in doing so. You would get the same "fix" by declaring `pro` as a big int, and that might be acceptable. But the ideal fix is to keep the array elements as small as you need, but immediately cast the content to bigger int before doing the multiply: `pro*(long long int)arr[i]` – Gem Taylor Jun 29 '18 at 09:58
1

Consider the case where N = 3 and A = [10^3,10^3,10^3]. After the second iteration, your product will be 10^9. In the third iteration, your product will be (10^9 * 10^3) % 1000000007. Before doing the modulo operation, the product would create integer overflow and hence the WA.

jainilvachhani
  • 708
  • 6
  • 13