# DCP-118: Rearrange Digit Back to All Problems

Hard Divide and Conquer > Dynamic Programming

Pokemon found a binary number. He can switch places of its bits. Help him make the greatest binary number without leading zeros which is divisible by 30 by switching bits position. If it is not possible then return -1. Input: ------ Input starts with an integer **T (1<=10)**, denoting the number of test cases. Each case contains a binary number. Length of the binary number is less then **1000**. You can assume there are no leading zeros. Output: ------- For each case of input, output the greatest binary number which is divisible by 30 otherwise print -1. Sample Input ------------ 2 10 11101 Sample Output ------------- -1 11110

### Problem Limits

 Language Time Limit (seconds) C 1.00 C++ 1.00 C++14 1.00 C# 2.00 Go 2.00 Java 2.00 JavaScript 2.00 Objective-C 2.00 Perl 2.00 PHP 2.00 Python 2.00 Python3 2.00 Ruby 2.00 VB.Net 2.00

# 17/81

Solve/Submission

### Ranking

# User Language Timing
01 feodorv Cpp14 0.01s
02 Morass Cpp14 0.01s
03 i_love_nikita_gautam Cpp14 0.02s
04 SakibAlamin Cpp14 0.04s
05 Z0RR0 Cpp14 0.15s
06 sakib_muhit Cpp14 0.18s
07 moinul_shaon Cpp14 0.33s
08 Robbinb1993 Cpp 0.35s
09 INUA Cpp14 0.43s
10 sahedsohel Cpp14 0.52s
11 jayanto Cpp14 0.76s
12 Mahmudul_Tushar Cpp14 0.94s
13 underSpirit Cpp14 1.35s
Feedback