Posts

GCJ Qualification Round 2017 Problem B. Tidy Numbers

Problem Statement :  https://code.google.com/codejam/contest/3264486/dashboard#s=p1 Description : Basically you are given a number and one has to find the  largest number whose digits are all in increasing order. For example given 132   , largest number less than this where all digits are in increasing order is 129   since 9 > 2 > 1 For input 200 , output should be 199 My Approach : Since the input can be very large, I am keeping the number in string rather than integer.This also save all modulo and division operation. Start scanning from right hand side . Case 1 : If number at the index is 0 , make it as 9   and also decrements number at previous index. Do this until it is non-zero. Case 2 : If number at this index is smaller than its previous , for example 32 , since 2 is smaller than 3 we know the best we can do is,make this index 9. Not only this index but all the indices on right side of this index should be 9 as well. ...
Post a Comment
Read more

TopCoder SRM 723 TopXorer DIV I

Problem Statement:  https://community.topcoder.com/stat?c=problem_statement&pm=14736&rd=17027 Description: Given an array of number a , we have find what is the maximum XOR possible among them.One has to choose any number from 0 to a[i] My Approach: First lets sort the input array. Set the result as maximum of number of  bits required to stored largest a[i]. For example if a =9 which is (1001) i.e. 4 bits set the results as (1111) i.e. 15. flipped : This array stores whether the first bit of the number is flipped or not. This useful, let me explain with example suppose number is 1001 , to get a smaller number than this , we can flip 0 any any intermediate position only if top most bit is flipped. i.e. 0110 , which is 6 < 9 , At the same time if intermediate bit is 1,  it can be flipped unconditionally. for example 110 , second bit can be changed to 0 to achieve a smaller number i.e. 5 (101) Now scan each bit position for every a[i]  For all i =...
Post a Comment
Read more

Topcoder SRM 724 DIV 2 OrAndSumEasy

OrAndSumEasy : You are given pairOr & pairSum and we have to determine if it is possible or not. Let’s revisit truth table of OR and SUM OR: x y x|y 0 0 0 0 1 1 1 0 1 1 1 1 SUM: x y x+y 0 0 0 0 1 1 1 0 1 1 1 0(1) Few facts about the input OR of two number can never exceed SUM If OR is even, SUM cannot be odd. See row 1 of above truth tables.Note that converse is not true unless we know of carry bit of previous bit operation. This is explained below. Another obvious fact is SUM can never exceed OR by more than 1 bit, which is carry bit. Test case like {1, 100} will fall under this category and be solved straightaway. To solve further, iterate from lsb of pairSum and pairOr . Let’s define truth table for both cases when carry is 0 and carry 1 To read this table first check the i th bit of pairSum and see what all possible value pairOr can take. If pairOr has expected value, i...
Post a Comment
Read more