Remainder When Divided By 11

Easy

0/40

Average time to solve is 15m

15 upvotes

Asked in companies

Problem statement

You are given a number N. You need to find the remainder when N is divided by 11.

Note :

Number N may be very large.

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line contains an integer 'T' denoting the number of test cases to be run. The 'T' test cases follow. 

The first line of each test case contains a single number 'N' in the form of a string.

Output Format :

For each test case, print an integer denoting the remainder when 'N' is divided by 11.

Constraints :

1 <= T <= 5
1 <= length of N <= 10 ^ 6

Time Limit: 1 sec

Sample Input 1 :

2
4475
345

Sample Output 1 :

9
4

Explanation For Sample Input 1 :

For test case 1: When 4475 is divided by 11, the remainder comes out to be 9.

For test case 2: Similarly, when 345 is divided by 11, the remainder comes out to be 4.

Sample Input 2 :

2
55554444333
1331231

Sample Output 2 :

3
0

Hint 1

Store the number in the string and use modulo properties to calculate the remainder.

Approaches (1)

Approach 1

Using Modulo Property

Since the number is very large we can not simply calculate N % 11.
Now, any number say 256 % 11 can be calculated as (25*10 + 6)%11. Which in turn can be calculated as (( 25*10)%11+ 6)%11 or ( (25%11)*10 + 6)%11. Similarly 25%11 can be calculated as (2*10+5)%11. Therefore , 256 %11 can be finally calculated as ( ( (2*10 + 5)%11 )*10 + 6)%11.
So, the idea is to store the number N in string Str.
Take a variable Num, initialize it with 0.
Now iterate character by character over the string and convert it into a digit, starting from 0th index.
Multiply your current Num by 10 and add the current digit, say b, in it and then take it modulus with 11. So Num becomes Num = (Num*10 + b)%11.
The final value of Num will be the required remainder.

Time Complexity

O(L) per test case, where ‘L’ is the number of digits in ‘N’.

In the worst case, we are traversing ‘N’ once, digit by digit.

Space Complexity

O(1) per test case.

In the worst case, we are taking constant extra space.

(100% EXP penalty)

Remainder When Divided By 11

Console