DIVISIBLEBY8 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: ekeshwarj_5
Preparer: jay_1048576
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given a large number N, find the minimum number of digit changes required to make it divisible by 8.

EXPLANATION:

Among any 8 consecutive numbers, one of them will be divisible by 8, since their remainders upon division by 8 will increase by 1 at each step.

So, it’s always possible to use at most one change to reach the desired target; and further, we can do so by only changing the last digit.
This means we can simply try every units digit from 0 to 9 (or even find mathematically which digit to use, depending on N\bmod 8), and see if the resulting number is divisible by 8 or not.
Checking a large number for divisibility by 8 can be done in various ways; here’s a few of them.
Perhaps the simplest one is to note that it’s enough to consider only the last three digits of the number, so take them into an integer and check directly.

TIME COMPLEXITY

\mathcal{O}(|N|) per testcase.

CODE:

Preparer's code (C++) 
/*...................................................................*
 *............___..................___.....____...______......___....*
 *.../|....../...\........./|...../...\...|.............|..../...\...*
 *../.|...../.....\......./.|....|.....|..|.............|.../........*
 *....|....|.......|...../..|....|.....|..|............/...|.........*
 *....|....|.......|..../...|.....\___/...|___......../....|..___....*
 *....|....|.......|.../....|...../...\.......\....../.....|./...\...*
 *....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
 *....|.....\...../.........|....|.....|.......|.../........\...../..*
 *..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
 *...................................................................*
 */
 
#include <bits/stdc++.h>
using namespace std;

void solve(int tc)
{
    int len;
    cin >> len;
    string n;
    cin >> n;
    int mod = 0;
    for(int i=0;i<n.length();i++)
        mod = (mod*10+n[i]-'0')%8;
    if(mod == 0)
    {
        cout << n << '\n';
        return;
    }
    int last = n.back()-'0'+8-mod;
    if(last>=10)
        last -= 8;
    cout << n.substr(0,n.length()-1) << last << '\n';
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc=1;
    cin >> tc;
    for(int ttc=1;ttc<=tc;ttc++)
        solve(ttc);
    return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
    len, n = input().split()
    mnch, ans = 4, n
    for i in range(8, 1000, 8):
        s = str(i)
        if len(s) > len(n): break
        if len(n) <= 3 and len(s) < len(n): continue
        if len(n) >= 4: s = '0'*(3 - len(s)) + s
        changes = 0
        for j in range(len(s)):
            changes += n[len(n)-1-j] != s[len(s)-1-j]
        if changes < mnch:
            mnch = changes
            ans = n[:len(n) - len(s)] + s
    print(ans)
2

Link to My Submission
I precomputed all the 3 digit numbers that were divisible by 8, and then computed minimum according to last 3 digits(divisibility rule of 8). Can you tell where my code fails?

1 Like
3

Perhaps try the test case:

1
4 1025
4

Thanks a lot.

5

My code isn’t passing a single test case, although I implemented a similar idea to what is discussed in the tutorial. I will be thankful to you if you can point out the mistake in my code below:

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

int main() {
	// your code goes here
	int T;
	cin>>T;
	
	while(T--){
	    int n;
	    cin>>n;
	    string s;
	    cin>>s;
	    
	    if(n<3){
	        int num;
	        if(s.size()==1){
	            num=s[0]-'0';
	        }
	        else{
	            num = (s[0]-'0')*10+(s[1]-'0');
	        }
	        
	        int diff = num%8;
	        int lastDigit = num%10;
	        
	        if(lastDigit-diff>0){
	            num-=diff;
	        }
	        else{
	            num+=8-diff;
	        }
	        
	        s=num+'0';
	        cout<<s<<endl;
	    }
	    
	    else{
    	    int num = (s[n-3]-'0')*100 + (s[n-2]-'0')*10 + (s[n-1]);
    	    int diff = num%8;
    	    if(diff==0){
    	        cout<<s<<endl;
    	    }
    	    
    	    else{
    	       if((s[n-1]-'0')-diff>=0){
    	       s.at(n-1)=s.at(n-1)-diff;
        	    }
        	    else{
        	       s.at(n-1)=s.at(n-1)+8-diff;
        	    }
        	   cout<<s<<endl;
    	    }
	    }
	}
	return 0;
}

Thank you!

6

i just bruteforce the two last digits
and took the digits that look similar in string N and ( ( N - 2 ) + twodigits % 8 ) = 0
any one can give me a counter example where my code failed ?
submission

7

Hi! I used the same logic to solve this problem as specified in the explanation, but I implemented it differently. I get all the sample inputs right when I run it, but it shows me that I’ve entered the wrong answer on submission. I am unable to figure out what is wrong with my code. Could you please help me figure out what I have done wrong? Thank you.

Here’s the link to my submission.

8

There are some cases that may cause in trouble, such as,
1
1 900

1
1 1000

1
1 200

codechef.com/viewsolution/1025297287
You may visit here. There, I explained this problem. I think, that would be helpful))

9

CodeChef: Practical coding for everyone where am i going wrong can somebody please help me out

10

In Problem Statement, it is given that "Find a positive integer M (without leading zeroes) divisible by 8, formed by changing minimum number of digits in N.
So What if a String already has Leading zero then we have to make that change too…
Not a big Deal But this Edge Case hit hard when there is leading zero in 2 digit or 3 digit already given number…
I didn’t see any TestCases testing this part of problem…
Or Maybe the Question wasn’t being design that way but if Yes then Please update the Test cases…

11

Thank you for helping me out.