Find the largest multiple of 3 解答
2024-08-20 05:11:31
Question
Given an array of non-negative integers. Find the largest multiple of 3 that can be formed from array elements.
For example, if the input array is {8, 1, 9}, the output should be “9 8 1″, and if the input array is {8, 1, 7, 6, 0}, output should be “8 7 6 0″.
Solution
A number is multiple of 3 if and only if the sum of digits of number is multiple of 3.
1. Sort the array in non-decreasing order. 2. Take three queues. One for storing elements which on dividing by 3 gives remainder as 0.The second queue stores digits which on dividing by 3 gives remainder as 1. The third queue stores digits which on dividing by 3 gives remainder as 2. Call them as queue0, queue1 and queue2 3. Find the sum of all the digits. 4. Three cases arise:
……4.1 The sum of digits is divisible by 3. Dequeue all the digits from the three queues. Sort them in non-increasing order. Output the array. ……4.2 The sum of digits produces remainder 1 when divided by 3.
Remove one item from queue1. If queue1 is empty, remove two items from queue2. If queue2 contains less than two items, the number is not possible. ……4.3 The sum of digits produces remainder 2 when divided by 3.
Remove one item from queue2. If queue2 is empty, remove two items from queue1. If queue1 contains less than two items, the number is not possible. 5. Finally empty all the queues into an auxiliary array. Sort the auxiliary array in non-increasing order. Output the auxiliary array.
最新文章
- bootstrap学习笔记--bootstrap组件
- QT 对话框二
- 如何开发 Sublime Text 2 的插件
- 学习iOS笔记第一天的C语言学习记录
- X-UA-Compatible设置兼容模式
- Objc基础学习记录5
- LVS的调度算法分析
- [原创] linux 下上传 datapoint数据到yeelink 【golang版本】
- 生产者/消费者问题的多种Java实现方式
- jsp 表单回显
- mui返回上个页面并刷新数据
- HashMap 1.7
- Android 基础 十一 Android的消息机制
- CTF中图片隐藏文件分离方法
- 个人对java中对象锁与类锁的一些理解与实例
- 关于UrlEncode 一团乱麻的问题,后续彻底理解。Java中的 URLEncoder 与 URLDecoder无bug
- Transaction ACID (转载)
- 贪心--cf、education62-C
- hibernate3的配置
- scp命令详解—跨服务器复制文件